Generate Graphs

Once your algorithm is defined, you need to define some topology using dot. For small graphs, it is ok to do it by hand. For bigger graphs, you migth consider using gg and gg-deco, that are part of the sasa distribution:

Generate graphs skeletons with gg

gg -h
gg is an experimental graph generator.
usage: gg <graph-kind> [<option>]*
where <graph-kind> can be:
  clique           Generate a clique graph
  star             Generate a star graph
  ring             Generate a ring graph
  grid             Generate a grid graph
  HC               Generate a hyper-cube graph
  ER               Generate a graph using the Erdos Renyi algo
  BA               Generate a graph using the Barabasi‚ÄďAlbert algo
  tree             Generate an acyclic graph (tree)
  UDG              Generate a graph using the Unit Disc Graph algo
  QUDG             Generate a graph using the Quasi UDG algo

<option> can be:
  --output, -o <string>
                   Redirect stdout into a file
  --silent, -s     be quiet
  --directed, -dir Generate a directed graph.
  --help, -h       Print this help

Use 'gg <graph-kind> -h' to see specific options.
gg grid -h
gg is an experimental graph generator.
usage: gg grid [option]*
<option> can be:
  --output, -o <string>
                   Redirect stdout into a file
  --silent, -s     be quiet
  --directed, -dir Generate a directed graph.
  --help, -h       Print this help


<option> specific to this <graph-kind>:
  --width, -w <float>
                  Set the grid's width

  --height, -he <float>
                  Set the grid's height

Decorate graphs skeletons with gg-deco

gg-deco -h
usage: gg-deco "<decoration pattern>" <input-file.dot> [<option>]*
decorates an <input-file.dot> using a <decoration pattern>.

The <decoration pattern> specifies which algos should be attached to which nodes.
Its syntax (in EBNF) is:
   <decoration pattern> ::= <deco><more>
   <deco> ::=
    | <int>:<string>
    | <int>-<int>:<string>
    | <int>-:<string>
   <more> ::= ([ \t]*<deco>)*

  "i:file"   attaches <file> to node number <i> (the first node is numbered 0)
  "i-j:file" attaches <file> to nodes number <i>, <i>+1, ..., <j>
  "i-:file"  attaches <file> from node number <i> untill the end

decorations are handled from left to rigth (i.e., the rigth-most one wins).

Example: the <decoration pattern> "0:root.ml 1-:p.ml" assigns
  - "root.ml" to the first node, and
  - "p.ml" to the other ones.

<option> can be:
   --output, -o <file>
            Redirect stdout into a <file>
   --help, -h  Print this help

An example

The following commands generate a random graph with 30 nodes using the Erdos-Renyi algorithm, and launch an interactive session that computes a bfs spanning tree. We use the sfdp dot viewer as it give better result than the default one on this kind of graphs.

[ -d "sasa" ] || git clone https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/synchrone/sasa.git
cd sasa/test/bfs-spanning-tree
gg ER  -n 30 -o ER30.dot
gg-deco "0:root.ml 1-:p.ml" ER30.dot -o ER30.dot
make ER30.ml
rdbg -sut "sasa ER30.dot"
dot_view:=sf;;
nr