SAGE and Cliquer

SAGE is free open-source mathematics software that can be found at: http://www.sagemath.org/. SAGE has lots of useful support for graph theory. However, if you'd like to find cliques in large graphs, it's much faster to outsource the work to a set of routines called Cliquer.

Cliquer is a set of C routines for finding cliques in graphs. The routines are based on an algorithm developed by Patric Östergård. More details and the routines can be found at: http://users.tkk.fi/pat/cliquer.html.

After installing SAGE and downloading and compiling the Cliquer routines, I used the following steps to generate a graph in SAGE and then find cliques in that graph with Cliquer.

1. GENERATING AND OUTPUTTING A GRAPH IN SAGE

The first step is to create your desired graph. For simplicity, I use one of SAGE's existing graph constructors in this example.

G = graphs.FlowerSnark()

Now the graph is constructed. The next lines of code output lines of code that can be read in by Cliquer. (Cliquer requires input files to be formated using the DIMACS file formate.)

eList = G.edges()
vList = G.vertices()
line1 = 'p edge ' + repr(len(vList)) + ' ' + repr(len(eList))
print line1
for x in eList:
  print "e", repr(vList.index(x[0])+1), repr(vList.index(x[1])+1)

This will print out all of the necessary lines for input. If the graph is small, then you can just copy and paste the output into a text file and save the file in Cliquer's root folder. If the graph is large enough, then SAGE says "Warning! Output truncated" and nicely saves the output in a text file for you. Just move this file in Cliquer's root folder and you're ready for the next step.

2. RUNNING THE CLIQUER ROUTINES

Open up Terminal and navigate to the Cliquer root folder. Check out the options by typing

./cl - h

That will give you a list of options. Most likely you'll just want to type

./cl -s -x full_output.txt

This will give you the size of the largest clique and the corresponding vertices. It is important to note that Cliquer indexes the vertices from 1 to n where n is the number of vertices. However, SAGE indexes the vertices from 0 to n-1. Therefore if Cliquer lists vertex x as a vertex in the clique, then it corresponds to vertex x-1 in SAGE's vertex list.