Hi Elisha,

On Jul 6, 2005, at 6:12 PM, Elisha Berns wrote:

...

Ideally I do a topological sort to find the most dependent vertex (if that makes sense) which then becomes the root of an n-ary tree, and then build the tree from that vertex recursively finding the out-edges of child vertices. All that works provided the graph is actually a DAG. But sometimes it isn't because there can be small cycles(?) inside

Doug, Thanks for the reply. As I am still relatively a novice at graph algorithms I am still trying to decipher parts of your response. Regarding your suggestion to modify the topological sort code, it looks like only the topological sort visitor needs modification, and seemingly just removing the exception throwing. Anyways this is what I came up with, best_case_topological_sort method that just stores the back edges should they be needed later. It looks like this (comments please if this is what you intended): Thanks, #ifndef BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_HPP #define BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_HPP #include <list> #include #include #include #include namespace boost { // Best case topological sort visitor // // This visitor merely writes the linear ordering into an // OutputIterator. The OutputIterator could be something like an // ostream_iterator, or it could be a back/front_insert_iterator. // Note that if it is a back_insert_iterator, the recorded order is // the reverse topological order. On the other hand, if it is a // front_insert_iterator, the recorded order is the topological // order. // template <typename OutputIterator> struct best_case_topo_sort_visitor : public dfs_visitor<> { best_case_topo_sort_visitor(OutputIterator _iter) : m_iter(_iter) { } template void back_edge(const Edge& u, Graph&) { m_back_edges.push_back(u); } template void finish_vertex(const Vertex& u, Graph&) { *m_iter++ = u; } OutputIterator m_iter; typedef std::list<Edge> EdgeList; EdgeList m_back_edges; }; // Topological Sort // // The topological sort algorithm creates a linear ordering // of the vertices such that if edge (u,v) appears in the graph, // then u comes before v in the ordering. The graph must // be a directed acyclic graph (DAG). The implementation // consists mainly of a call to depth-first search. // template void best_case_topological_sort(VertexListGraph& g, OutputIterator result, const bgl_named_params& params) { typedef best_case_topo_sort_visitor<OutputIterator> TopoVisitor; depth_first_search(g, params.visitor(TopoVisitor(result))); } template void best_case_topological_sort(VertexListGraph& g, OutputIterator result) { best_case_topological_sort(g, result, bgl_named_params(0)); // bogus } } // namespace boost #endif /*BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_H*/ the

...

graph where one vertex refers to its parent's parent's vertex. So everything in the graph can be suitable for a DAG except for this small set of vertices that becomes self-referential.

One thing I've done in the past was to run the strong_components algorithm first to detect all of the strongly-connected components (SCCs). Then, I built another graph with one vertex for each SCC and, finally, run the topological sort on this new graph.

However, I think my problem was a little different from yours, because I expected there to be many fewer SCCs than vertices. Since you mentioned that you have only a few, small cycles, there are other options. The first option is to copy most of the topological_sort code but ignore back edges. Another alternative is to use a filtered_graph<> to filter out any back edges.

Doug

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Hi Elisha,

On Jul 6, 2005, at 6:12 PM, Elisha Berns wrote:

...

Ideally I do a topological sort to find the most dependent vertex (if that makes sense) which then becomes the root of an n-ary tree, and then build the tree from that vertex recursively finding the out-edges of child vertices. All that works provided the graph is actually a DAG. But sometimes it isn't because there can be small cycles(?) inside

What test is there to determine whether an edge is a back-edge that can be used inside a filter predicate of the filter_graph? Thanks, Elisha the

...

graph where one vertex refers to its parent's parent's vertex. So everything in the graph can be suitable for a DAG except for this small set of vertices that becomes self-referential.

One thing I've done in the past was to run the strong_components algorithm first to detect all of the strongly-connected components (SCCs). Then, I built another graph with one vertex for each SCC and, finally, run the topological sort on this new graph.

However, I think my problem was a little different from yours, because I expected there to be many fewer SCCs than vertices. Since you mentioned that you have only a few, small cycles, there are other options. The first option is to copy most of the topological_sort code but ignore back edges. Another alternative is to use a filtered_graph<> to filter out any back edges.

Doug

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Thanks again for a reply. Excuse my confusion and lack of understanding, but I don't yet understand what you explain below: "You can store a copy of the color map in the edge filter predicate" I think I get this, is this what you mean (here are the definitions for this part): typedef adjacency_list < vecS, vecS, directedS, property< vertex_color_t, default_color_type, property< vertex_type_t, VertexType > >

Graph;

typedef property_map::type VertexColorMap; template struct valid_edge { valid_edge() { } valid_edge(Graph& graph, VertexColorMap color_map) : m_graph(graph), m_color_map(color_map) { } template <typename Edge> bool operator()(const Edge& e) const { return ( Color::gray() != get(m_color_map, target(e, m_graph)) ); } VertexColorMap m_color_map; Graph& m_graph; }; And the code to setup the above: valid_edge filter(m_graph, get(vertex_color, m_graph)); filtered_graph > fg(m_graph, filter); But the next part of what you write isn't clear: "pass the same color map to depth_first_search; then you filter out any edges whose targets are gray" So which graph gets sorted with depth_first_search? The filter graph I presume? But I thought the constructor for filter_graph will call the predicate function for every edge without having to do a depth_first_search??? Also, if the predicate has only a copy of the vertex color map then how are the results from depth_first_search going to be reflected in the predicate object? Anyways, those last two steps don't make sense yet. Thanks for a clarification. Yours, Elisha

...

What test is there to determine whether an edge is a back-edge that can be used inside a filter predicate of the filter_graph?

You can use the (vertex) color map to determine if an edge is a back edge. You can store a copy of the color map in the edge filter predicate, and pass the same color map to depth_first_search; then you filter out any edges whose targets are gray.

Doug

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Hi Doug, Thanks for the reply, however long it took. I realize you must be swamped with questions and work. The reply is still very useful. The only thing that I haven't determined yet is whether the results will be different for the two methods: 1) a straight depth_first_search that just ignores any back edges (and doesn't throw not_a_dag) and 2) using a filtered graph approach. But I'll test it all and see. Forgive my seeming thick on this matter, but still, there is some mystery to me as to why the filtered graph approach will work at all. So I just want to get clear on who does what to whom here, and why. So lets start at the top, so that hopefully you can spot immediately the hole in my (mis)understanding here: 1) Construct a graph that is mostly, predominately, a DAG. 2) This graph doesn't have any valid color properties yet, because is hasn't been traversed in any way (this is the point that seemingly is hanging me up). 3) Construct an edge filter that will eliminate edges that have the color 'gray'. 4) Construct a filtered_graph using the above edge filter and a copy of the color map from the 'original' graph that isn't quite a DAG. 5) Run a depth first search on the filtered graph and voila the resulting filtered graph will now be a DAG in depth first search order. So where do the vertices get colored gray? Presumably during the depth_first_search operation, right? Does that mean depth_first_search first colors the vertices, then calls the filtered_graph's edge predicate? And then the filtered_graph eliminates the gray edge? Something's missing, but I can't quite articulate it. On the other hand, if you wrote that you first run a depth_first_search that ignores back edges on the graph in order to first color the vertices, that would be clear to me. And then of course you run that graph with its initialized color_map through the filtered_graph using the edge predicate that eliminates all edges with color gray. That would make perfect sense to my small mind! But this way, I don't get where the vertices get 'colored' and how they then get 'eliminated'. Thanks for your patience and clarity here. Yours, Elisha

Hello,

My apologies for the long delay in replying; I hope it's still useful

:(

On Jul 8, 2005, at 2:00 PM, Elisha Berns wrote:

...

Thanks again for a reply. Excuse my confusion and lack of understanding, but I don't yet understand what you explain below:

"You can store a copy of the color map in the edge filter predicate"

I think I get this, is this what you mean (here are the definitions

for

...

this part):

typedef adjacency_list < vecS, vecS, directedS, property< vertex_color_t, default_color_type, property< vertex_type_t, VertexType > >

...

Graph;

typedef property_map::type VertexColorMap;

template struct valid_edge { valid_edge() { } valid_edge(Graph& graph, VertexColorMap color_map) : m_graph(graph), m_color_map(color_map) { } template <typename Edge> bool operator()(const Edge& e) const { return ( Color::gray() != get(m_color_map, target(e, m_graph)) ); } VertexColorMap m_color_map; Graph& m_graph; };

And the code to setup the above:

valid_edge filter(m_graph, get(vertex_color, m_graph));

filtered_graph > fg(m_graph, filter);

Yes, that's exactly what I meant.

...

But the next part of what you write isn't clear:

"pass the same color map to depth_first_search; then you filter out any edges whose targets are gray"

So which graph gets sorted with depth_first_search? The filter graph I presume?

Yes, the filtered_graph.

...

But I thought the constructor for filter_graph will call the predicate function for every edge without having to do a depth_first_search???

When depth_first_search asks the filtered_graph to list the edges it knows about, filtered_graph will first ask the predicate which edges it should make visible.

...

Also, if the predicate has only a copy of the vertex color map then how are the results from depth_first_search going to be reflected in the predicate object?

Even though you have multiple copies of the color map returned by get(vertex_color, m_graph) (one in the edge predicate and one that's passed to depth_first_search), they all refer to the same information, e.g., the color value stored on the vertices of the graph nodes.

Doug

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Hi Doug, Thanks doubly for the clear explanation. Finally the pieces are making (more) sense here. Just one question:

Here's the first minor issue. At this point, we should initialize the color map with all white vertices.

Hi Elisha,

On Jul 25, 2005, at 12:35 PM, Elisha Berns wrote:

...

So lets start at the top, so that hopefully you can spot immediately the hole in my (mis)understanding here:

1) Construct a graph that is mostly, predominately, a DAG. 2) This graph doesn't have any valid color properties yet, because is hasn't been traversed in any way (this is the point that seemingly is hanging me up).

Here's the first minor issue. At this point, we should initialize the color map with all white vertices.

...

3) Construct an edge filter that will eliminate edges that have the color 'gray'.

We want to eliminate edges whose target vertex has the color gray.

...

4) Construct a filtered_graph using the above edge filter and a copy of the color map from the 'original' graph that isn't quite a DAG. 5) Run a depth first search on the filtered graph and voila the resulting filtered graph will now be a DAG in depth first search order.

So where do the vertices get colored gray? Presumably during the depth_first_search operation, right? Does that mean depth_first_search first colors the vertices, then calls the filtered_graph's edge predicate?

Yes. Check out the DFS-VISIT pseudo in the documentation here:

http://www.boost.org/libs/graph/doc/depth_first_search.html

As soon as DFS sees a vertex "u" for the first time (so u is white), it colors it gray in the property map, then visits its out-edges. The filtered_graph applies the filter predicate on-the-fly, so as we're stepping through the out-edge list of the underlying graph, it's filtering out any edges (u, v) such that v is colored gray.

It's like we took the loop from DFS-VISIT that looks like this:

for each v in Adj[u] // do something

and made it:

for each v in Adj[u] if color[v] != gray // do something

...

And then the filtered_graph eliminates the gray edge? Something's missing, but I can't quite articulate it.

I'm guessing that you're expecting that the edge filter predicate is applied once, when the filtered_graph is constructed, instead of lazily as we iterate through the out-edges for each vertex. It's very likely that our documentation doesn't make this abundantly clear.

...

On the other hand, if you wrote that you first run a depth_first_search that ignores back edges on the graph in order to first color the vertices, that would be clear to me. And then of course you run

I assume you mean to say that it is necessary to call 'put(...)' on this property map for every vertex that is in the graph to initialize each vertex's color to white? Otherwise it won't happen...? Elisha that

...

graph with its initialized color_map through the filtered_graph using the edge predicate that eliminates all edges with color gray. That would make perfect sense to my small mind!

We might get stuck if we did this, because all vertices in the graph could end up colored black by the depth_first_search and we'd do nothing on the second pass.

Doug

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users