BGL: traversal algorithm for tree
I have implemented a rooted tree structure as a BGL graph. I need to be able to traverse the tree from root to leaves, while doing something at each vertex. I need to be able to do this as inorder and postorder traversal. My question is if it's possible to do this with any of the existing algorithms in BGL. My current thinking is to implement a function traversal( ... ), but if there already exists an alternative, I would prefer to use it. Björn
Hi Bj�rn, Here's a couple options: 1. Use depth_first_search. Use the finish_vertex event point for your postorder action, and use the tree_edge event point for the inorder action. This will be a bit tricky, since you will not want to trigger the inorder action on every call to tree_edge, only on the second call to tree_edge per vertex. 2. Use the traverse_tree function in boost/graph/tree_traits.hpp and the graph_as_tree adaptor from boost/graph/graph_as_tree.hpp. Note that these two files are undocumented and untested :( However, if you find bugs I promise to fix them :) Regards, Jeremy On Fri, 12 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> I have implemented a rooted tree structure as a BGL graph. I need to be yg-boo> able to traverse the tree from root to leaves, while doing something at yg-boo> each vertex. I need to be able to do this as inorder and postorder yg-boo> traversal. My question is if it's possible to do this with any of the yg-boo> existing algorithms in BGL. My current thinking is to implement a yg-boo> function traversal( ... ), but if there already exists an alternative, I yg-boo> would prefer to use it. yg-boo> yg-boo> yg-boo> Bj�rn ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Jeremy Siek wrote:
Hi Björn,
Here's a couple options:
1. Use depth_first_search. Use the finish_vertex event point for your postorder action, and use the tree_edge event point for the inorder action. This will be a bit tricky, since you will not want to trigger the inorder action on every call to tree_edge, only on the second call to tree_edge per vertex.
2. Use the traverse_tree function in boost/graph/tree_traits.hpp and the graph_as_tree adaptor from boost/graph/graph_as_tree.hpp. Note that these two files are undocumented and untested :( However, if you find bugs I promise to fix them :)
It looks to me like the second suggestion would be the simplest and most elegant solution. I have a couple of questions though, I can't get it to quite work. I think I'm misunderstanding the template parameters to the graph_as_tree class. What is ParentMap in this context? Let's say I have the following graph type: typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, vertex_property, edge_property> tree; How would I make a graph_as_tree object out of such a graph for use with the traverse_tree function? Thanks in advance, Björn
Hi Bj�rn, On Mon, 15 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> > 2. Use the traverse_tree function in boost/graph/tree_traits.hpp and yg-boo> > the graph_as_tree adaptor from boost/graph/graph_as_tree.hpp. Note yg-boo> > that these two files are undocumented and untested :( However, yg-boo> > if you find bugs I promise to fix them :) yg-boo> yg-boo> It looks to me like the second suggestion would be the simplest and most yg-boo> elegant solution. I have a couple of questions though, I can't get it to yg-boo> quite work. I think I'm misunderstanding the template parameters to the yg-boo> graph_as_tree class. What is ParentMap in this context? yg-boo> yg-boo> Let's say I have the following graph type: yg-boo> yg-boo> typedef boost::adjacency_list<boost::vecS, boost::vecS, yg-boo> boost::directedS, vertex_property, edge_property> tree; yg-boo> yg-boo> How would I make a graph_as_tree object out of such a graph for use with yg-boo> the traverse_tree function? The ParentMap maps a vertex to its parent vertex in the tree. So, for example, you could do the following: tree G; // fill G with vertices and edges ... typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>::vertex_descriptor vertex_t; std::vector<vertex_t> parent_vec(num_vertices(G)); typedef iterator_property_map<std::vector<vertex_t>::iterator> parent_map_t; parent_map_t parent_map(parent_vec.begin()); typedef graph_as_tree<tree, parent_map_t> real_tree_t; vertex_t root = *vertices(G).begin(); real_tree_t T(G, root, parent_map); The above call to the constructor for T fills in the parent map. One question... do you need to access parents? If not, you could fabricate a dummy property map of the right type and pass that in. Or you could hack graph_as_tree and remove all the stuff about parents. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Jeremy Siek wrote:
Hi Björn,
On Mon, 15 Jul 2002, [iso-8859-1] Björn Lindberg wrote: yg-boo> > 2. Use the traverse_tree function in boost/graph/tree_traits.hpp and yg-boo> > the graph_as_tree adaptor from boost/graph/graph_as_tree.hpp. Note yg-boo> > that these two files are undocumented and untested :( However, yg-boo> > if you find bugs I promise to fix them :) yg-boo> yg-boo> It looks to me like the second suggestion would be the simplest and most yg-boo> elegant solution. I have a couple of questions though, I can't get it to yg-boo> quite work. I think I'm misunderstanding the template parameters to the yg-boo> graph_as_tree class. What is ParentMap in this context? yg-boo> yg-boo> Let's say I have the following graph type: yg-boo> yg-boo> typedef boost::adjacency_list<boost::vecS, boost::vecS, yg-boo> boost::directedS, vertex_property, edge_property> tree; yg-boo> yg-boo> How would I make a graph_as_tree object out of such a graph for use with yg-boo> the traverse_tree function?
The ParentMap maps a vertex to its parent vertex in the tree. So, for example, you could do the following:
tree G; // fill G with vertices and edges ...
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>::vertex_descriptor vertex_t; std::vector<vertex_t> parent_vec(num_vertices(G)); typedef iterator_property_map<std::vector<vertex_t>::iterator> parent_map_t; parent_map_t parent_map(parent_vec.begin());
typedef graph_as_tree<tree, parent_map_t> real_tree_t; vertex_t root = *vertices(G).begin(); real_tree_t T(G, root, parent_map);
The above call to the constructor for T fills in the parent map.
Using the above I get a compile error: ----- phylo_tree.cpp: In function `std::string phylo::write_newicktree(phylo::tree&)': phylo_tree.cpp:63: wrong number of template arguments (1, should be 4) /home/compbio/d95-bli/include/boost/property_map.hpp:328: provided for ` template<class RandomAccessIterator, class IndexMap, class T, class R> class boost::iterator_property_map' ----- The offending line is: typedef boost::iterator_property_map<std::vector<vertex_t>::iterator> parent_map_t; It needs another template argument, namely an "IndexMap". I have to confess I'm not completely sure what that is.
One question... do you need to access parents? If not, you could fabricate a dummy property map of the right type and pass that in. Or you could hack graph_as_tree and remove all the stuff about parents.
I /think/ I will need access to the parent for some traversals. It will depend on how I implement them. Right now, I actually changed the graph type from directed to bidirectional, because I needed access to the parent. So now I can access the parent with in_edges(...) for the cost of increased memory requirements. If I get graph_as_tree to work I guess I can go back to using the directed graph type again? Björn
On Tue, 16 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> The offending line is: yg-boo> yg-boo> typedef boost::iterator_property_map<std::vector<vertex_t>::iterator> yg-boo> parent_map_t; yg-boo> yg-boo> It needs another template argument, namely an "IndexMap". I have to yg-boo> confess I'm not completely sure what that is. Oops, my documentation lied to me. I'll have to fix that too. An IndexMap maps vertices to a unique integer for each vertex, in the range [0,N), where N=num_vertices(G). If the graph has an internal property map for vertex indices, then you can get the map this way: typedef property_map<graph_t, vertex_index_t>::type index_map_t; index_map_t index_map = get(vertex_index, G); yg-boo> > One question... do you need to access parents? If not, you could fabricate yg-boo> > a dummy property map of the right type and pass that in. Or you could hack yg-boo> > graph_as_tree and remove all the stuff about parents. yg-boo> yg-boo> I /think/ I will need access to the parent for some traversals. It will yg-boo> depend on how I implement them. Right now, I actually changed the graph yg-boo> type from directed to bidirectional, because I needed access to the yg-boo> parent. So now I can access the parent with in_edges(...) for the cost yg-boo> of increased memory requirements. If I get graph_as_tree to work I guess yg-boo> I can go back to using the directed graph type again? Sure, or you can implement the parent property map using in_edges(). The graph_as_tree approach will use a bit less memory. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Jeremy Siek wrote:
On Tue, 16 Jul 2002, [iso-8859-1] Björn Lindberg wrote: yg-boo> The offending line is: yg-boo> yg-boo> typedef boost::iterator_property_map<std::vector<vertex_t>::iterator> yg-boo> parent_map_t; yg-boo> yg-boo> It needs another template argument, namely an "IndexMap". I have to yg-boo> confess I'm not completely sure what that is.
Oops, my documentation lied to me. I'll have to fix that too.
An IndexMap maps vertices to a unique integer for each vertex, in the range [0,N), where N=num_vertices(G). If the graph has an internal property map for vertex indices, then you can get the map this way:
typedef property_map<graph_t, vertex_index_t>::type index_map_t; index_map_t index_map = get(vertex_index, G);
yg-boo> > One question... do you need to access parents? If not, you could fabricate yg-boo> > a dummy property map of the right type and pass that in. Or you could hack yg-boo> > graph_as_tree and remove all the stuff about parents. yg-boo> yg-boo> I /think/ I will need access to the parent for some traversals. It will yg-boo> depend on how I implement them. Right now, I actually changed the graph yg-boo> type from directed to bidirectional, because I needed access to the yg-boo> parent. So now I can access the parent with in_edges(...) for the cost yg-boo> of increased memory requirements. If I get graph_as_tree to work I guess yg-boo> I can go back to using the directed graph type again?
Sure, or you can implement the parent property map using in_edges(). The graph_as_tree approach will use a bit less memory.
I have managed to use the traverse_tree algorithm with graph_as_tree now. I just thought of something though. When I traverse the tree, I will need access to several internal properties at the nodes and also edges in the original graph. Elsewhere I access them via property maps, but I can't see how this could be done inside a TreeVisitor. Even if I take a Tree as an argument to the TreeVisitor constructor, I won't be able to extract the property maps from the graph inside the Tree (graph_as_tree really), right? Right now I'm thinking that I should just skip graph_as_tree, and reimplement the traverse_tree algorithm directly for graphs, so that I can access all of the graph functionality. Would this be best do you think, and have I made any oversights in the reasoning above? TIA, Björn
Hi Bj�rn, On Thu, 18 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> yg-boo> I have managed to use the traverse_tree algorithm with yg-boo> graph_as_tree now. I just thought of something though. When I yg-boo> traverse the tree, I will need access to several internal yg-boo> properties at the nodes and also edges in the original graph. yg-boo> Elsewhere I access them via property maps, but I can't see how yg-boo> this could be done inside a TreeVisitor. Even if I take a Tree as yg-boo> an argument to the TreeVisitor constructor, I won't be able to yg-boo> extract the property maps from the graph inside the Tree yg-boo> (graph_as_tree really), right? Not a problem. I've added a parameter in the visitor function for the tree, and I've added property map accessors to the underlying graph for graph_as_tree. These updates are in CVS. Also, I've added an example: libs/graph/example/graph_as_tree.cpp. yg-boo> Right now I'm thinking that I should just skip graph_as_tree, and yg-boo> reimplement the traverse_tree algorithm directly for graphs, so that I yg-boo> can access all of the graph functionality. Would this be best do you yg-boo> think, and have I made any oversights in the reasoning above? The traverse_tree algorithm would be useful for DAGs. Perhaps a good name for it would be traverse_DAG. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Jeremy Siek wrote:
yg-boo> Right now I'm thinking that I should just skip graph_as_tree, and yg-boo> reimplement the traverse_tree algorithm directly for graphs, so that I yg-boo> can access all of the graph functionality. Would this be best do you yg-boo> think, and have I made any oversights in the reasoning above?
The traverse_tree algorithm would be useful for DAGs. Perhaps a good name for it would be traverse_DAG.
I have implemented a traverse_dag algorithm now. I decided it was better for me, since I needed some additional functionality beyond that of traverse_tree(). I needed the visitor to be invoked on_edge(), and also the inorder() function to be invoked "between" all recursive calls to children. ---------- template<typename DAG, typename DAGVisitor> void traverse_dag(typename boost::graph_traits<DAG>::vertex_descriptor v, DAG & g, DAGVisitor visitor) { visitor.preorder(v, g); typename boost::graph_traits<DAG>::adjacency_iterator i, end; tie(i, end) = adjacent_vertices(v, g); if (i != end) // om ej löv { traverse_dag(*i, g, visitor); visitor.on_edge(boost::edge(v, *i++, g).first, g); while (i != end) { visitor.inorder(v, g); traverse_dag(*i, g, visitor); visitor.on_edge(boost::edge(v, *i++, g).first, g); } } else visitor.inorder(v, g); visitor.postorder(v, g); } ---------- What do you think? BTW, unrelated issue: I'm going to need to keep an external property map with some tables associated with every node. Could this be realised as a vector where the vertex indices are indexing the vector of tables? Björn
Hi Bj�rn, On Fri, 19 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> yg-boo> I have implemented a traverse_dag algorithm now. I decided it was yg-boo> better for me, since I needed some additional functionality beyond yg-boo> that of traverse_tree(). I needed the visitor to be invoked yg-boo> on_edge(), and also the inorder() function to be invoked "between" yg-boo> all recursive calls to children. yg-boo> yg-boo> What do you think? Looks good. If you throw your name and an appropriate copyright on the source, I'll check it into boost CVS. Also, could I entice you to write up docs and a test for it? (If not I will) yg-boo> BTW, unrelated issue: I'm going to need to keep an external yg-boo> property map with some tables associated with every node. Could yg-boo> this be realised as a vector where the vertex indices are indexing yg-boo> the vector of tables? Yep, I do that a lot. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Hi Bj�rn, One more issue just came to mind. Even though the graph is acyclic, we still need to consider the case when a vertex has more than one in-edge. Do we want the traverse_dag algorithm to visit that node just once, or multiple times? If just once, then we need to added coloring similar to DFS. Or is what you really want a tree traversal (still formulated in terms of BGL graphs) and not a dag traversal? (a node in tree graph never has more than one in-edge). The only difference being that you would change the name to traverse_tree_graph. Cheers, Jeremy On Fri, 19 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> ---------- yg-boo> template<typename DAG, typename DAGVisitor> yg-boo> void traverse_dag(typename yg-boo> boost::graph_traits<DAG>::vertex_descriptor v, yg-boo> DAG & g, yg-boo> DAGVisitor visitor) yg-boo> { yg-boo> visitor.preorder(v, g); yg-boo> typename boost::graph_traits<DAG>::adjacency_iterator i, end; yg-boo> tie(i, end) = adjacent_vertices(v, g); yg-boo> if (i != end) // om ej l�v yg-boo> { yg-boo> traverse_dag(*i, g, visitor); yg-boo> visitor.on_edge(boost::edge(v, *i++, g).first, g); yg-boo> while (i != end) yg-boo> { yg-boo> visitor.inorder(v, g); yg-boo> traverse_dag(*i, g, visitor); yg-boo> visitor.on_edge(boost::edge(v, *i++, g).first, g); yg-boo> } yg-boo> } yg-boo> else yg-boo> visitor.inorder(v, g); yg-boo> visitor.postorder(v, g); yg-boo> } yg-boo> ---------- ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Jeremy Siek wrote:
Hi Björn,
One more issue just came to mind.
Even though the graph is acyclic, we still need to consider the case when a vertex has more than one in-edge. Do we want the traverse_dag algorithm to visit that node just once, or multiple times? If just once, then we need to added coloring similar to DFS.
Or is what you really want a tree traversal (still formulated in terms of BGL graphs) and not a dag traversal? (a node in tree graph never has more than one in-edge). The only difference being that you would change the name to traverse_tree_graph.
Hi, Jeremy I'm working exclusively with trees in my current work rather than DAGs. I think the DAG traversal is probably a good idea for DAGs, but for trees the colour is maybe an unnecessary overhead? I've made the changes you requested, and include the file as an attachment to this post. I'm not sure I feel up to writing either documentation or tests yet. If I get the time, I could look at some of the existing tests to get an idea for how you are constructing them. In any case, I feel honoured to be able to make an -- albeit minor -- contribution to the BGL. I have been thinking a bit about trees in the context of the BGL lately. For my work, I frequently need to handle leaves differently from inner nodes. I decided to implement this as a "vertex_type" internal property, which is an enum of the types {ROOT, INNER, LEAF}. The simplest example of this is using the traverse_tree_graph algoritm to print out a tree with edge weights, and where only the leaf nodes have explicit names. An example is: ((a, b, c), (d, e));. This necessitates that I have a switch-case construct in the methods of the visitor used, selecting on the node type. Do you think this is a sufficient approach? Maybe this could be done with templates instead? Björn ---------- /* Copyright 2002 Björn Lindberg */ #ifndef BOOST_TRAVERSE_TREE_GRAPH_HPP #define BOOST_TRAVERSE_TREE_GRAPH_HPP #include <boost/graph/graph_traits.hpp> namespace boost { template<typename TreeGraph, typename TreeGraphVisitor> void traverse_tree_graph(typename boost::graph_traits<TreeGraph>::vertex_descriptor v, TreeGraph & g, TreeGraphVisitor visitor) { visitor.preorder(v, g); typename boost::graph_traits<TreeGraph>::adjacency_iterator i, end; tie(i, end) = adjacent_vertices(v, g); if (i != end) // if current node is not a leaf { traverse_tree_graph(*i, g, visitor); visitor.on_edge(boost::edge(v, *i++, g).first, g); while (i != end) { visitor.inorder(v, g); traverse_tree_graph(*i, g, visitor); visitor.on_edge(boost::edge(v, *i++, g).first, g); } } else visitor.inorder(v, g); visitor.postorder(v, g); } } #endif // BOOST_TRAVERSE_TREE_GRAPH_HPP [Non-text portions of this message have been removed]
On Mon, 22 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> Hi, Jeremy yg-boo> yg-boo> I'm working exclusively with trees in my current work rather than yg-boo> DAGs. I think the DAG traversal is probably a good idea for DAGs, yg-boo> but for trees the colour is maybe an unnecessary overhead? Yep, sounds like changing the name, and leaving out the coloring is the right approach. yg-boo> I've made the changes you requested, and include the file as an yg-boo> attachment to this post. I'm not sure I feel up to writing either yg-boo> documentation or tests yet. If I get the time, I could look at yg-boo> some of the existing tests to get an idea for how you are yg-boo> constructing them. In any case, I feel honoured to be able to make yg-boo> an -- albeit minor -- contribution to the BGL. If you don't have the time, no big deal. I may get around to it :) How about we put this stuff in the boost sandbox for now. I'll go ahead and check this in. Also, do you have a sourceforge user name? If so I'll give you permissions to access the sandbox CVS. yg-boo> I have been thinking a bit about trees in the context of the BGL yg-boo> lately. For my work, I frequently need to handle leaves yg-boo> differently from inner nodes. I decided to implement this as a yg-boo> "vertex_type" internal property, which is an enum of the types yg-boo> {ROOT, INNER, LEAF}. The simplest example of this is using the yg-boo> traverse_tree_graph algoritm to print out a tree with edge yg-boo> weights, and where only the leaf nodes have explicit names. An yg-boo> example is: ((a, b, c), (d, e));. This necessitates that I have a yg-boo> switch-case construct in the methods of the visitor used, yg-boo> selecting on the node type. Do you think this is a sufficient yg-boo> approach? Maybe this could be done with templates instead? Yeah, your approach is fine. I can't think of a way to use templates for this... best save that hammer for when we really need it ;) yg-boo> yg-boo> Bj�rn yg-boo> ---------- yg-boo> yg-boo> /* Copyright 2002 Bj�rn Lindberg yg-boo> */ yg-boo> #ifndef BOOST_TRAVERSE_TREE_GRAPH_HPP yg-boo> #define BOOST_TRAVERSE_TREE_GRAPH_HPP yg-boo> yg-boo> #include <boost/graph/graph_traits.hpp> yg-boo> yg-boo> yg-boo> namespace boost yg-boo> { yg-boo> yg-boo> template<typename TreeGraph, typename TreeGraphVisitor> yg-boo> void traverse_tree_graph(typename boost::graph_traits<TreeGraph>::vertex_descriptor v, yg-boo> TreeGraph & g, yg-boo> TreeGraphVisitor visitor) yg-boo> { yg-boo> visitor.preorder(v, g); yg-boo> typename boost::graph_traits<TreeGraph>::adjacency_iterator i, end; yg-boo> tie(i, end) = adjacent_vertices(v, g); yg-boo> if (i != end) // if current node is not a leaf yg-boo> { yg-boo> traverse_tree_graph(*i, g, visitor); yg-boo> visitor.on_edge(boost::edge(v, *i++, g).first, g); yg-boo> while (i != end) yg-boo> { yg-boo> visitor.inorder(v, g); yg-boo> traverse_tree_graph(*i, g, visitor); yg-boo> visitor.on_edge(boost::edge(v, *i++, g).first, g); yg-boo> } yg-boo> } yg-boo> else yg-boo> visitor.inorder(v, g); yg-boo> visitor.postorder(v, g); yg-boo> } yg-boo> yg-boo> } yg-boo> yg-boo> #endif // BOOST_TRAVERSE_TREE_GRAPH_HPP yg-boo> yg-boo> yg-boo> [Non-text portions of this message have been removed] yg-boo> yg-boo> yg-boo> yg-boo> Info: <http://www.boost.org> yg-boo> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> yg-boo> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> yg-boo> yg-boo> yg-boo> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ yg-boo> yg-boo> ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Jeremy Siek wrote:
yg-boo> I've made the changes you requested, and include the file as an yg-boo> attachment to this post. I'm not sure I feel up to writing either yg-boo> documentation or tests yet. If I get the time, I could look at yg-boo> some of the existing tests to get an idea for how you are yg-boo> constructing them. In any case, I feel honoured to be able to make yg-boo> an -- albeit minor -- contribution to the BGL.
If you don't have the time, no big deal. I may get around to it :) How about we put this stuff in the boost sandbox for now. I'll go ahead and check this in. Also, do you have a sourceforge user name? If so I'll give you permissions to access the sandbox CVS.
I just created a Sourceforge account, username "blindberg". What is the sandbox?
yg-boo> example is: ((a, b, c), (d, e));. This necessitates that I have a yg-boo> switch-case construct in the methods of the visitor used, yg-boo> selecting on the node type. Do you think this is a sufficient yg-boo> approach? Maybe this could be done with templates instead?
Yeah, your approach is fine. I can't think of a way to use templates for this... best save that hammer for when we really need it ;)
I guess you're right here. Have you checked it in yet? I ask because I found a "bug" in the algorithm in that it might work differently from what one would expect. They it was originally written, it visited edges /after/ visiting the corresponding target node. This worked fine for myfrist purpose; to write out a tree with edge weights. However, apart from being named on_edge, which is a bit counter-intuitive, there is often a reason to want to visit an edge /before/ the target node. I decided to make both possible, so that a TreeGraphVisitor now has to implement both on_edge (before) as well as postedge (after). I'm attaching the new code to this post. Björn ---------- /* Copyright 2002 Björn Lindberg */ #ifndef BOOST_TRAVERSE_TREE_GRAPH_HPP #define BOOST_TRAVERSE_TREE_GRAPH_HPP #include <boost/graph/graph_traits.hpp> namespace boost { template<typename TreeGraph, typename TreeGraphVisitor> void traverse_tree_graph( typename boost::graph_traits<TreeGraph>::vertex_descriptor v, TreeGraph & g, TreeGraphVisitor visitor) { visitor.preorder(v, g); typename boost::graph_traits<TreeGraph>::adjacency_iterator i, end; tie(i, end) = adjacent_vertices(v, g); if (i != end) // if current node is not a leaf { visitor.on_edge(boost::edge(v, *i, g).first, g); traverse_tree_graph(*i, g, visitor); visitor.postedge(boost::edge(v, *i++, g).first, g); while (i != end) { visitor.inorder(v, g); visitor.on_edge(boost::edge(v, *i, g).first, g); traverse_tree_graph(*i, g, visitor); visitor.postedge(boost::edge(v, *i++, g).first, g); } } else visitor.inorder(v, g); visitor.postorder(v, g); } } #endif // BOOST_TRAVERSE_TREE_GRAPH_HPP [Non-text portions of this message have been removed]
Hi Bj�rn, On Thu, 25 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> yg-boo> I just created a Sourceforge account, username "blindberg". What yg-boo> is the sandbox? It is the sourceforge CVS repository that we use for collaborating on new (hopeful) boost libraries. http://sourceforge.net/projects/boost-sandbox/ yg-boo> yg-boo> I guess you're right here. Have you checked it in yet? I ask yg-boo> because I found a "bug" in the algorithm in that it might work yg-boo> differently from what one would expect. They it was originally yg-boo> written, it visited edges /after/ visiting the corresponding yg-boo> target node. This worked fine for myfrist purpose; to write out a yg-boo> tree with edge weights. However, apart from being named on_edge, yg-boo> which is a bit counter-intuitive, there is often a reason to want yg-boo> to visit an edge /before/ the target node. I decided to make both yg-boo> possible, so that a TreeGraphVisitor now has to implement both yg-boo> on_edge (before) as well as postedge (after). I've already checked in the code, so why don't you check it out and update it in CVS. That way I don't get in the way :) Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
participants (2)
-
Björn Lindberg -
Jeremy Siek