adamcrussell

Graph Visualization (for small graphs)

Visualizing graphs is somewhat surprisingly complex when the size of the graph (i.e. the number of vertices and edges) gets very large. Even relatively small graphs become unreadable balls of spaghetti unless the layout is well done. Happily, there are many great packages for visualizing graphs. Perhaps the oldest and most widely used is Graphviz. Sometimes even Graphviz is a bit much of the graph is very small, sometimes you'd be happy with just some console output. As in many situations, it turns out there is a CPAN module for that! In this case the module is Graph::Easy which provides support for a variety of input and output formats. Let's see how it is used with Perl Weekly Challenge 056.

The Challenge

You are given a binary tree and a sum, write a script to find if the tree has a path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered for a sum.

What I Did

ch-2.pl
ch-2.pl

Graph::Easy is used here in display_path(). There we take our graph and highlight the path vertices with an asterisk and then format it in Graph::Easy's own markup format. We could have also used another input format (such as GraphViz dot format or GDL) if the situation needed.

If we use the above functions with the following code
my $graph = new Graph(multivertexed => true);
my @a = (11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31);     
my $root;     
for my $a (@a){          
   if(!$root){             
       $root = insert($graph, $root, $a)         
   }
   else{
            insert($graph, $root, $a)         
   }     
}     
while($graph->has_vertex("left") && $graph->has_vertex("right")){
   $graph->delete_vertices("left", "right");     
}     
my $path = find_path_sum($graph, SUM, [$root]);     
display_path($graph, $path); 

Then we would have something that looks like this!

The path showing the sum of 35 is highlighted in this console output.

If we prefer something a little nicer than we can output a Graphviz dot file and then if we run the command
$ dot -Tpng ch-2.dot -o ch-2.png
We'd get this:

ch-2.png
ch-2.png

Notes

  • Obviously this would not be a great method of visualizing graphs of any size but for small graphs this sort of formatted console output is perfect for quick debugging!
  • Graph::Easy also installs a command line tool graph-easy. This is convenient for command line pipes and scripts, especially if you just want to quickly displays someone else's data.

Comments for this post were locked by the author