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