
Boost : 
Subject: Re: [boost] Graph Algorithm Advice
From: J Birch (birchsport_at_[hidden])
Date: 20121119 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk