More Graphing with Graphviz

I started working on Prim’s Minimum Spanning tree algorithm again. Last time, I wanted to ‘see’ the input graph so I can determine the final value.

This time, I needed help debugging my implementation and wanted to graph the algorithm’s progress. Graphing the algorithm’s progress was a lot more work and I want to share some details and tips.

Tools I used to display the algorithm’s progress:

• Graphviz
• ImageMagick

Graphviz is a fantastic tool. As I use it more and understand the ins and outs of the tool, I am happy using a free and open source tool for graphing. Graphviz will do most of the graphing work.

ImageMagick another great tool. For this problem, I only use ImageMagick to put together images.

I constructed all the graphs with these basic primitives:

• Rendering with Dot
• Basic Graph
• Weight Highlight
• Node Highlight
• Source Node
• Additional Graphviz Tips

Rendering Graphs with Dot

To create the images from the graph file:

$ dot -O -Tpng *.dot

Basic Graph

This basic graph representation is:

graph {
  a [color = black]
  b [color = black]
  c [color = black]
  d [color = black]
  e [color = black]
  a -- b [label="2"];
  a -- d [label="6"];
  b -- c [label="3"];
  b -- d [label="8"];
  b -- e [label="5"];
  c -- e [label="7"];
  d -- e [label="9"];
}

Weight Highlight

To highlight a weight, add: fontcolor=<color> to the label:

graph {
  a [color = black]
  b [color = black]
  c [color = black]
  d [color = black]
  e [color = black]
  a -- b [label="2" fontcolor=red];
  a -- d [label="6"];
  b -- c [label="3"];
  b -- d [label="8"];
  b -- e [label="5"];
  c -- e [label="7"];
  d -- e [label="9"];
}

Node Highlight

To highlight the node, change the: color=<color> in the node info:

graph {
  a [color = red]
  b [color = red]
  c [color = black]
  d [color = black]
  e [color = black]
  a -- b [label="2"];
  a -- d [label="6"];
  b -- c [label="3"];
  b -- d [label="8"];
  b -- e [label="5"];
  c -- e [label="7"];
  d -- e [label="9"];
}

Source Node

I use the attributes fillcolor=grey style=filled to highlight the source node by filling it to stand out from the other nodes:

graph {
  a [color = black fillcolor=grey style=filled]
  b [color = black]
  c [color = black]
  d [color = black]
  e [color = black]
  a -- b [label="2"];
  a -- d [label="6"];
  b -- c [label="3"];
  b -- d [label="8"];
  b -- e [label="5"];
  c -- e [label="7"];
  d -- e [label="9"];
}

Creating Animated Graphs

To animate the all images generated:

$ convert  -delay 100 -loop 1 *.png prims_mst.gif`

This combined with the basic attributes I animated Prim’s Minimum Spanning Tree algorithm:

Whew! What a lot of work to just see what’s going on inside Prim’s Minimum Spanning Tree algorithm.

Additional Graphviz Tips

Things I also learned in Graphviz while working on this problem.

Same Nodes, Different Order, Different Layout

Dot layout engine produces different graph layout with different input, even if the nodes are the same

• Graph 1:

  graph {
    a -- b [label="2"];
    a -- d [label="6"];
    b -- c [label="3"];
    b -- d [label="8"];
    b -- e [label="5"];
    c -- e [label="7"];
    d -- e [label="9"];
  }
  

• Graph 2:

  graph {
    a -- d [label="6"];
    a -- b [label="2"];
    b -- d [label="8"];
    b -- c [label="3"];
    c -- e [label="7"];
    b -- e [label="5"];
    d -- e [label="9"];
  }
  

Same Nodes, Same Order, Same Layout

Dot layout will be more consistent if nodes attributes appear at the beginning, in the same order, even with different attributes and/or order:

• Graph 1:

  graph {
    a [color = black]
    b [color = black]
    c [color = black]
    d [color = black]
    e [color = black]
    a -- b [label="2"];
    a -- d [label="6"];
    b -- c [label="3"];
    b -- d [label="8"];
    b -- e [label="5"];
    c -- e [label="7"];
    d -- e [label="9"];
  }
  

• Graph 2:

  graph {
    a [color = red fillcolor=red style=filled]
    b [color = black]
    c [color = black]
    d [color = black]
    e [color = black]
    a -- b [label="2" fontcolor=red];
    a -- d [label="6"];
    b -- c [label="3"];
    b -- d [label="8"];
    b -- e [label="5"];
    c -- e [label="7"];
    d -- e [label="9"];
  }
  

Pinning Nodes

If it is absolutely necessary, nodes are pinnable to a location. Neato, another graphviz layout engine that works on undirected graphs, can place nodes a specified positions, even nodes appear in different order.

Neato takes the same arguments as dot:

$ neato -Tpng -O *.nea

• Pinned Graph 1

  graph {
    a [color = black pos="0,0!"]
    b [color = black pos="0,1!"]
    c [color = black pos="1,0!"]
    d [color = black pos="1,1!"]
    e [color = black pos="0,2!"]
    a -- b [label="2"];
    a -- d [label="6"];
    b -- c [label="3"];
    b -- d [label="8"];
    b -- e [label="5"];
    c -- e [label="7"];
    d -- e [label="9"];
  }
  

• Pinned Graph 2

  graph {
    a [color = black pos="1,1!"]
    b [color = black pos="1,0!"]
    c [color = black pos="0,1!"]
    d [color = black pos="0,0!"]
    e [color = black pos="1,2!"]
    a -- b [label="2"];
    a -- d [label="6"];
    b -- c [label="3"];
    b -- d [label="8"];
    b -- e [label="5"];
    c -- e [label="7"];
    d -- e [label="9"];
  }
  

Clustering Nodes

Dot has a ‘cluster’ feature to outline a group of nodes:

graph {
  a [color = red fillcolor=grey style=filled]
  b [color = black]
  c [color = black]
  d [color = black]
  e [color = black]
  a -- b [label="2" fontcolor=red];
  a -- d [label="6"];
  b -- c [label="3"];
  b -- d [label="8"];
  b -- e [label="5"];
  c -- e [label="7"];
  d -- e [label="9"];
 subgraph cluster_0 {
    a -- b;
    color = blue;
  }
}

Conclusion

From this experience with Graphviz, I enjoy working with graph algorithms more. I like being able to see what is going on with the algorithm, not just the start or end result.

Developing and/or debugging a graphing algorithm is so much nicer to have visual representation than the final ‘weight’ value.

Next time I have to work with a graphing algorithm, I’ll use these to help visualize what is going on.