[SoC] BGL project idea

Hi, I am a Computer Science student hoping to contribute to Boost for this year's summer of code. I had a few questions regarding the BGL project idea (https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Graph) for SOC 2010. 1. I can think of only a few places where the suggested algorithms will be used. Does the community think that these algorithms are used frequently enough to put them in a library? How important does the community consider this project? 2. Will the project proposal be expected to include the API design? Thanks and Regards Gautam

I am a Computer Science student hoping to contribute to Boost for this year's summer of code. I had a few questions regarding the BGL project idea (https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Graph) for SOC 2010.
1. I can think of only a few places where the suggested algorithms will be used. Does the community think that these algorithms are used frequently enough to put them in a library? How important does the community consider this project?
A topology-generating and testing functions can be used for testing, among other things. The connectives are intended to make the BGL a little more algebraically complete. Basically, we're just looking to make the BGL a little more feature complete. 2. Will the project proposal be expected to include the API design? The project necessitates API design :) You would be working on a library. Andrew Sutton andrew.n.sutton@gmail.com

On Fri, Mar 12, 2010 at 2:30 AM, Andrew Sutton <andrew.n.sutton@gmail.com>wrote:
2. Will the project proposal be expected to include the API design?
The project necessitates API design :) You would be working on a library.
I know that doing the project will obviously involve API design :). I just wanted to know whether it's something that should be taken up at this stage and a complete initial design put in the project proposal.

The project necessitates API design :) You would be working on a library.
I know that doing the project will obviously involve API design :). I just wanted to know whether it's something that should be taken up at this stage and a complete initial design put in the project proposal.
You might discuss some requirements of the API in your proposal (kinds of parameters you might need to pass), but I wouldn't be too specific about anything. Andrew Sutton andrew.n.sutton@gmail.com

On 03/11/2010 08:19 PM, Gautam Sewani wrote:
Hi, I am a Computer Science student hoping to contribute to Boost for this year's summer of code. I had a few questions regarding the BGL project idea (https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Graph) for SOC 2010.
1. I can think of only a few places where the suggested algorithms will be used. Does the community think that these algorithms are used frequently enough to put them in a library? How important does the community consider this project?
I'm personally interested in _tests_ for different topologies, e.g. whether a given graph (or a filtered one) describes a path or a cycle, etc. I'm using those for different tasks in my current project. Thus I'd prefer the library to be able to test those, too. Matthias Walter

I'm personally interested in _tests_ for different topologies, e.g. whether a given graph (or a filtered one) describes a path or a cycle, etc. I'm using those for different tasks in my current project. Thus I'd prefer the library to be able to test those, too.
It's in description. The is_star, is_cycle has some interesting design tradeoffs (isomorphism, labelling, etc.). Andrew Sutton andrew.n.sutton@gmail.com

Hi there, Gautam Sewani <gautamcool88@gmail.com> writes:
Hi, I am a Computer Science student hoping to contribute to Boost for this year's summer of code. I had a few questions regarding the BGL project idea (https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Graph) for SOC 2010.
I read throught the posted url and I'm a little astonished about "Closures and Reductions - Implement a suite qof generic graph algorithms that computer closures and reductions on graphs. The BGL already contains a transitive_closure algorithm, but not (yet) a transitive_reduction. Other kinds of computable closures and reductions include reflexive, symmetric, and congruence. This project can also include predicates to test whether or not a graph exhibits these properties (e.g., is_symmetric)." After all there is a transitive_reduction.hpp in boost BGL. Ok it is not documented at the moment. And there is https://svn.boost.org/trac/boost/ticket/3821 The algorithm in this ticket is not as efficient as the algorithm, which is already there in the transitive_closure.hpp. As I wrote transitive_reduction.hpp in the form in this ticket, I noticed, that besides adding the input and output parameters and reconstructing the transitive reduction of the graph from the transitive reduction of the structure graph, it is not much afford to add transitive reduction if one has transitive closure. (Why is the algorithm included in transitive_reduction.hpp not as efficient as the algorithm included in transitive_closure.hpp? The algorithm in transitive_closure.hpp uses successor sets there transitive_reduction.hpp uses a adjacency matrix for the core algorithm.) I see that there is much more to the proposed project, than to add a transitive reduction, but it is not true that there is none. Yours sincerely, Eric

After all there is a transitive_reduction.hpp in boost BGL. Ok it is not documented at the moment.
It was an oversight. I copied over a number of proposals from last year and forgot to update the closures project. I've updated the wiki.
And there is https://svn.boost.org/trac/boost/ticket/3821
Should I integrate those tests and documentation? Will they apply to the current version of transitive_reduction? Andrew Sutton andrew.n.sutton@gmail.com

Hi Andrew, Andrew Sutton <andrew.n.sutton@gmail.com> writes:
And there is https://svn.boost.org/trac/boost/ticket/3821
Should I integrate those tests and documentation? Will they apply to the current version of transitive_reduction?
No. They fit the transitive_reduction.hpp which is included in the tarball. Sorry. Eric

Should I integrate those tests and documentation? Will they apply to the current version of transitive_reduction?
No. They fit the transitive_reduction.hpp which is included in the tarball. Sorry.
Hi Eric, I'm a little confused about the Trac ticket and its relation to what's in Boost. Is there anything in the Trac ticket that could or should be in trunk? Andrew Sutton andrew.n.sutton@gmail.com

Andrew Sutton <andrew.n.sutton@gmail.com> writes:
Should I integrate those tests and documentation? Will they apply to the current version of transitive_reduction?
No. They fit the transitive_reduction.hpp which is included in the tarball. Sorry.
Hi Eric,
I'm a little confused about the Trac ticket and its relation to what's in Boost. Is there anything in the Trac ticket that could or should be in trunk?
Hmm. I don't understand the question. The file transitive_reduction.hpp which is in, for example, boost 1.41, was a first try on the transitive reduction. (The algorithm there works only for DAGs.) I simply posted the code on this mailing list and somebody else added it to boost. ( I don't know who. ) The code included in the Trac Ticket is a far improved version and should replace the actual transitive_reduction.hpp. It is still far from perfect (or maybe even good), but it is an improvement and it has documentation. I don't know which rules apply to code in order to decide, wether it should be contained in trunk. Maybe you should ask Jeremiah Willcock. He is the maintainer of BGL, isn't he? So maybe he should decide, wether the code is added? Yours sincerely, Eric

On Sat, 20 Mar 2010, Eric Wolf wrote:
Andrew Sutton <andrew.n.sutton@gmail.com> writes:
Should I integrate those tests and documentation? Will they apply to the current version of transitive_reduction?
No. They fit the transitive_reduction.hpp which is included in the tarball. Sorry.
Hi Eric,
I'm a little confused about the Trac ticket and its relation to what's in Boost. Is there anything in the Trac ticket that could or should be in trunk?
Hmm. I don't understand the question.
The file transitive_reduction.hpp which is in, for example, boost 1.41, was a first try on the transitive reduction. (The algorithm there works only for DAGs.) I simply posted the code on this mailing list and somebody else added it to boost. ( I don't know who. )
The code included in the Trac Ticket is a far improved version and should replace the actual transitive_reduction.hpp. It is still far from perfect (or maybe even good), but it is an improvement and it has documentation.
I should look at it -- I haven't so far.
I don't know which rules apply to code in order to decide, wether it should be contained in trunk.
Things that people submit normally go in if they're good quality and have documentation and everything.
Maybe you should ask Jeremiah Willcock. He is the maintainer of BGL, isn't he? So maybe he should decide, wether the code is added?
Both Andrew and I are maintainers, so either of us can look through your code and decide what to do with it. -- Jeremiah Willcock

Jeremiah Willcock <jewillco@osl.iu.edu> writes:
Things that people submit normally go in if they're good quality and have documentation and everything.
If you want me to improve something, write me an e-mail :)
Maybe you should ask Jeremiah Willcock. He is the maintainer of BGL, isn't he? So maybe he should decide, wether the code is added?
Both Andrew and I are maintainers, so either of us can look through your code and decide what to do with it.
Okay. Yours sincerely, Eric

Things that people submit normally go in if they're good quality and have documentation and everything.
If you want me to improve something, write me an e-mail :)
Maybe you should ask Jeremiah Willcock. He is the maintainer of BGL, isn't he? So maybe he should decide, wether the code is added?
Both Andrew and I are maintainers, so either of us can look through your code and decide what to do with it.
Hi Eric, I've got a lot of things on my plate this week (including working on another BGL algorithm). Hopefully, I'll have some time on Friday and next week to go over the new version. If it looks good, I'll commit it. Does that sound reasonable? Andrew Sutton andrew.n.sutton@gmail.com

I don't know which rules apply to code in order to decide, wether it should be contained in trunk.
I looked through your tarball. Here are some comments: There are a lot of tabs in the source file; they are not allowed in Boost code. The copyright and license info at the top of the file are also incorrect; the old code in boost/graph/transitive_reduction.hpp has the correct text. The coding style is different from the rest of the BGL code; we normally use K&R style. You might want to remove the debugging code from the library itself. Should edge_in_closure be a boost::multi_array or a boost::adjacency_matrix to be clearer on what it's being used for? 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? 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. I believe strong_components actually returns a topologically sorted list of the components (I do not remember which order the sort is in), so you may not need to do that separately on the DAG of components. Why are you using a vector of vectors as that adjacency list structure for CG and the other temporary graphs? Why not boost::adjacency_list? Line 243 is missing an "e" on the end of "transitive". The documentation style is too informal compared to the rest of the BGL reference documentation. The function signatures also need to be signatures at the top of the documentation file -- that is likely to be one of the first things a user will be looking for when they pull up the documentation page. I do appreciate that you have figures in there; it might be better if they were a bit smaller, though, and you put each grouping (graph, trans. closure, trans. reduction) in a single horizontal line. In the examples and tests, "exspectation" should be "expectation" in several variable names; there are some spelling errors in the comments too. For brevity, you might also want to use the graph constructors that take a sequence of pairs that becomes the edge list of the graph. -- Jeremiah Willcock

Hi Jeremiah, first of all: thanks for the feedback! I'll work on your comments in the next weeks (perhaps months). Some I answer here. Jeremiah Willcock <jewillco@osl.iu.edu> writes:
I don't know which rules apply to code in order to decide, wether it should be contained in trunk.
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.
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.
I believe strong_components actually returns a topologically sorted list of the components (I do not remember which order the sort is in), so you may not need to do that separately on the DAG of components.
I'll have to investigate that ... but if it's not part of the documented behavior it would be not "right" to rely on it, wouldn't it?
In the examples and tests, "exspectation" should be "expectation" in several variable names; there are some spelling errors in the comments too.
I'm not a native speaker, so I have to search for spell checking software. (aspell or ispell, wether one of them can do unicode) Yours sincerely, Eric

On Tue, 23 Mar 2010, Eric Wolf wrote:
Hi Jeremiah,
first of all: thanks for the feedback! I'll work on your comments in the next weeks (perhaps months). Some I answer here.
Jeremiah Willcock <jewillco@osl.iu.edu> writes:
I don't know which rules apply to code in order to decide, wether it should be contained in trunk.
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?
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?
I believe strong_components actually returns a topologically sorted list of the components (I do not remember which order the sort is in), so you may not need to do that separately on the DAG of components.
I'll have to investigate that ... but if it's not part of the documented behavior it would be not "right" to rely on it, wouldn't it?
I guess not -- ftp://db.stanford.edu/pub/cstr/reports/cs/tr/75/508/CS-TR-75-508.pdf suggests that Tarjan's algorithm does prodice the components in order, but that's a variant that may not be the same as the BGL one. -- Jeremiah Willcock

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

On Wed, 14 Jul 2010, Eric Wolf wrote:
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.
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

Dear Jeremiah, thanks for the fast response. 1) I'll give some general clarifications on the algorithm, then 2) I want to talk (read/write) about how to implement it and your very valueable suggestions. 1) First of all some clarification (i'm not sure you need them though :) ) Jeremiah Willcock <jewillco@osl.iu.edu> writes:
On Wed, 14 Jul 2010, Eric Wolf wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> writes:
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? Is there a reason you're not using the current transitive_closure algorithm in BGL?
An already computed transitive closure can't be used, as there is a need to compute it in all cases, as some times it must be checked, whether an edge is already in the to be computed closure.
I will modify transitive_closure from Vladimir Prus and use successor sets. This will give better time complexity and better memory usage.
So the transitive closure is stored in the successor sets in what I imagine to be the next version of transitive_reduction.hpp. No explicit transitive closure needed any more. I cite some text, which would came later in your email:
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;
Correct. Thats what I will use successor sets for in my next imagined version.
I don't remember if that was just for the condensation graph or if it was a transitive closure of the whole input graph.
Just for the condensation graph.
You also need an explicit condensation graph as temporary storage for doing the reduction, too, or am I mistaken?
I'm not sure about this. The transitive_reduction of the condensation graph is only touched to insert edges. It is not read in the “core“ algorithm. It is needed, to construct the transitive_reduction of the original graph I think. (If the reduction of the original graph is stored as an explicit graph, or if I write vertex pairs to an output iterator isn't important though.) 2) Now I answer the other points in your response:
OK. Please try to contribute that as a separate algorithm so other people can use it as well.
Ehh ... I don't understand, what you mean. A separate algorithm to the previous version? Who would want the previous version (of transitive_reduction)?
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?
yes
They just add or remove some edges, if I understand correctly.
yes
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.
That's a great idea. But I couldn't get the grasp of bgl named parameters until now. I thought bgl would use the boost::parameter library, but in my perception the documentation and what's done in named_parameters.hpp don't fit.
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?
The reduction could be easily written to an output iterator I imagine, but the computation of the transitive closure of the condensation graph must be done in all cases and stored somehow. Now in the successor sets.
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.
Even it the reduction is not used or wanted by the user, it still would be computed from the reduction of the condensation graph. But maybe it is an accepable annoyance?
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).
And a two functions to construct the reduction and the closure from the cond.gr.rd. and the cond.gr.cl. and the mappings. Yeah, thats a possible way.
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?).
Nope. The reduction of the condensation graph is only written, not read in the core algorithm. It gets read if one tries to build the transitive reduction of the whole graph. But I don't like that option, too. It is ugly.
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.
If you think it is feasible, then I would like to take that route. One remedy still remains in my perception. If the user doesn't want the transitive reduction, an unused local variable remains in the main implementation function ... Can that be removed somehow by fancy template stuff? What's your favorite choice? Yours, Eric

On Thu, 15 Jul 2010, Eric Wolf wrote:
Dear Jeremiah,
thanks for the fast response.
1) I'll give some general clarifications on the algorithm, then 2) I want to talk (read/write) about how to implement it and your very valueable suggestions.
1) First of all some clarification (i'm not sure you need them though :) )
Jeremiah Willcock <jewillco@osl.iu.edu> writes:
On Wed, 14 Jul 2010, Eric Wolf wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> writes:
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? Is there a reason you're not using the current transitive_closure algorithm in BGL?
An already computed transitive closure can't be used, as there is a need to compute it in all cases, as some times it must be checked, whether an edge is already in the to be computed closure.
I don't understand what you're saying, and it seems to be contradicted by your next part about using Vladimir's transitive_closure code.
I will modify transitive_closure from Vladimir Prus and use successor sets. This will give better time complexity and better memory usage.
So the transitive closure is stored in the successor sets in what I imagine to be the next version of transitive_reduction.hpp. No explicit transitive closure needed any more.
That's just a transitive closure stored as an adjacency list, though, right? Why not just use that rather than an adjacency_matrix, or make it configurable by the user (since looking up whether edges are in the closure is faster with a matrix when the closure is dense).
I cite some text, which would came later in your email:
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;
Correct. Thats what I will use successor sets for in my next imagined version.
OK.
I don't remember if that was just for the condensation graph or if it was a transitive closure of the whole input graph.
Just for the condensation graph.
That's what I thought. BTW, did you see <boost/graph/create_condensation_graph.hpp>? Is anything in there useful to you?
You also need an explicit condensation graph as temporary storage for doing the reduction, too, or am I mistaken?
I'm not sure about this. The transitive_reduction of the condensation graph is only touched to insert edges. It is not read in the “core“ algorithm. It is needed, to construct the transitive_reduction of the original graph I think. (If the reduction of the original graph is stored as an explicit graph, or if I write vertex pairs to an output iterator isn't important though.)
So you don't need to read back any of the transitive reduction of the condensation graph as part of creating it?
2) Now I answer the other points in your response:
OK. Please try to contribute that as a separate algorithm so other people can use it as well.
Ehh ... I don't understand, what you mean. A separate algorithm to the previous version? Who would want the previous version (of transitive_reduction)?
I think that was referring to the successor-set-based transitive closure algorithm, but check my previous email to be sure.
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?
yes
They just add or remove some edges, if I understand correctly.
yes
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.
That's a great idea. But I couldn't get the grasp of bgl named parameters until now. I thought bgl would use the boost::parameter library, but in my perception the documentation and what's done in named_parameters.hpp don't fit.
I think BGL predates Boost.Parameter. In new algorithms, what we do is convert the BGL named parameter structure to a Boost.Parameter one and then use Boost.Parameter (with a bunch of BGL-specific wrapper functions) to work with it. Look at <boost/graph/random_spanning_tree.hpp> and the trunk/1.44 version of <boost/graph/astar_search.hpp> for examples.
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?
The reduction could be easily written to an output iterator I imagine, but the computation of the transitive closure of the condensation graph must be done in all cases and stored somehow. Now in the successor sets.
OK.
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.
Even it the reduction is not used or wanted by the user, it still would be computed from the reduction of the condensation graph. But maybe it is an accepable annoyance?
I thought you could save some time by computing only the closure; isn't a reduction on even the condensation graph extra work to compute? Remember, too, you can probably assume that code like: if (!boost::is_same<ReductionOutput, dummy_iterator>::value) { compute reduction } would be handled well by compilers.
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).
And a two functions to construct the reduction and the closure from the cond.gr.rd. and the cond.gr.cl. and the mappings. Yeah, thats a possible way.
I don't mean two functions. Here's what I had in mind in more detail: Assume: - component == SCC - G is the graph - .+ is the transitive closure operator - .- is the transitive closure/reduction operator - C is the condensation graph - comp(v) maps from a vertex in G to its corresponding component in C - next(v) maps from a vertex in G to another vertex in the same component (creating a loop in each component) - rep(v) is a bit flag that is true for one vertex in G in each component Now, as far as I understand, an edge (v, w) is in G+ iff (comp(v), comp(w)) is an edge in C+. An edge (v, w) is in G- iff either w = next(v) or rep(v) and rep(w) and (comp(v), comp(w)) is an edge in C-. You can define a graph type based on those computations. For the closure, you would store C+ and comp() explicitly, and then compute things like out_edges(v, G+) based on those using the formula above. For the reduction, you would store C-, comp(), next(), and rep(), then use the formulas to compute out_edges(v, G-). The other graph operations like vertices() would just forward to the original G. Using that kind of approach, you can create graph objects (things that model the graph concepts) that can be used to get the transitive closure and reduction of G while only storing information about the closure and reduction of C and a couple of other property maps on G.
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?).
Nope. The reduction of the condensation graph is only written, not read in the core algorithm. It gets read if one tries to build the transitive reduction of the whole graph.
But I don't like that option, too. It is ugly.
OK. When do you need to read it back to produce the closure of the full graph? Don't you just need equivalents of the comp(), next(), and rep() maps that I talked about above, plus a way to emit the edges of the reduction of the condensation graph?
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.
If you think it is feasible, then I would like to take that route. One remedy still remains in my perception. If the user doesn't want the transitive reduction, an unused local variable remains in the main implementation function ...
Can that be removed somehow by fancy template stuff?
Something simple like the if statement I showed above should be enough to deal with that issue. If not, it's pretty easy to use mpl::if_ to remove the reduction code more completely.
What's your favorite choice?
I like the implicit graph idea because of its elegance and reduction in output size, but it is more work to implement (the formulas I put down above are fairly simple but turning them into iterators is more work; if you want to go this way, I can give more detailed pseudocode closer to what you actually need to write to model BGL concepts). Otherwise, either streaming edges to an output iterator (my option 1) or one of your options is reasonable. Your option 1 is probably equivalent to your option 2, since you can special-case the code based on your black-hole graph type and so not actually do the graph insertions when it is used; remember too that named parameters can be used so the user doesn't actually see the black-hole graph. -- Jeremiah Willcock

Dear Jeremiah, Jeremiah Willcock <jewillco@osl.iu.edu> writes:
Is there a reason you're not using the current transitive_closure algorithm in BGL?
An already computed transitive closure can't be used, as there is a need to compute it in all cases, as some times it must be checked, whether an edge is already in the to be computed closure.
I don't understand what you're saying, and it seems to be contradicted by your next part about using Vladimir's transitive_closure code.
I meant to say that I can't compute the reduction of a graph from an existing transitive closure. One could say, I think, the algorithm computes the transitive closure and from time to time writes an edge to the transitive reduction. But the decision, whether to write an edge to the transitive reduction isn't based on properties of the transitive closure, but on properties of the state of the construction process of the transitive closure.
I don't remember if that was just for the condensation graph or if it was a transitive closure of the whole input graph.
Just for the condensation graph.
That's what I thought. BTW, did you see <boost/graph/create_condensation_graph.hpp>? Is anything in there useful to you?
Yes! Great. Why hadn't Vladimir used that in its transitive_closure.hpp? Maybe transitive_closure predates create_condensation_graph.hpp? I wonder though, there doesn't seem to be documentation about this?
You also need an explicit condensation graph as temporary storage for doing the reduction, too, or am I mistaken?
I'm not sure about this. The transitive_reduction of the condensation graph is only touched to insert edges. It is not read in the “core“ algorithm. It is needed, to construct the transitive_reduction of the original graph I think. (If the reduction of the original graph is stored as an explicit graph, or if I write vertex pairs to an output iterator isn't important though.)
So you don't need to read back any of the transitive reduction of the condensation graph as part of creating it?
I don't need to read back any of the transitive reduction of the condensation graph “as part of creating the transitive reduction of the condensation graph.” Like that, it is true.
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).
And a two functions to construct the reduction and the closure from the cond.gr.rd. and the cond.gr.cl. and the mappings. Yeah, thats a possible way.
I don't mean two functions. Here's what I had in mind in more detail:
Assume: - component == SCC - G is the graph - .+ is the transitive closure operator - .- is the transitive closure/reduction operator - C is the condensation graph - comp(v) maps from a vertex in G to its corresponding component in C - next(v) maps from a vertex in G to another vertex in the same component (creating a loop in each component) - rep(v) is a bit flag that is true for one vertex in G in each component
Now, as far as I understand, an edge (v, w) is in G+ iff (comp(v), comp(w)) is an edge in C+. An edge (v, w) is in G- iff either w = next(v) or rep(v) and rep(w) and (comp(v), comp(w)) is an edge in C-. You can define a graph type based on those computations. For the closure, you would store C+ and comp() explicitly, and then compute things like out_edges(v, G+) based on those using the formula above. For the reduction, you would store C-, comp(), next(), and rep(), then use the formulas to compute out_edges(v, G-). The other graph operations like vertices() would just forward to the original G. Using that kind of approach, you can create graph objects (things that model the graph concepts) that can be used to get the transitive closure and reduction of G while only storing information about the closure and reduction of C and a couple of other property maps on G.
Ah, yes that would be quite cool. Sounds like work, though. How about internal properties of a graph? I don't understand those very good and could imagine, that it would be better not to try to provide them through G+ or G- as the type of G- or G+ would need to carry all those internal properties? Should the original graph be copied for the result of the algorithm? For example to avoid life-time issues and maybe a mutable graph, that gets changed after the algorithm has been applied? Or would it be sufficient to write in the documentation, that a change to a mutable graph invalidates the decorator? And that the user has to make sure, that the original graph lifes longer than the decorator? With boost/iterators/iterator_adapter.hpp the iterators should be manageable, but I doubt, that I can do an (for exampel out_edge) iterator with a amortized constant time operator++, as every out edge of a vertex has to be tested by the formulas above. So if one or more edges don't pass the test (aka are not edges of the transitive reduction) operator++ will not be constant time. Is that an issue? Do you have a idea to tackle that? If I think about it, the result of the algorithm could be a factory for filter_iterator or so ...
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?).
Nope. The reduction of the condensation graph is only written, not read in the core algorithm. It gets read if one tries to build the transitive reduction of the whole graph.
But I don't like that option, too. It is ugly.
OK. When do you need to read it back to produce the closure of the full graph? Don't you just need equivalents of the comp(), next(), and rep() maps that I talked about above, plus a way to emit the edges of the reduction of the condensation graph?
Yes, thats exactly true.
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.
If you think it is feasible, then I would like to take that route. One remedy still remains in my perception. If the user doesn't want the transitive reduction, an unused local variable remains in the main implementation function ...
Can that be removed somehow by fancy template stuff?
Something simple like the if statement I showed above should be enough to deal with that issue. If not, it's pretty easy to use mpl::if_ to remove the reduction code more completely.
What's your favorite choice?
I like the implicit graph idea because of its elegance and reduction in output size, but it is more work to implement (the formulas I put down above are fairly simple but turning them into iterators is more work; if you want to go this way, I can give more detailed pseudocode closer to what you actually need to write to model BGL concepts).
Hmm. Are there documented BGL iterator concepts? I couldn't find those.
Otherwise, either streaming edges to an output iterator (my option 1) or one of your options is reasonable. Your option 1 is probably equivalent to your option 2, since you can special-case the code based on your black-hole graph type and so not actually do the graph insertions when it is used; remember too that named parameters can be used so the user doesn't actually see the black-hole graph.
I think for my option 2 there isn't a need for a black-hole-graph type, as the DONT_COMPUTE_TRANSITIVE_CLOSURE type is only used by the interface functions and not by any function a user should access. So there is no need to supply all the get, set, vertices, add_edge, ... functions. My resumee: Your option 1 is easiest and probably best. Your option 2 makes a nice learning experience. I'll try to do your option 2. If you have any ideas, how to make the operator++ of the iterators amortized constant time, let me know. Yours, Eric

On Mon, 19 Jul 2010, Eric Wolf wrote:
Dear Jeremiah,
Jeremiah Willcock <jewillco@osl.iu.edu> writes:
Is there a reason you're not using the current transitive_closure algorithm in BGL?
An already computed transitive closure can't be used, as there is a need to compute it in all cases, as some times it must be checked, whether an edge is already in the to be computed closure.
I don't understand what you're saying, and it seems to be contradicted by your next part about using Vladimir's transitive_closure code.
I meant to say that I can't compute the reduction of a graph from an existing transitive closure. One could say, I think, the algorithm computes the transitive closure and from time to time writes an edge to the transitive reduction. But the decision, whether to write an edge to the transitive reduction isn't based on properties of the transitive closure, but on properties of the state of the construction process of the transitive closure.
OK. My understanding now is that you create the transitive closure and need to have explicit access to previously created parts of it, but the reduction is a possible side product of that computation that you do not need to look at during its creation. Is that correct?
I don't remember if that was just for the condensation graph or if it was a transitive closure of the whole input graph.
Just for the condensation graph.
That's what I thought. BTW, did you see <boost/graph/create_condensation_graph.hpp>? Is anything in there useful to you?
Yes! Great. Why hadn't Vladimir used that in its transitive_closure.hpp? Maybe transitive_closure predates create_condensation_graph.hpp? I wonder though, there doesn't seem to be documentation about this?
I don't know anything about it either. It doesn't seem to be used anywhere in BGL.
You also need an explicit condensation graph as temporary storage for doing the reduction, too, or am I mistaken?
I'm not sure about this. The transitive_reduction of the condensation graph is only touched to insert edges. It is not read in the “core“ algorithm. It is needed, to construct the transitive_reduction of the original graph I think. (If the reduction of the original graph is stored as an explicit graph, or if I write vertex pairs to an output iterator isn't important though.)
So you don't need to read back any of the transitive reduction of the condensation graph as part of creating it?
I don't need to read back any of the transitive reduction of the condensation graph “as part of creating the transitive reduction of the condensation graph.” Like that, it is true.
OK.
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).
And a two functions to construct the reduction and the closure from the cond.gr.rd. and the cond.gr.cl. and the mappings. Yeah, thats a possible way.
I don't mean two functions. Here's what I had in mind in more detail:
Assume: - component == SCC - G is the graph - .+ is the transitive closure operator - .- is the transitive closure/reduction operator - C is the condensation graph - comp(v) maps from a vertex in G to its corresponding component in C - next(v) maps from a vertex in G to another vertex in the same component (creating a loop in each component) - rep(v) is a bit flag that is true for one vertex in G in each component
Now, as far as I understand, an edge (v, w) is in G+ iff (comp(v), comp(w)) is an edge in C+. An edge (v, w) is in G- iff either w = next(v) or rep(v) and rep(w) and (comp(v), comp(w)) is an edge in C-. You can define a graph type based on those computations. For the closure, you would store C+ and comp() explicitly, and then compute things like out_edges(v, G+) based on those using the formula above. For the reduction, you would store C-, comp(), next(), and rep(), then use the formulas to compute out_edges(v, G-). The other graph operations like vertices() would just forward to the original G. Using that kind of approach, you can create graph objects (things that model the graph concepts) that can be used to get the transitive closure and reduction of G while only storing information about the closure and reduction of C and a couple of other property maps on G.
Ah, yes that would be quite cool. Sounds like work, though. How about internal properties of a graph? I don't understand those very good and could imagine, that it would be better not to try to provide them through G+ or G- as the type of G- or G+ would need to carry all those internal properties?
I would at most forward vertex properties to the original graph; there is no point doing anything about edge properies. The filtered_graph class does that kind of forwarding to its underlying graph.
Should the original graph be copied for the result of the algorithm? For example to avoid life-time issues and maybe a mutable graph, that gets changed after the algorithm has been applied?
I think the condensation graph and the maps I described are enough to store the closure and/or reduction without needing the original graph; the properties of the original graph would need to stay around if those are going to be forwarded from the new graphs. That is something that can just be handled through documentation, though, like filtered_graph does (i.e., just say that the new graphs can refer to the old ones and so they need to be kept around unmodified). The user can copy the result graphs of transitive_reduction if they want to modify or delete the underlying graph.
Or would it be sufficient to write in the documentation, that a change to a mutable graph invalidates the decorator? And that the user has to make sure, that the original graph lifes longer than the decorator?
I think that's the right approach.
With boost/iterators/iterator_adapter.hpp the iterators should be manageable, but I doubt, that I can do an (for exampel out_edge) iterator with a amortized constant time operator++, as every out edge of a vertex has to be tested by the formulas above. So if one or more edges don't pass the test (aka are not edges of the transitive reduction) operator++ will not be constant time. Is that an issue? Do you have a idea to tackle that?
I think a good first try (and maybe a good final result) is to use shared_array_iterator and have out_edges() compute the full edge set immediately. The iterators would then just return the precomputed values from the array.
If I think about it, the result of the algorithm could be a factory for filter_iterator or so ...
I had thought about that, and I think constant time increment is possible, but it is likely that the constants in it will still be large and it will be complicated to implement. I would at least start with shared_array_iterator and consider possibly changing to something else later.
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?).
Nope. The reduction of the condensation graph is only written, not read in the core algorithm. It gets read if one tries to build the transitive reduction of the whole graph.
But I don't like that option, too. It is ugly.
OK. When do you need to read it back to produce the closure of the full graph? Don't you just need equivalents of the comp(), next(), and rep() maps that I talked about above, plus a way to emit the edges of the reduction of the condensation graph?
Yes, thats exactly true.
OK.
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.
If you think it is feasible, then I would like to take that route. One remedy still remains in my perception. If the user doesn't want the transitive reduction, an unused local variable remains in the main implementation function ...
Can that be removed somehow by fancy template stuff?
Something simple like the if statement I showed above should be enough to deal with that issue. If not, it's pretty easy to use mpl::if_ to remove the reduction code more completely.
What's your favorite choice?
I like the implicit graph idea because of its elegance and reduction in output size, but it is more work to implement (the formulas I put down above are fairly simple but turning them into iterators is more work; if you want to go this way, I can give more detailed pseudocode closer to what you actually need to write to model BGL concepts).
Hmm. Are there documented BGL iterator concepts? I couldn't find those.
BGL mostly uses the standard STL iterator concepts, plus MultiPassInputIterator (which is documented in the BGL documentation).
Otherwise, either streaming edges to an output iterator (my option 1) or one of your options is reasonable. Your option 1 is probably equivalent to your option 2, since you can special-case the code based on your black-hole graph type and so not actually do the graph insertions when it is used; remember too that named parameters can be used so the user doesn't actually see the black-hole graph.
I think for my option 2 there isn't a need for a black-hole-graph type, as the DONT_COMPUTE_TRANSITIVE_CLOSURE type is only used by the interface functions and not by any function a user should access. So there is no need to supply all the get, set, vertices, add_edge, ... functions.
My resumee: Your option 1 is easiest and probably best. Your option 2 makes a nice learning experience.
I'll try to do your option 2. If you have any ideas, how to make the operator++ of the iterators amortized constant time, let me know.
See above for hints. -- Jeremiah Willcock

Dear Jeremiah, Jeremiah Willcock <jewillco@osl.iu.edu> writes:
On Mon, 19 Jul 2010, Eric Wolf wrote:
I meant to say that I can't compute the reduction of a graph from an existing transitive closure. One could say, I think, the algorithm computes the transitive closure and from time to time writes an edge to the transitive reduction. But the decision, whether to write an edge to the transitive reduction isn't based on properties of the transitive closure, but on properties of the state of the construction process of the transitive closure.
OK. My understanding now is that you create the transitive closure and need to have explicit access to previously created parts of it, but the reduction is a possible side product of that computation that you do not need to look at during its creation. Is that correct?
Yes. But the point is that not only “need to have explicit access to previously created parts of it”, but also that access is needed to a transitive closure, thats not yet finished. (Each state of the construction process determines, wether to write an edge to the transitive reduction.) Yours Eric

On Mon, 26 Jul 2010, Eric Wolf wrote:
Dear Jeremiah,
Jeremiah Willcock <jewillco@osl.iu.edu> writes:
On Mon, 19 Jul 2010, Eric Wolf wrote:
I meant to say that I can't compute the reduction of a graph from an existing transitive closure. One could say, I think, the algorithm computes the transitive closure and from time to time writes an edge to the transitive reduction. But the decision, whether to write an edge to the transitive reduction isn't based on properties of the transitive closure, but on properties of the state of the construction process of the transitive closure.
OK. My understanding now is that you create the transitive closure and need to have explicit access to previously created parts of it, but the reduction is a possible side product of that computation that you do not need to look at during its creation. Is that correct?
Yes. But the point is that not only “need to have explicit access to previously created parts of it”, but also that access is needed to a transitive closure, thats not yet finished. (Each state of the construction process determines, wether to write an edge to the transitive reduction.)
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. -- Jeremiah Willcock

Jeremiah Willcock <jewillco@osl.iu.edu> 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 vacation. Yours, Eric

On Sat, 7 Aug 2010, Eric Wolf wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> 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 vacation.
Are you still interested in submitting your transitive closure and reduction code? -- Jeremiah Willcock

Dear Jeremiah, Jeremiah Willcock <jewillco@osl.iu.edu> writes:
On Sat, 7 Aug 2010, Eric Wolf wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> 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 vacation.
Are you still interested in submitting your transitive closure and reduction code?
https://svn.boost.org/trac/boost/attachment/ticket/3821/transitive_reduction... 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 algorithm. 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 called. 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 forward them. Does that stuff go in the right direction? Your sincerely, Eric

Dear Jeremiah, I gave up. If someone is willing to include the transitive reduction in bgl, he should do it. Your sincerely, Eric
participants (5)
-
Andrew Sutton
-
Eric Wolf
-
Gautam Sewani
-
Jeremiah Willcock
-
Matthias Walter