# 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
``````