
GSOC 2008 is on: http://code.google.com/soc/2008/ If folks have ideas for potential projects then now would be a good time to start thinking about them - that way we can apply to Google to be a mentoring organisation with a good selection of ideas already up and running. Cheers, John.

If folks have ideas for potential projects then now would be a good time to start thinking about them - that way we can apply to Google to be a mentoring organisation with a good selection of ideas already up and running.
I've been thinking about Boost.Graph v2. I was hoping to finish the work that I started in the fall. Of course, I was hoping for a little more free reign with the interfaces for this work - source compatibility won't be high on my list of priorities in my proposal. Andrew Sutton asutton@cs.kent.edu

On Mar 2, 2008, at 6:31 PM, Andrew Sutton wrote:
If folks have ideas for potential projects then now would be a good time to start thinking about them - that way we can apply to Google to be a mentoring organisation with a good selection of ideas already up and running.
I've been thinking about Boost.Graph v2. I was hoping to finish the work that I started in the fall. Of course, I was hoping for a little more free reign with the interfaces for this work - source compatibility won't be high on my list of priorities in my proposal.
So long as Visual C++ 6/7 compatibility isn't also high on your list of priorities, go for it :) Half of the ugliness of the BGL implementation is in the workarounds needed to deal with compilers that can't handle class template partial specialization. - Doug

I've been thinking about Boost.Graph v2. I was hoping to finish the work that I started in the fall. Of course, I was hoping for a little more free reign with the interfaces for this work - source compatibility won't be high on my list of priorities in my proposal.
So long as Visual C++ 6/7 compatibility isn't also high on your list of priorities, go for it :)
I think this would be true for any library with a non-trivial template component.
Half of the ugliness of the BGL implementation is in the workarounds needed to deal with compilers that can't handle class template partial specialization.
Since I'm thinking about being experimental, and SoC is a sandbox within a sandbox, maybe it wouldn't hurt to build the next version using newer C++ features (esp. variadic templates). I also have a couple of other goals that don't align very well the current implementation either. 1. Making the interface a little less generic without sacrificing flexibility. For example, I don't know that the vertex/edge storage stuff actually sees much use, and it can cause terrible inefficiency if you're not extremely careful with it (e.g., num_vertices()/ num_edges() using listS storage). Also, I never did understand why certain functions weren't just member functions (like add_vertex()). 2. Revisit the interface and implementation for BFS/DFS, and get rid of the parameter passing. It's ugly and causes a lot of problems for people learning how to write the code. My gut feeling on this is that if you're using optional parameters to have the same algorithm behave somewhat differently, then building a new function might not be a bad idea. I also want to redesign the searches for "stoppability" - either for user-selected termination (as per Loïc's request), or in the case of disjoint subgraphs. I'm also hoping to use the experience as fodder for a class I'm teaching in the Fall - Generic Programming and Library Design. Obviously, it would be nearly impossible to re-implement the entirety of the BGL, but I think that taking a long slow look at the interfaces and providing a subset with some very common algorithms (BFS, DFS, etc...) using new C++ features could provide an interesting data point for how new features could be used. Andrew Sutton asutton@cs.kent.edu

On Mar 5, 2008, at 7:32 AM, Andrew Sutton wrote:
Half of the ugliness of the BGL implementation is in the workarounds needed to deal with compilers that can't handle class template partial specialization.
Since I'm thinking about being experimental, and SoC is a sandbox within a sandbox, maybe it wouldn't hurt to build the next version using newer C++ features (esp. variadic templates).
I don't imagine that variadic templates would help all that much, but who knows?
I also have a couple of other goals that don't align very well the current implementation either. 1. Making the interface a little less generic without sacrificing flexibility. For example, I don't know that the vertex/edge storage stuff actually sees much use, and it can cause terrible inefficiency if you're not extremely careful with it (e.g., num_vertices()/ num_edges() using listS storage).
These are pretty important operations... I don't think they can go away, even though they do require linear time for some data structures.
Also, I never did understand why certain functions weren't just member functions (like add_vertex()).
It's so that people can use their own graph types with BGL algorithms. I guess one could have a member "add_vertex" in adjacency_list and also have the free function "add_vertex" that just forwards to the member, which might be easier for users... but I'm not convinced that the redundancy would help.
2. Revisit the interface and implementation for BFS/DFS, and get rid of the parameter passing.
... or use the Boost.Parameter library, which simplifies passing optional parameters. [*]
It's ugly and causes a lot of problems for people learning how to write the code. My gut feeling on this is that if you're using optional parameters to have the same algorithm behave somewhat differently, then building a new function might not be a bad idea.
Interesting. There's a lot of internal reuse of BFS and DFS that would go away if they lost some of their flexibility, but perhaps there's a way to have both.
I also want to redesign the searches for "stoppability" - either for user-selected termination (as per Loïc's request), or in the case of disjoint subgraphs.
DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size. - Doug [*] Now *that* is a library that could benefit from variadic templates!

On Wed, Mar 5, 2008 at 7:49 AM, Douglas Gregor <doug.gregor@gmail.com> wrote:
Why does everyone dislike throwing an exception to terminate the search?
I imagine that most people view using exceptions for control flow as being akin to using "goto". ;-) Under normal circumstances, they're probably right. However with deep nesting or recursion, I'm not so sure. Throwing certainly seems to offer an extremely simple way to do it. I bet if someone went ahead and benchmarked
the two options, the exception would be faster for graphs of non- trivial size.
I would be extremely interested in seeing any benchmark results. Jon

On Wed, Mar 5, 2008 at 11:52 AM, Jonathan Franklin <franklin.jonathan@gmail.com> wrote:
On Wed, Mar 5, 2008 at 7:49 AM, Douglas Gregor <doug.gregor@gmail.com> wrote:
Why does everyone dislike throwing an exception to terminate the search?
I imagine that most people view using exceptions for control flow as being akin to using "goto". ;-)
Under normal circumstances, they're probably right. However with deep nesting or recursion, I'm not so sure. Throwing certainly seems to offer an extremely simple way to do it.
I bet if someone went ahead and benchmarked
the two options, the exception would be faster for graphs of non- trivial size.
I would be extremely interested in seeing any benchmark results.
I have a Pathfinding library that currently uses visitors much like the BGL, except mine uses a visitor.at_goal() function to signal when to terminate the search, rather than an exception. I modified the code to no longer call that function, and instead loop infinitely (until the search space is exhausted), meaning the visitor now had to throw an exception to exit once it reached the goal. Here are my results in Release mode, full optimizations, averaged over 10 runs each. There were only about 15,000 nodes generated in the search, so it wasn't a very large graph. at_goal() called every iteration - 0.121104 seconds exception - 0.130855 seconds Not very scientific I know...also it uses my own library, not BGL, but someone would have to modify BGL's algorithms and visitor class to use a function that returns a bool (continue searching, or not) to do a meaningful benchmark. 0.01 seconds might be enough for some people in games to want an alternative. Exceptions are also supported much more primitively on most consoles (either not at all, or they are much slower). Both of these may be why some people don't want exceptions as the early termination method. --Michael Fawcett

On Wed, Mar 5, 2008 at 11:15 AM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
<snip>
There were only about 15,000 nodes generated in the
search, so it wasn't a very large graph.
Any way to crank that up to 150,000, or 1.5 million? Thanks for the data point. Jon

On Wed, Mar 5, 2008 at 1:51 PM, Jonathan Franklin <franklin.jonathan@gmail.com> wrote:
On Wed, Mar 5, 2008 at 11:15 AM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
<snip>
There were only about 15,000 nodes generated in the
search, so it wasn't a very large graph.
Any way to crank that up to 150,000, or 1.5 million?
Same test, but I resized the image to 1280 x 1280 (it was at 128 x 128). There were 1,016,906 nodes generated during the search. I only did each version 5 times instead of 10 this time, since it took quite a bit longer. at_goal() - 19.05272 seconds exception - 18.85408 seconds So, throwing an exception was faster in this case. Just to make sure I didn't screw things up the first time, I tried it again with the 128 x 128 bitmap, and at_goal() was indeed faster than the exception again over 5 runs (this time by 0.02 seconds, not 0.01 like before). I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly. --Michael Fawcett

Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.
I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run? Sebastian Redl

On Wed, Mar 5, 2008 at 3:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.
I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?
I have cygwin available. This might take some time to do though, I'll try to get around to it before the end of the week. The code is unfortunately company code, so I can't share it, but I'm hoping to convince them to let me release it soon. --Michael Fawcett

on Thu Mar 06 2008, "Michael Fawcett" <michael.fawcett-AT-gmail.com> wrote:
On Wed, Mar 5, 2008 at 3:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.
I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?
I have cygwin available. This might take some time to do though, I'll try to get around to it before the end of the week.
Cygwin won't tell us much; it uses essentially the same crappy SJLJ exception implementation that VS uses in 32-bit mode, IIRC. -- Dave Abrahams Boost Consulting http://boost-consulting.com

On Sun, Apr 27, 2008 at 9:39 PM, David Abrahams <dave@boost-consulting.com> wrote:
on Thu Mar 06 2008, "Michael Fawcett" <michael.fawcett-AT-gmail.com> wrote:
On Wed, Mar 5, 2008 at 3:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.
I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?
I have cygwin available. This might take some time to do though, I'll try to get around to it before the end of the week.
Cygwin won't tell us much; it uses essentially the same crappy SJLJ exception implementation that VS uses in 32-bit mode, IIRC.
I don't know much about Cygwin, but the results were very different from Cygwin/gcc vs Windows/VS 2005. Why this was, I have no clue and never investigated further. --Michael Fawcett

On Wed, Mar 5, 2008 at 4:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.
I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?
So I finally got it compiling and running under Cygwin/gcc. Here are the results (averaged over 5 runs): 1280 x 1280 at_goal() - 23.45162 seconds exception - 23.39538 seconds 128 x 128 at_goal() - 0.20304038 seconds exception - 0.1919092 seconds So exception beat at_goal() in both cases here, but the margins are much smaller. I suspect that I wasn't compiling to gcc's fullest optimization potential, but I did use -O3. --Michael Fawcett

On Mar 12, 2008, at 6:38 PM, Michael Fawcett wrote:
On Wed, Mar 5, 2008 at 4:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.
I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?
So I finally got it compiling and running under Cygwin/gcc. Here are the results (averaged over 5 runs):
1280 x 1280
at_goal() - 23.45162 seconds exception - 23.39538 seconds
128 x 128
at_goal() - 0.20304038 seconds exception - 0.1919092 seconds
So exception beat at_goal() in both cases here, but the margins are much smaller. I suspect that I wasn't compiling to gcc's fullest optimization potential, but I did use -O3.
Very interesting. Thanks for running these experiments! - Doug

So exception beat at_goal() in both cases here, but the margins are
I haven't tried the experiments and this could be all wet, but I wonder how much more pronounced the difference would be if the at_goal() method were virtual? (and the static binding could not be inferred at compile time)

on Wed Mar 05 2008, Sebastian Redl <sebastian.redl-AT-getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler.
64- or 32- bit? It matters. -- Dave Abrahams Boost Consulting http://boost-consulting.com

On Sun, Apr 27, 2008 at 9:38 PM, David Abrahams <dave@boost-consulting.com> wrote:
on Wed Mar 05 2008, Sebastian Redl <sebastian.redl-AT-getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler.
64- or 32- bit? It matters.
32-bit. --Michael Fawcett

on Sun Apr 27 2008, "Michael Fawcett" <michael.fawcett-AT-gmail.com> wrote:
On Sun, Apr 27, 2008 at 9:38 PM, David Abrahams <dave@boost-consulting.com> wrote:
on Wed Mar 05 2008, Sebastian Redl <sebastian.redl-AT-getdesigned.at> wrote:
Michael Fawcett wrote:
I forgot to mention before that this is using VS 2005 as the compiler.
64- or 32- bit? It matters.
32-bit.
That's a poor test of any other compiler, or of what's possible, then. MS used the setjmp/longjmp approach to EH with that compiler, for compatibility with "structured exceptions." The 64-bit compiler has a "real" EH implementation ;-) One more thing to note about the case of terminating graph algorithms with exceptions: these algorithms have *lots* of hooks for each iteration of the process, each of which might need to terminate the algorithm (e.g. http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/DFSVisitor.html), so that can add up to quite a few tests for each iteration of the inner loop, which can be avoided if EH is used. -- Dave Abrahams Boost Consulting http://boost-consulting.com

On Mon, Apr 28, 2008 at 9:10 AM, David Abrahams <dave@boost-consulting.com> wrote:
One more thing to note about the case of terminating graph algorithms with exceptions: these algorithms have *lots* of hooks for each iteration of the process, each of which might need to terminate the algorithm (e.g. http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/DFSVisitor.html ), so that can add up to quite a few tests for each iteration of the inner loop, which can be avoided if EH is used.
Right. However, what we would like to accomplish here is to move away from speculation over how poorly one method performs over the other, and gather some good empirical data that covers all (or at least the most prevalent) usage patterns. Jon

Right. However, what we would like to accomplish here is to move away from speculation over how poorly one method performs over the other, and gather some good empirical data that covers all (or at least the most prevalent) usage patterns.
Fortunately, my proposal sorta covers this type empirical investigation. Part of it is to look at other some other graph libraries and see how they provide various aspects of the interface. My guess is I'll end up producing a bunch of little generic kernels that can be composed to provide variations on searches (e.g., traversal, find first, find all, etc.). Andrew Sutton asutton@cs.kent.edu

On Mon, Apr 28, 2008 at 11:10 AM, David Abrahams <dave@boost-consulting.com> wrote:
One more thing to note about the case of terminating graph algorithms with exceptions: these algorithms have *lots* of hooks for each iteration of the process, each of which might need to terminate the algorithm (e.g. http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/DFSVisitor.html), so that can add up to quite a few tests for each iteration of the inner loop, which can be avoided if EH is used.
Understood. I thought we were simply talking about the cost of an exception vs the cost of *one more* hook (e.g. an at_goal() hook). Most of the algorithms loop until some container is empty, or until the search area is exhausted. This one extra hook would be in addition to that check, e.g. while (search_not_exhausted && visitor.at_goal(current) == false) { /* call other hooks */ } Their visitor can handle the details of storing another bool if they need to be able to signal termination from any hook. --Michael Fawcett

On Wed, Mar 5, 2008 at 1:14 PM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
Same test, but I resized the image to 1280 x 1280 (it was at 128 x 128). There were 1,016,906 nodes generated during the search.
<snip>
at_goal() - 19.05272 seconds exception - 18.85408 seconds
So on this platform/configuration, w/ ~15K nodes, at_goal() was ~7.5% faster, and w/ ~1M nodes, exception was a little over 1% faster. It would be interesting to plot some curves to see where the turning point for this platform lies. I still wonder if the exception method would *significantly* outperform at_goal() for larger graphs. For me, 1% isn't all that compelling, unless it offers something else, such as design simplicity (or decreasing the WTF?!? (astonishment) factor). Jon

on Wed Mar 05 2008, "Michael Fawcett" <michael.fawcett-AT-gmail.com> wrote:
Here are my results in Release mode, full optimizations, averaged over 10 runs each. There were only about 15,000 nodes generated in the search, so it wasn't a very large graph.
at_goal() called every iteration - 0.121104 seconds
exception - 0.130855 seconds
Not very scientific I know...also it uses my own library, not BGL, but someone would have to modify BGL's algorithms and visitor class to use a function that returns a bool (continue searching, or not) to do a meaningful benchmark.
I know it's a bit late to add anythign here, but... the compiler being used is the most important piece of information I'd need to evaluate whether this number means anything at all. -- Dave Abrahams Boost Consulting http://boost-consulting.com

Douglas Gregor a écrit :
I also want to redesign the searches for "stoppability" - either for user-selected termination (as per Loïc's request), or in the case of disjoint subgraphs.
DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size.
There are two kind of early-stop. One is : "Stop the search". The other one is : "Stop looking in this direction, but continue the search". Throwing an exception may be a solution for the first category, but I don't see how is could help for the second. Maybe another way to go for the second would be to manually modify some well chosen colors in the visitor functions, but this approach seemed to scary for me to try it. -- Loïc

on Wed Mar 05 2008, Loïc Joly <loic.actarus.joly-AT-numericable.fr> wrote:
Douglas Gregor a écrit :
I also want to redesign the searches for "stoppability" - either for user-selected termination (as per Loïc's request), or in the case of disjoint subgraphs.
DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size.
There are two kind of early-stop. One is : "Stop the search". The other one is : "Stop looking in this direction, but continue the search".
Throwing an exception may be a solution for the first category, but I don't see how is could help for the second. Maybe another way to go for the second would be to manually modify some well chosen colors in the visitor functions, but this approach seemed to scary for me to try it.
I would probably do that kind of pruning with a graph adaptor. -- Dave Abrahams Boost Consulting http://boost-consulting.com

I don't imagine that variadic templates would help all that much, but who knows?
I thought vertex/edge property specification was built using recursive templates. I was thinking of that as an application for variadic templates, but I could be way off base :)
IFor example, I don't know that the vertex/edge storage stuff actually sees much use, and it can cause terrible inefficiency if you're not extremely careful with it (e.g., num_vertices()/ num_edges() using listS storage).
These are pretty important operations... I don't think they can go away, even though they do require linear time for some data structures.
I wouldn't get rid of the operations - they're pretty fundamental. I was just thinking about the underlying storage mechanisms for edge lists and vertex lists. I can certainly see arguments for using non- vector storage, but I don't know how often its used in practice.
It's so that people can use their own graph types with BGL algorithms.
Why not just build a simple wrapper class? My concern here is that trying to provide a generic interface for a number of different implementations may actually inhibit the utility of the specific implementations of graph types and algorithms within the library.
... or use the Boost.Parameter library, which simplifies passing optional parameters. [*]
I played with this last summer - it doesn't actually seem to solve the problem. In fact, it actually makes it a little bit worse because it hides (the inevitable) compiler errors behind a thick wall of preprocessor code. The problem is not passing optional parameters, but the fact that doing so is often used to select different versions of the same algorithm. It becomes very difficult to document.
DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size.
That's a good idea. I've always felt a little queasy about throwing exceptions as a means of terminating a function when no error has occurred, but there may not be anything /too/ wrong with it in this case. It would avoid the requirement to check a terminate condition in every iteration of the algorithm. Hiding the throw behind a function might not hurt either. Something like finish() or stop(). I don't know... maybe I'm thinking too hard. Building a version of BGL2 based on the current code base (or whatever's in sandbox) is just as good a summer project. Andrew Sutton asutton@cs.kent.edu

On Mar 5, 2008, at 10:19 PM, Andrew Sutton wrote:
I don't imagine that variadic templates would help all that much, but who knows?
I thought vertex/edge property specification was built using recursive templates. I was thinking of that as an application for variadic templates, but I could be way off base :)
Ah. Well, you're right, but I'd eliminate that way of specifying properties. Instead, I would do everything with "bundled" properties, because they provide a much more solid mapping between the user's domain and the graph library.
I wouldn't get rid of the operations - they're pretty fundamental. I was just thinking about the underlying storage mechanisms for edge lists and vertex lists. I can certainly see arguments for using non- vector storage, but I don't know how often its used in practice.
It's one of those, "when you need it, you *really* need it" things. Sometimes you need to be able to add edges and vertices quickly, without invalidating descriptions. Non-vector containers are great for that.
It's so that people can use their own graph types with BGL algorithms.
Why not just build a simple wrapper class?
One reason not to rely on wrappers is that they must be specified every time one uses a BGL algorithm, e.g., breadth_first_search(wrap_as_bgl_graph(mygraph), ...) By using a traits- and free-function based approach in the BGL, merely including the appropriate header makes any existing data structure "just work" as a BGL graph.
My concern here is that trying to provide a generic interface for a number of different implementations may actually inhibit the utility of the specific implementations of graph types and algorithms within the library.
I'm not sure I understand. If we're inhibiting the utility of specific graph types/algorithms, then our concepts are probably wrong (or, at least, the concept taxonomy itself isn't complete enough).
... or use the Boost.Parameter library, which simplifies passing optional parameters. [*]
I played with this last summer - it doesn't actually seem to solve the problem. In fact, it actually makes it a little bit worse because it hides (the inevitable) compiler errors behind a thick wall of preprocessor code. The problem is not passing optional parameters, but the fact that doing so is often used to select different versions of the same algorithm. It becomes very difficult to document.
Perhaps we need to draw a line between customizing an algorithm (which could/should(?) be done through optional parameters) and selecting different variants of an algorithm (which should not be done through optional parameters). Drawing that distinction might simplify the use of these algorithms.
I don't know... maybe I'm thinking too hard. Building a version of BGL2 based on the current code base (or whatever's in sandbox) is just as good a summer project.
I think we're just envisioning different "final products" for BGLv2, because we use BGL for different things. Today, I happen to be working with VTK, which has a new vtkGraph data type. They provide the appropriate graph_traits specializations, free functions, etc. so that a pointer to a vtkGraph (vtkGraph*) works off-the-shelf in BGL algorithms: no wrappers required. That's exactly the kind of thing that I believe the BGL excels at, and I think it's important for future revisions of the BGL to support that use case. There's a lot of cruft I'd like to eliminate---non-partial-specialization hacks, the property<...> class, etc.---and bits that I'd like to clean up--- property map creation is too hard, adjacency_list has too many knobs only useful in rare circumstances, etc.---but I think, fundamentally, the Graph concepts are just about right. - Doug

I played with this last summer - it doesn't actually seem to solve the problem. In fact, it actually makes it a little bit worse because it hides (the inevitable) compiler errors behind a thick wall of preprocessor code. The problem is not passing optional parameters, but the fact that doing so is often used to select different versions of the same algorithm. It becomes very difficult to document.
Perhaps we need to draw a line between customizing an algorithm (which could/should(?) be done through optional parameters) and selecting different variants of an algorithm (which should not be done through optional parameters). Drawing that distinction might simplify the use of these algorithms.
I think that's definitely a good idea. While it's not really an implementation issue, documenting functions, they're types, and concept requirements becomes ridiculously complicated when there are lots of options - especially if those options actually control the behavior of the algorithm.
I don't know... maybe I'm thinking too hard. Building a version of BGL2 based on the current code base (or whatever's in sandbox) is just as good a summer project.
I think we're just envisioning different "final products" for BGLv2, because we use BGL for different things. Today, I happen to be working with VTK, which has a new vtkGraph data type. They provide the appropriate graph_traits specializations, free functions, etc. so that a pointer to a vtkGraph (vtkGraph*) works off-the-shelf in BGL algorithms: no wrappers required. That's exactly the kind of thing that I believe the BGL excels at, and I think it's important for future revisions of the BGL to support that use case. There's a lot of cruft I'd like to eliminate---non-partial-specialization hacks, the property<...> class, etc.---and bits that I'd like to clean up--- property map creation is too hard, adjacency_list has too many knobs only useful in rare circumstances, etc.---but I think, fundamentally, the Graph concepts are just about right.
I can see (from my previous comments) why you'd think we're talking about different final products, which probably means that I did a poor job communicating my ideas :) I'm starting to see the BGL as three distinct libraries: the generic interface (concepts), the algorithms (based on concepts) and some graph type implementations. The changes to the latter two (algorithms and types) that I'm kicking around don't (or shouldn't) necessitate changes to the generic interface. It actually sounds like your cruft isn't too different than what I'm actually envisioning. I just want to put a little more focus on designing the class interface as a refinement of the generic interface. After all, STL containers provide coherent, usable interfaces as refinements of the concepts that enable the STL algorithms. I definitely agree with your list of things that need to be worked on... I'm not entirely sure of the best way to solve some of them. Maybe this summer would be a good time to experiment with some alternative designs since removing much of the cruft could potentially obsolete legacy BGL code - at least the declarations of graph types; probably not generic code. Getting rid of the property<> class will break the classes I wrote last summer :) Besides, new designs might give the opportunity to start thinking formally about new concepts like subgraphs and hypergraphs. I'll try to start making a coherent (and hopefully realistic) list of possible goals for the summer and their rationale. I'll try to send it up sometime in the next week or so to see if it anybody would be interested in mentoring such a proposal. Andrew Sutton asutton@cs.kent.edu

Andrew Sutton a écrit :
I've been thinking about Boost.Graph v2. I was hoping to finish the work that I started in the fall. Of course, I was hoping for a little more free reign with the interfaces for this work - source compatibility won't be high on my list of priorities in my proposal.
If I may suggest one item that is on my wish list for such a new version, I would really appreciate if the visitor concepts were expanded in a way that allowed to stop exploration in one direction on graph specific conditions. This might be achieved by having the "Discover Vertex" or "Examine Edge" have a return value. Regards, -- Loïc

On Mar 2, 2008, at 4:12 AM, John Maddock wrote:
GSOC 2008 is on: http://code.google.com/soc/2008/
If folks have ideas for potential projects then now would be a good time to start thinking about them - that way we can apply to Google to be a mentoring organisation with a good selection of ideas already up and running.
A project idea: "porting" Boost to C++0x, providing alternative (= better, simpler, faster, etc) implementations of core Boost libraries by making use of C++0x features like variadic templates, rvalue references, and decltype. - Doug

Doug Gregor a écrit :
A project idea: "porting" Boost to C++0x, providing alternative (= better, simpler, faster, etc) implementations of core Boost libraries by making use of C++0x features like variadic templates, rvalue references, and decltype.
I think it would be a wonderful idea, but do you think that the language itself, and the available compilers, are stable enough to allow for such an operation now ? Is that why you omit concepts in your feature list ? Regards, -- Loïc Joly

On Mar 3, 2008, at 3:01 PM, Loïc Joly wrote:
Doug Gregor a écrit :
A project idea: "porting" Boost to C++0x, providing alternative (= better, simpler, faster, etc) implementations of core Boost libraries by making use of C++0x features like variadic templates, rvalue references, and decltype.
I think it would be a wonderful idea, but do you think that the language itself, and the available compilers, are stable enough to allow for such an operation now ?
GCC 4.3 should be released in a few weeks, with decent support for those features. So, I think we can get started exercising those features in Boost, both to help squish the bugs in GCC and to entice other compiler vendors to start supporting these features.
Is that why you omit concepts in your feature list ?
Yes. ConceptGCC is buggy enough to prevent serious implementations of Boost at this time, and I'm most interested in getting the best use out of the C++0x features we have in released (or soon-to-be-released) compilers. - Doug

On Mar 2, 2008, at 4:12 AM, John Maddock wrote:
GSOC 2008 is on: http://code.google.com/soc/2008/
If folks have ideas for potential projects then now would be a good time to start thinking about them - that way we can apply to Google to be a mentoring organisation with a good selection of ideas already up and running.
I've started a page on the wiki with ideas for potential projects, here: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summer... We'll also need Boosters willing to mentor GSoC students. John, was it you who sent in the actual organization application last year? - Doug
participants (10)
-
Andrew Sutton
-
David Abrahams
-
Doug Gregor
-
Douglas Gregor
-
John Maddock
-
Jonathan Franklin
-
Loïc Joly
-
Michael Fawcett
-
Sebastian Redl
-
Stephen Nuchia