README

The first tool, "gengraph", generates graphs in the GraphML format, see

  http://graphml.graphdrawing.org

The graph types that can be generated are as follows:

 - waxman                      A random graph introduced in the paper by B.M. 
                               Waxman: Routing of multipoint connections. 
                               IEEE Journal on Selected Areas in 
                               Communications, 6(9)

 - planar                      Planar random graph generated by the standard 
                               LEDA planar graph generator.

 - planar_delaunay             Nodes are positioned at random in a unit square 
                               and the Delaunay triangulation is computed. To 
                               obtain a smaller number of edges, edges are 
                               deleted at random.

 - compinduced                 Generate a graph originated in equal-sized 
                               components, which is done as follows: From top 
                               down split each component into a number of 
                               selected nodes and some components. Then the 
                               components at level 1 are constructed by 
                               connecting the nodes chosen for the respective 
                               component, after that edges from inside each 
                               component to the nodes chosen to be adjacent to
                               that component are established, and last 
                               selected nodes are connected one to another.
                               The characteristics of the graph are read from 
                               an input file whose format is:
                                #nodes #levels
                                (for each level: for each component one level 
                                above that is to be split:) 
                                #(selected nodes) #components #(adjacent nodes)

 - hierarchical_delaunay       A given number of components are generated 
                               with the planar_delaunay function and laid out 
                               as a grid. Then, another high-level 
                               planar_delaunay graph is generated which
                               occupies the whole grid area. Per component, 
                               a given number of nodes in the corresponding 
                               grid cell of the high-level graph is connected 
                               to nodes from the component.

 - planar_kuratowski           From a standard random graph edges violating 
                               the statement of the Kuratowski theorem are 
                               deleted until the graph gets planar.

 - planar_kuratowski_complete  Same as planar_kuratowski, but the procedure 
                               starts with a complete graph

 - six_grids                   A regular graph consisting of hexagons.

 - rectangular                 A n times m grid.

 - diameter                    A regular triangulated planar graph that has a 
                               given diameter.
                               Caution: the straight-line embedding is not 
                               planar!

 - globe                       A regular globe graph.

 - icosahedron                 A icosahedron.

 - triangle                    A regular graph consisting of triangles

 - triangle2                   Given a graph (e.g., a icosahedron) consisting 
                               of triangles with the nodes on a unit sphere, 
                               each triangle is split in four triangles 
                               by adding a new node in the middle of each edge.
                               The new nodes are projected to the sphere 
                               after each iteration.

 - graph_with_preference       A graph with preference.

 - small_world                 A small-world graph.


Optionally, the graphs can be made connected by either trying to generate 
graphs until the generated graph is connected, or by taking the maximal 
component of the graph.

The second tool, "graphml2ps", produces a picture of a GraphML graph in 
Postscript. 

For further usage of the programs call them without options.



Examples:
=========
gengraph --waxman -n 1000 -a 0.01 -b 5 -x 1000 -y 1000 -c 2 -f waxman.graphml
gengraph --hierarchical_delaunay -N 56 -M 135 -n 59 -m 160 -a 4 -C 16 -f hdel.graphml
gengraph --six_grids -x 21 -y 21 -f sixgrid.graphml 
gengraph --rectangular -x 20 -y 50 -f rect.graphml
gengraph --diameter -D 333 -f diameter.graphml
gengraph --globe -x 31 -y 31 -f globe.graphml
gengraph --icosahedron -r 1 -f icosahedron.graphml
gengraph --triangle -I 44 -f triangle.graphml
gengraph --triangle2 -I 3 -i icosahedron.graphml -f sphere.graphml
gengraph --graph_with_preference -n 1000 -d 3 -f pref.graphml
gengraph --small_world -n 1000 -r 10 -p 0.4 -f smallworld.graphml

graphml2ps sixgrid.graphml > sixgrid.ps