Re: [boost] Graph Algorithm Advice

Subject: Re: [boost] Graph Algorithm Advice
From: J Birch (birchsport_at_[hidden])
Date: 2012-11-19 17:49:34

Thank you Jeremiah.  That gets me very close to what I am looking for.  Do you have an example how this would be used with a DFS?

Thanks!
Birch
On Nov 19, 2012, at 5:13 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:

> 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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost