Subject: Re: [boost] [SoC] BGL project idea
From: Eric Wolf (eric_at_[hidden])
Date: 2010-11-03 10:01:07
Jeremiah Willcock <jewillco_at_[hidden]> writes:
> On Sat, 7 Aug 2010, Eric Wolf wrote:
>> Jeremiah Willcock <jewillco_at_[hidden]> writes:
>>> Are you still working on this? Is there any help you need from me?
>>> I've been busy since you sent the email so I didn't respond.
>> Yes. I'm still working on it. I think the user should be able to select
>> which output he wants: A changed mutable graph, edges streamed to some
>> output iterator or a proxy object behaving like a graph.
>> This time I would like to send you the code before I write the
>> documentation, so I don't waste so much work.
>> But I will be unable to do something until thursday, as I'm on a
> Are you still interested in submitting your transitive closure and
> reduction code?
Here is some stuff, I would be really thankful if you could take a look
at. Especially on the usage of boost::mpl and how the tags are done.
The idea is, that only the parts of the algorithm are compiled in, which
are needed. But I am not sure if it isn't overkill for such a small
Okay the general idea is as follows: You call one of the functions
transitive_*_stream or transitive_*_mutgr which provide the right data
structure for what you want via a tag mechanism. Then the central
algorithm is called, which does the calculation of the strong
components, the condensation graph and the transitive reduction and/or
the transitive closure of the condensation graph depending on the tag of
the data structure. And after that functions are called, which either
create an edge list of the transitive reduction/transitive closure or
which modify mutable graphs depending on which interface function you
That way it should be possible to add something like a filtered_graph
interface we wrote about earlier.
I didn' realize the idea of a kind of a filtered_graph. The properties a
graph can carry give me a headache and I did not understand how to
Does that stuff go in the right direction?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk