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
