Boost :

Subject: Re: [boost] Graph Algorithm Advice
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-11-20 13:08:29

On Mon, 19 Nov 2012, J Birch wrote:

> 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?

Not off hand; it seems like RGL's bfs_search_tree_from method might be
what you want (BFS works as well as DFS for this application). You will
then get a tree that you can traverse using the pseudocode I gave earlier.

-- Jeremiah Willcock

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