Parsing a Graph

In Ruby parsing a graph data-structure from an input stream is surprisingly easy if I represent the graph internally as a hash of node-to-neighbours. Consider the following graph data input:

a: [b, c, d]
b: [b, c]
c: [a]

Node a points to neighbour nodes b, c and d. Similarly node c points to neighbour node a. Here is the Ruby code which parses this graph, assuming it comes from stdin:

require 'yaml'
g = YAML::load(STDIN)

I can generate a dot file that visualizes the graph like so:

puts "digraph {"
g.each_key do |v|
  g[v].each { |n| puts "  #{v} -> #{n};" }
end
puts "}"

Visualization of Graph g by graphviz dot

If I want to add support for edge weights then I can do it by changing the input format:

a: {b: 3, c: 3, d: 2}
b: {b: 0, c: 1}
c: {a: 3}

All I’m doing is playing on YAML, so my parsing code need not change. I “added” a feature without changing a single line of code!

It is interesting to find an analogous technique in C++, where I parse a graph into a map. The following code will take a directed, unweighted graph from stdin:

#include<iostream>
#include<algorithm>
#include<iterator>
#include<map>
#include<set>
#include<sstream>
#include<string>

using namespace std;
typedef map<string,set<string> > graph;

int main(int argc, char* argv[])
{
    string line;
    graph g;
    while( getline(cin, line) ) {
        istringstream ss(line);
        string from, to;
        ss >> from;
        graph::mapped_type neighbours;
        copy(istream_iterator<string>(ss),
             istream_iterator<string>(),
             inserter(neighbours, neighbours.end()));
        g.insert(make_pair(from, neighbours));
    }

    return 0;
}

The standard C++ library doesn’t support YAML, but it does provide help for parsing whitespace-delimited input through the iostream library. That’s what the code above takes advantage of. Graph input for the above C++ program will thus look like so:

a b c d
b b c
c a

I leave it as an exercise for you to add support for parsing a weighted graph:

a b 3 c 4 d 5
b b 0 c 1
c a 4