
Boost : 
Subject: Re: [boost] [SoC] BGL project idea
From: Eric Wolf (eric_at_[hidden])
Date: 20100714 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 reductionwithclosure
>>> and reductiononly 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 reductionwithclosure and
>> reductiononly 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk