To those interested, // sorrt Alas summer is over. and the students have returned to clog the hallowed (and somewhat narrow) halls of my building... No more quiet days in my lab hacking out Boost.Graph code and documentation. On the brighter side, I have finished - at least to the satisfaction of mentor Jeremy Siek and myself - the goals that I had originally planned for my Summer of Code project. The end results are: - Two new graph classes (undirected and directed) which are intended to make the library more approachable for new developers - A suite of graph measures including degree and closeness centrality, mean geodesic distance, eccentricity, and clustering coefficients. - An algorithm for visiting all cycles in a directed graph (Tiernan's from 1970ish). It works for undirected graphs too, but reports cycles twice (one for each direction). - An algorithm for visiting all the cliques a graph (Bron&Kerbosch). Works for both directed and undirected. - Derived graph measures radius and diameter (from eccentricity) and girth and circumference (from Tiernan), and clique number (from Bron&Kerbosch). - An exterior_property class that helps hides some of the weirdness with exterior properties. - A constant-valued property map - useful for naturally unweighted graphs. - A noop-writing property map - useful when you have to provide an argument, but just don't care about the output. There are also a couple of other informal introductions that need to be polished, documented and tested. These include: - Graph cores - Implemented by David Gleich (@Stanford University) - Deterministic graph generators - capable of creating or inducing specific types of graphs over a vertex set (e.g., star graph, wheel graph, prism graph, etc). There are several other specific types that could be added to this, but I haven't had the time just yet. There are also some introductions in this package that can - or probably should be - backported to existing code. Specifically, issues dealing with vertex and edge indices and how they are mapped into exterior properties. There are also a couple of changes to the current codebase that can be immediately applied. Specifically, this includes new and updated concept checking classes and a completely new archetype system for concept coverage testing. I've also written quickbook docs for much of the new code - and have been slowly folding the older docs in - it's a long process. Also, if you aren't on a Linux box, you can't build the new docs since I'm using Makefiles, graphviz and latex to generate images. So, the up-to- date stuff is here: http://warhol.sdml.cs.kent.edu/~asutton/boost/libs/graph/doc/html/ Most of the "good" docs are toward the bottom of the ToC. I have more to say on the topic, but I will split it into a second email since this is pretty long. Andrew Sutton asutton@cs.kent.edu
To those interested, // sorrt
Oops... accidental pasting.
I have more to say on the topic, but I will split it into a second email since this is pretty long.
Since my SoC package constitutes a significant addition to the Boost.Graph library, Jeremy and I felt that it would benefit from the formal review process - especially the newer code that is concerned with the library interface. However, we're unsure if the review needs the same formality as a completely new library since this is, as mentioned, a (albeit rather large) change to an existing library. An alternate idea might be to take these changes and any new Boost.Graph algorithms in the vault as a single introduction. This could include: - the planar graph suite - cycle ratio code - floyd-warshall (new params) A third option - and actually not a terrible idea - would be to branch the Boost.Graph trunk, perform the integration and then do some serious housekeeping like cleaning up tests, examples, documentations, making sure the interface is clean and consistent, and - god forbid - putting Boost.Graph into boost::graph. The more I think about it, the more I'm becoming a fan of the third option. Unfortunately, it's also a fairly large chunk of work and would take a serious commitment from the developer(s) working on it. Any thoughts? Andrew Sutton asutton@cs.kent.edu
Andrew Sutton wrote:
To those interested, // sorrt
Oops... accidental pasting.
I have more to say on the topic, but I will split it into a second email since this is pretty long.
Since my SoC package constitutes a significant addition to the Boost.Graph library, Jeremy and I felt that it would benefit from the formal review process - especially the newer code that is concerned with the library interface. However, we're unsure if the review needs the same formality as a completely new library since this is, as mentioned, a (albeit rather large) change to an existing library.
An alternate idea might be to take these changes and any new Boost.Graph algorithms in the vault as a single introduction. This could include:
- the planar graph suite - cycle ratio code - floyd-warshall (new params)
A third option - and actually not a terrible idea - would be to branch the Boost.Graph trunk, perform the integration and then do some serious housekeeping like cleaning up tests, examples, documentations, making sure the interface is clean and consistent, and - god forbid - putting Boost.Graph into boost::graph.
The more I think about it, the more I'm becoming a fan of the third option. Unfortunately, it's also a fairly large chunk of work and would take a serious commitment from the developer(s) working on it.
Any thoughts?
Both having a review process and doing housekeeping on a branch seem worthwhile. I personally don't think the review has to be as formal as for a new library, but should follow the same basic procedure; it should be announced ahead of time, all the material should be available at an accessible location, it should run for 10 days or so, etc. Rather than having a review manager as such, perhaps Jeremy and Doug could moderate. As far as a branch goes, we would like to keep the trunk more stable than in the past. So for a major change that might involve some instability for awhile, a branch sounds like a good idea until the changes stablize. --Beman
On Aug 27, 2007, at 12:33 PM, Andrew Sutton wrote:
Since my SoC package constitutes a significant addition to the Boost.Graph library, Jeremy and I felt that it would benefit from the formal review process - especially the newer code that is concerned with the library interface. However, we're unsure if the review needs the same formality as a completely new library since this is, as mentioned, a (albeit rather large) change to an existing library.
I agree with Beman... I don't think we need a full formal review, but something like it would be useful.
An alternate idea might be to take these changes and any new Boost.Graph algorithms in the vault as a single introduction. This could include:
- the planar graph suite - cycle ratio code - floyd-warshall (new params)
Planar graphs and the cycle ratio code are already in Subversion (?)
A third option - and actually not a terrible idea - would be to branch the Boost.Graph trunk, perform the integration and then do some serious housekeeping like cleaning up tests, examples, documentations, making sure the interface is clean and consistent, and - god forbid - putting Boost.Graph into boost::graph.
This is the kind of thing that we really, really, really wanted to do as part of the "Boost.Graph version 2". We'd also like to jettison the current BGL named parameters mechanism to use the parameter library, and also work to update the documentation from crusty old HTML to Quickbook (which I think the IBD project has started doing?). We have a few interface improvements and a bunch of bug fixes in the Parallel BGL that could also make their way into this branch... The big question, of course, is whether we can dedicate enough time to make this happen. I can spare a few cycles until mid-October, after which I hope my schedule will free up a bit to work on the BGL. - Doug
An alternate idea might be to take these changes and any new Boost.Graph algorithms in the vault as a single introduction. This could include:
- the planar graph suite - cycle ratio code - floyd-warshall (new params)
Planar graphs and the cycle ratio code are already in Subversion (?)
I just noticed that, and will retract the suggestion :)
This is the kind of thing that we really, really, really wanted to do as part of the "Boost.Graph version 2". We'd also like to jettison the current BGL named parameters mechanism to use the parameter library, and also work to update the documentation from crusty old HTML to Quickbook (which I think the IBD project has started doing?). We have a few interface improvements and a bunch of bug fixes in the Parallel BGL that could also make their way into this branch...
The big question, of course, is whether we can dedicate enough time to make this happen. I can spare a few cycles until mid-October, after which I hope my schedule will free up a bit to work on the BGL.
I'm more than willing to spend some serious time working on Boost.Graph this semester - It won't be as much as I spent this summer, but at least a couple days a week. Besides, the person working on Boost docs for IBD was me. Unfortunately, I've only taken a quick look at pBGL so I don't know too much about it. Those improvements would have to be pointed out. Andrew Sutton asutton@cs.kent.edu
On Thu, 2007-08-30 at 22:07 -0400, Andrew Sutton wrote:
I'm more than willing to spend some serious time working on Boost.Graph this semester - It won't be as much as I spent this summer, but at least a couple days a week.
Great! I am, of course, willing to spend what time I can on this long-overdue project.
Besides, the person working on Boost docs for IBD was me.
I should have known that :)
Unfortunately, I've only taken a quick look at pBGL so I don't know too much about it. Those improvements would have to be pointed out.
Sure. The one major improvement that we're working on in the pBGL that's also useful for the BGL is the "named vertices" extension to graphs. The basic idea is very simple: if the vertex property somehow contains a "name" buried inside it, we can use that name as an alternative way to refer to the vertex. For example, say we have a City structure that we attach to each vertex: struct City { City() {} City(const std::string& name, int population = -1) : name(name), population(population) { } std::string name; int population; }; If we tell the BGL that the "name" field of the City structure is the name of the corresponding vertex, then graphs will now allow us to refer to cities by name: typedef adjacency_list<...> RoadMap; RoadMap road_map; Vertex bloomington = add_vertex(City("Bloomington", 69291), map); Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map); Vertex chicago = add_vertex(City("Chicago", 9500000), map); add_edge(bloomington, "Indianapolis", map); add_edge("Indianapolis", chicago, map); add_edge("Indianapolis", "Cincinatti", map); The graph handles the mapping from names like "Indianapolis" to vertex descriptors, even adding vertices when no such vertex exists (as is the case for "Cincinatti"). How many times have users had to create and maintain an std::map<std::string, vertex_descriptor> to do this same thing? Too many, in my opinion. - Doug
Besides, the person working on Boost docs for IBD was me.
I should have known that :)
Well, the docs aren't exactly the most visible in the world - they're buried in my SoC directory - and for some reason, I can't build them anymore.
Sure. The one major improvement that we're working on in the pBGL that's also useful for the BGL is the "named vertices" extension to graphs. The basic idea is very simple: if the vertex property somehow contains a "name" buried inside it, we can use that name as an alternative way to refer to the vertex. For example, say we have a City structure that we attach to each vertex:
The graph handles the mapping from names like "Indianapolis" to vertex descriptors, even adding vertices when no such vertex exists (as is the case for "Cincinatti").
How many times have users had to create and maintain an std::map<std::string, vertex_descriptor> to do this same thing? Too many, in my opinion.
How true :) That's a great idea. It sounds like the approach is actually similar to my idea for weighted graphs, albeit for a very different purpose. I think there are a couple of nice concepts in here somewhere. I'd actually like to take a whack at getting some of this work started. I may even be able to find a couple of other students who would be willing to help (it's a strong maybe). If you're interested, I can create a branch in the sandbox and start writing up a laundry list. Andrew Sutton asutton@cs.kent.edu
On Aug 31, 2007, at 9:36 AM, Andrew Sutton wrote:
How many times have users had to create and maintain an std::map<std::string, vertex_descriptor> to do this same thing? Too many, in my opinion.
How true :) That's a great idea. It sounds like the approach is actually similar to my idea for weighted graphs, albeit for a very different purpose. I think there are a couple of nice concepts in here somewhere.
Agreed.
I'd actually like to take a whack at getting some of this work started. I may even be able to find a couple of other students who would be willing to help (it's a strong maybe). If you're interested, I can create a branch in the sandbox and start writing up a laundry list.
Yes, please go ahead and create a branch. We probably want to treat this more like a sandbox library (with sandbox layout), where the boost/graph and libs/graph subdirectories are branches off the trunk's boost/graph and libs/graph. In this case, we might as well just put it in the sandbox: sandbox/projects/graph-v2 - Doug
Yes, please go ahead and create a branch. We probably want to treat this more like a sandbox library (with sandbox layout), where the boost/graph and libs/graph subdirectories are branches off the trunk's boost/graph and libs/graph. In this case, we might as well just put it in the sandbox:
sandbox/projects/graph-v2
There doesn't seem to be a projects directory in the sandbox, so I just created a new top-level graph-v2 directory in the sandbox. Apparently, I need a full checkout of the full repository to branch it - it looks like copying across repos won't work. This may take a while. Andrew Sutton asutton@cs.kent.edu
There doesn't seem to be a projects directory in the sandbox, so I just created a new top-level graph-v2 directory in the sandbox. Apparently, I need a full checkout of the full repository to branch it - it looks like copying across repos won't work. This may take a while.
Apparently, it didn't take quite so long as I thought. I've branched both Boost.Graph and Boost.PropertyMap into the graph-v2 library. Since the two libraries are so closely relatd (and PropertyMap is kind of small), I figured we might do for PropertyMap at the same time - besides, I have an addition or two for it. It's all here: http://svn.boost.org/svn/boost/sandbox/graph-v2 I'll start working on the laundry list over the weekend and post it back here. Maybe I could turn it into trac tickets. Andrew Sutton asutton@cs.kent.edu
On Aug 31, 2007, at 12:53 PM, Andrew Sutton wrote:
Apparently, it didn't take quite so long as I thought. I've branched both Boost.Graph and Boost.PropertyMap into the graph-v2 library. Since the two libraries are so closely relatd (and PropertyMap is kind of small), I figured we might do for PropertyMap at the same time - besides, I have an addition or two for it.
It's all here:
Thanks!
I'll start working on the laundry list over the weekend and post it back here. Maybe I could turn it into trac tickets.
I've added a Trac page here: http://svn.boost.org/trac/boost/wiki/GraphVersion2 - Doug
I've added a Trac page here:
That's probably a much better place to start building a TODO list. I'll post it there. Hopefully it will turn into some kind of coherent plan of action. Andrew Sutton asutton@cs.kent.edu
on Thu Aug 30 2007, Douglas Gregor <doug.gregor-AT-gmail.com> wrote:
On Aug 27, 2007, at 12:33 PM, Andrew Sutton wrote:
Since my SoC package constitutes a significant addition to the Boost.Graph library, Jeremy and I felt that it would benefit from the formal review process - especially the newer code that is concerned with the library interface. However, we're unsure if the review needs the same formality as a completely new library since this is, as mentioned, a (albeit rather large) change to an existing library.
I agree with Beman... I don't think we need a full formal review, but something like it would be useful.
In particular, I don't think votes for or against acceptance would be appropriate here. Doug, there is a Trac peer review plugin you might want to think about installing. http://trac-hacks.org/wiki/PeerReviewPlugin -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com
Andrew Sutton wrote:
http://warhol.sdml.cs.kent.edu/~asutton/boost/libs/graph/doc/html/
Wasn't there an predecessor _edge_ recorder as well?
participants (6)
-
Andrew Sutton -
Beman Dawes -
David Abrahams -
Doug Gregor -
Douglas Gregor -
Jens Müller