Re: [boost] Graph Algorithm Advice

Subject: Re: [boost] Graph Algorithm Advice
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-11-19 17:13:47

On Mon, 19 Nov 2012, J Birch wrote:

> This isn't a Boost Graph problem per se, just a graph algorithm 
> question.  Let's say I have the following graph:
>
>
>
> I want to represent this graph in a certain way.  In the small legend 
> box above, there are 2 versions of a correct answer.  I want to print 
> out each vertex followed by it's immediate adjacent vertex.  If it has 
> more than one, then each path from that point should be wrapped in a 
> '()'.  Currently, I am using the Ruby RGL package and have tried both a 
> directed and an undirected graph using a depth first search traversal, 
> and have yet to hit on an algorithm that takes every edge case.

Are the graphs always trees?  If so, it looks like you can just do a 
preorder traversal (parents first, then children), wrapping any child 
subtrees in parentheses whenever they are not the last for their parent:

void print(node n) {
   cout << contents(n);
   size_t index = 0;
   for (c : children(n)) {
     bool last = (index == num_children(n) - 1);
     ++index;
     if (!last) cout << "(";
     print(c);
     if (!last) cout << ")";
   }
}

If you don't know the parent/child structure but know you have an 
undirected tree, use BFS or DFS to generate the correct directions for the 
tree.

-- Jeremiah Willcock