Re: [boost] Graph Algorithm Advice

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
>