Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Eric Wolf (eric_at_[hidden])
Date: 2010-07-14 00:48:23

Jeremiah Willcock <jewillco_at_[hidden]> 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