Graph Algorithm Advice
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. Anyone out there have some pointers on how to do this? Thanks! Birch
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
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@osl.iu.edu> 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
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@osl.iu.edu> 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
participants (2)
-
J Birch -
Jeremiah Willcock