Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk