Using FCA Software with Sage

The computer algebra software Sage is a free open source alternative to Magma, Maple, Mathematica and Matlab. Hopefully, one day someone will write FCA tools that can be fully integrated with Sage. In the meantime, this website explains what can already be done with currently available technology. (Further information on how to use Sage and FCA software for teaching mathematics can be found in these on-line course materials.)

Sage contains core modules and provides interfaces to packages which can also be used individually. Because some of the functionality exists both in the Sage core and the individual packages, the code needs to be slightly changed depending on whether functions are used via Sage or via an individual package.

Contents of this page:

Files used in the code examples/Preprocessing with FcaStone

The code below uses the formal context from this example. The FcaStone command-line tool was used to convert between the different FCA file formats. For example, to convert from cxt to csv format: 
fcastone sageExample.cxt sageExample.csv
The following files are used in the code examples below (the "txt" extensions should be removed after saving the files): It is possible to call FcaStone via a system call from Sage. The following example converts a cxt file into a slf file using FcaStone. It then processes the slf file by deleting the first lines up to and including "[relation]", splitting the lines into arrays and finally creating a binary matrix of the relation in Sage: 
import subprocess
import string
from sage.all import *

pipe = subprocess.Popen("fcastone -N sageExample.cxt filename.slf", \
shell=True, bufsize=1,stdout=subprocess.PIPE).stdout
text = pipe.readlines()
pipe.close()

text= text[(text.index("[relation]\n") +1):]
for i in range(len(text)):
   text[i] = string.split(text[i])

M1 = Matrix(GF(2),text)
print M1

NetworkX: Importing formal contexts as graphs

The NetworkX tool (which is part of Sage) provides numerous graph algorithms. The easiest way to import a formal context into NetworkX is to use a csv file which can be obtained as described in the previous section. Note: it is important not to have blank lines at the end of the csv file. This can now be imported into NetworkX as a graph as follows: 
from networkx import *
G = read_edgelist("sageExample.csv",delimiter=",")
or into Sage: 
import networkx
from sage.all import *
G = networkx.read_edgelist("sageExample.csv",delimiter=",")
G2 = Graph(G)
In this case G is a graph in the NetworkX format whereas G2 is the same graph in Sage's format. G can use NetworkX functions (e.g. G.nodes()), whereas G2 can use either Sage functions (G2.show()) or NetworkX functions (G2.networkx_graph().nodes()).

NetworkX can be used to analyse the (bipartite) graph consisting of formal objects and formal attributes in a variety of manners. NetworkX also allows to convert the data into a number of other formats, including matrices.

NetworkX: Importing concept lattices as graphs

In order to import a concept lattice as a graph into NetworkX, the "dot" file of the lattice as produced by FcaStone can be converted into a csv file of the lattice graph using the following Python script. The script reads a file sageExample.dot and outputs a file sageExampleLattice.csv. This script will only work with dot files produced by FcaStone, not dot files in general. 
import re
file = open("sageExample.dot","r")
text = file.readlines()
file.close()

outputfile = open("sageExampleLattice.csv","w")

keyword1 = re.compile(r"\[|\{|\}")
keyword2 = re.compile(r" -> ")

for line in text:
    if not keyword1.search (line):
         outputfile.write(keyword2.sub(",",line))

This can be read into NetworkX using
G = networkx.read_edgelist("sageExampleLattice.csv",delimiter=",",create_using=DiGraph()) .

If pygraphviz or pydot are installed, it is also possible to read a dot file into NetworkX using read_dot(path). Most likely the dot file produced by FcaStone might need to be edited before it can be read in this manner because it contains invisible edges for placing the labels.

NetworkX: Producing gif files of the graphs (via Graphviz)

Using Sage, graphs can be visualised using G.show().

In order to visualise the graphs using NetworkX (without Sage), one needs to install further software. If Graphviz is installed, then the proper interfaces are established via pygraphviz or pydot. If one does not want to also install those tools, there is a very primitive write_gif() function that produces gifs using Graphviz without pygraphviz or pydot. The code is available here and some more information on how to use it is on this page. To install write_gif() one can save it as writegif.py into the readwrite directory in NetworkX and edit the __init__.py file in that directory to import it.

Matrices: importing formal contexts as matrices

There are at least three different ways of representing matrices in Sage: using the Sage core, using Numpy and using Sympy which all have different functions and structures. Currently there does not seem to be an implementation of Relation Algebra or Boolean Matrix Algebra in Sage therefore not all context operations that are common for FCA applications are available. But Sage does allow Matrices to be represented over GF(2) which ensures that they contain only 0s and 1s.

There are different ways of importing formal contexts:

a) Convert the context to slf format and delete everything before and including "[relation]". Then use: 

import numpy
from sage.all import *
M1 = Matrix(numpy.loadtxt("sageExampleMatrix.txt"))
N1 = M1.change_ring(GF(2))
or b) import a csv file of a context, convert it to a graph and from there into a matrix: 
import networkx
import numpy
from sage.all import *
G = networkx.read_edgelist("sageExample.csv",delimiter=",")
M2 = networkx.to_numpy_matrix(G,['girl','woman','boy','man',\
'female','juvenile','adult','male'])[0:4,4:9]
N2 = Matrix(numpy.array(M2)).change_ring(GF(2))
The conversion from a graph to a matrix depends on which graph node corresponds to which matrix row/column. Therefore the to_numpy_matrix() function needs to know the sequence of the formal objects and attributes. The Numpy matrix is then reduced to those rows and columns which form the context (by using [0:4,4:9]) and converted into the Sage Matrix format. After issuing these statements N1 and N2 are equal.

In a similar manner the context can be converted into a Scipy sparse matrix using to_scipy_sparse_matrix(G).

The following table shows some of Sage's matrix operations that could be useful for FCA:

dual matrix (mirrored along diagonal) transpose(N1)
apposition of N1 and N2 N1.augment(N2)
subposition of N1 and N2 N1.stack(N2)
null matrix of dimension i Matrix(GF(2),i,i,0)
diagonal matrix of dimension i Matrix(GF(2),i,i,1)
test for equality N1 == N2
test for containment N1 < N2
switching rows i and j N1.swap_rows(i,j)
switching columns i and j N1.swap_columns(i,j)
forming a submatrix N1.submatrix(i,j,k,l)
calculating density N1.density()

Using lattice/poset operations

The code example shows how Sage's poset and lattice operations can be applied to concept lattices that have been imported as described in the section above. 
import networkx
from sage.all import *
G = networkx.read_edgelist("sageExampleLattice.csv",delimiter=",",create_using=DiGraph())
P = Poset((G.networkx_graph().nodes(),G.networkx_graph().edges()),cover_relations=True)
P.show()
P1 = Poset(G)
P1 == P
P.top()
P.bottom()
P.is_meet_semilattice()
L = LatticePoset(G)
L.is_distributive()

Future: How to develop a full FCA/Sage tool

Challenges/Questions:

If anybody is interested, the Sage community might be willing to help with respect to how to build Sage components.

References

Copyright 2010 Uta Priss.
www.upriss.org.uk