Jeremiah Willcock <jewillco@osl.iu.edu> writes: Dear Jeremiah,
I looked through your tarball. Here are some comments:
Why are you computing the transitive closure explicitly when it is not part of the algorithm's documented output? It there a reason that you can't use the SCC structure (and the connections between them) directly to compute the reduction without storing the full closure?
You mean the edge_in_closure adjacency matrix in transitive_reduction_for_dag? It's part of the algorithm to have the reflexive transitive closure stored. I have no idea how I could generate the same behavior in the decision logic ( the "if( not edge_in_closure[i][*it] )" line ) without it.
I guess you could do a BFS, but if the traditional algorithm uses an explicit closure you probably should too. You might want to mention the quadratic memory usage though. It would be better to have an explicit adjacency_matrix graph for the closure. Is there a reason you're not using the current transitive_closure algorithm in BGL?
I will modify transitive_closure from Vladimir Prus and use successor sets. This will give better time complexity and better memory usage.
Why are there functions that do the transitive closure as well as the reduction? Is having both of them a common use case? It appears that there is a lot of redundant code between the reduction-with-closure and reduction-only functions.
It's the same algorithm. The algorithm for computing the closure and the reduction is essentially the same. So you could have the other one for free if you generate one of them. I doubt that it is a common use case, I admit, but I thought one should have the possibility to get both in one run, if its for free. So the reduction-with-closure and reduction-only functions are essentially duplicates of each other.
OK. Is there a way to factor out the common code?
** long lines below ** Several ways to accomplish that come to my mind, but I'm unsure which route to go and ask you for some advice. 1) Define a Graph type which absorbs all add_vertex and add_edge operations like /dev/null in unix, then write one implementation function like namespace detail { template < typename Graph, typename GraphTC, typename G_to_TC_map, typename GraphTR, typename G_to_TR_map, typename VertexIndexMap > void transitive_reduction_and_closure( Graph g, GraphTC tc, G_to_TC_map g_to_tc_map, GraphTR tr, G_to_TR_map g_to_tr_map, VertexIndexMap vertex_index_map) { \\impl } } and two interface functions template < typename Graph, typename GraphTC, typename G_to_TC_map, typename VertexIndexMap > void transitive_closure( Graph g, GraphTC tc, G_to_TC_map g_to_tc_map, VertexIndexMap vertex_index_map) { detail::absorbing_graph ag; transitive_reduction_and_closure( g, tc, g_to_tc_map, ag, identity_property_map() ); } transitive_reduction is analog. Disadvantages: strange type with empty functions needs to be thrown away by compiler optimization and its not clear to me if such a type would meet the requirements of the Graph concept as it clearly states that add_edge should return a vertex_descriptor for the inserted vertex. Returning null_vertex() as no vertex got inserted is splitting hairs and not in the purpose of the Graph concept? 2) Use boost::enable_if like that: (In the following ... denotes an ellipsis of zero or more parameters, not varargs.) namespace detail { struct DONT_COMPUTE_TR {}; struct DONT_COMPUTE_TC {}; template < ..., GraphTC > void construct_tc_from_successor_set( ..., GraphTC tc, ... boost::enable_if< boost::is_same< GraphTC, detail::DONT_COMPUTE_TC >::type * = 0 ) { //dont do anything, as we shall not construct an TC } template < ..., GraphTC > void construct_tc_from_successor_set( ..., GraphTC tc, ... boost::disable_if< boost::is_same< GraphTC, detail::DONT_COMPUTE_TC >::type * = 0 ) { ... //compute the transitive_closure and build it up in tc } //transitive_reduction is analog template < typename Graph, typename GraphTC, typename G_to_TC_map, typename GraphTR, typename G_to_TR_map, typename VertexIndexMap > void transitive_reduction_and_closure( Graph g, GraphTC tc, G_to_TC_map g_to_tc_map, GraphTR tr, G_to_TR_map g_to_tr_map, VertexIndexMap vertex_index_map) { \\impl construct_tc_from_successor_set( ... ); construct_tr( ... ); } } template < typename Graph, typename GraphTC, typename G_to_TC_map, typename VertexIndexMap > void transitive_closure( Graph g, GraphTC tc, G_to_TC_map g_to_tc_map, VertexIndexMap vertex_index_map) { detail::transitive_reduction_and_closure( g, tc, g_to_tc_map, detail::DONT_COMPUTE_TR(), identity_property_map() ); } transitive_reduction is analog. advantages: - unused code is not compiled into the executable as SFINAE prevents this disadvantages: - pulls in boost/utility/enable_if.hpp and boost/type_traits/is_same.hpp - the transitive reduction cannot be computed from the successor set, so there would be a builder for the transitive reduction of the _condensation graph_, which I would implemet with a template class and a template class specializiation with enable_if like above. 3) a suggestion from you? As I don't know your suggestion yet, at the moment I vote for 2) or something similar. Is there a “template pattern“ which I could use? To me 2) appears a little bit naive but could it work? Yours, Eric