Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-14 14:36:33

On Wed, 14 Jul 2010, Eric Wolf wrote:

> 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.

OK.  Please try to contribute that as a separate algorithm so other people 
can use it as well.

>>>> 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.

The closure and reduction will always have the same number of vertices as 
the original graph, right?  They just add or remove some edges, if I 
understand correctly.  What if you didn't output a graph at all, just a 
list of edges (pairs of vertices, since the edge may not exist in the 
original graph)?  Then a user could easily ignore the list, or feed it 
back into a graph class's constructor to create a result graph.  You could 
then use named parameters and make the default be to ignore the outputs. 
If I understand correctly, though, you always need to make some kind of 
transitive closure graph internally, even if the user doesn't want it; I 
don't remember if that was just for the condensation graph or if it was a 
transitive closure of the whole input graph.  You also need an explicit 
condensation graph as temporary storage for doing the reduction, too, or 
am I mistaken?  So here are some other options I've thought of; if some of 
the stuff I wrote in this paragraph is wrong, that might change which ones 
are possible.

1 (easy). Accept an Output Iterator that will get the reduction as a list 
of edges, built using the vertices from the original graph.  Do the same 
for the closure.  Use named parameters to make both of these outputs 
ignored by default, but they can also be used to create new graphs.

2 (harder, but not because of template tricks). Create two semi-implicit 
graphs, one for the closure and one for the reduction; return both from 
your algorithm.  In this case, your graphs would only store a map from 
each vertex to its component (i.e., vertex in the condensation graph), 
which vertex is the representative of its component (for reductions), and 
the condensation graph (either its closure or reduction).  You would then 
need to do the reduction even if the user doesn't need it, but you would 
not need to store the reduction or closure of anything but the 
condensation graph.  You could also just have two variants of the 
algorithm, one that creates the condensation graph and its transitive 
closure, and another that creates both the condensation graph, its 
closure, and its reduction.  That will likely save you code still, and 
named parameters can be used to determine in one function whether the 
reduction is necessary to compute (and this can probably be done with a 
run-time if statement on a property of a template argument, without 
needing any fancy metaprogramming beyond type_traits).

Your options:

> 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 ...

I don't like this option because I don't think the reduction can be 
removed completely, since I believe you need an explicit graph for the 
reduction when you are computing (you use already filled-in parts of it to 
create other parts, right?).

> 2) Use boost::enable_if like that: (In the following ... denotes an
> ellipsis of zero or more parameters, not varargs.) ...

This option is feasible and probably easier than you think it is; named 
parameters will take care of the dispatching, so you probably won't need 
enable_if.

-- Jeremiah Willcock