Read Me

GraphLayout v2.4
08 June 2010

Carlo Nicolini

**********************************************************************
************		How to build the source 				**********
**********************************************************************
How to use the programs:
	make all

To clean the executables:
	make clean


**********************************************************************
************		How to draw a DIMACS graph				**********
**********************************************************************

The GraphLayout program has many options:
Choose the format
-m		0 = DIMACS (Default)
		1 = EDGELIST (space separated edges)
		2 = DOT (GraphViz compatible)

Choose the solver to minimize the layout cost function
-s		0 = Choose BFGS method with line search interpolation
		1 = Choose conjugate gradient method with line search interpolation
			(very fast if Kamada Kawai method is used )
		
-f		0 = Use Kamada Kawai (need to compute all-pair-shortest-path), default
		1 = Use Fruchterman Reingold model	
		2 = Use resistance distance matrix embedding model
		3 = Use Kamada Kawai model with a cutoff of 6 nodes

-o	"test.dimacs": output the finished layout to "test.dimacs" file
 
Usage example:
Draw a graph with Fruchterman Reingold layout model using conjugate gradient

./GraphLayout -o graphname_layouted.dimacs -s 1 -f 1 graphname.dimacs

All the graphs given in input are expected to be in dimacs format, e.g. (check the blanks)
#nodenumber ( pos_x, pos_y ) degree list_of_adjacent_nodes
For example:

1 ( -7.3127, 6.9487 ) 2 2 3
2 ( 5.2755, -4.8986 ) 2 1 4
3 ( -0.0913, -1.0102 ) 3 1 4 5
4 ( 3.0319, 5.7745 ) 3 2 3 5
5 ( -8.1228, -9.4331 ) 3 3 4 6
6 ( 6.7153, -1.3447 ) 1 5

Usually the GraphLayout produces a .eps file using gnuplot with the final draw of the graph.
If this is not possible, first install gnuplot (ver. > 4) on a unix environment.

For example, if GraphLayout doesn't automatically create the .eps file of the graph, do as follow

	./GraphLayout [options] graphname.dimacs > graphname.dimacs.eps
	
and this will produce the graph eps.


**********************************************************************
******		How to measure the graph quality and features		******
**********************************************************************

The MeasureGraphQuality analyze the graph structure and measure its layout quality.
Usage example:
	./MeasureGraphQuality graphname.dimacs
create a graphname.dimacs.stat file with all the graph features and layout quality.	
	
To print to stdout a human readable information about the graph analyzed, select -p 1:
-p		1 	Print only a human readable graph information on stdout.

Usage example:
	./MeasureGraphQuality -p 1 graphname.dimacs
produces the following typical output.

Nodes 15
Edges 27
Max_deg 4
Min_deg 2
Avg_deg 3.6
Var_deg 0.64
Density 0.257143
Triangles  12
Diameter 4
Quality 1 0.542289
Quality 2 0.0184443