New Algorithms

I haven't given a lot of thought to these since the semester just ended. However, I am starting to consider various type requirements for the algorithms and have spent some time playing with conceptg++. I did notice however, that there is a ticket already exists for finding cliques within a graph (#693) - even better, with links to source code. It might be worth pointing out, that the Bron and Kerbosch algorithm is written for a Boolean matrix so interpreting it for an adjacency list is a bit of a chore. I haven't actually read the other algorithm yet, hopefully it's promising.

(Jeremy: btw, there is a matrix-as-graph adaptor in the BGL, and it would be straightforward to provide a graph-as-matrix adaptor.)

(Andrew: True enough... I was just looking for a graph-as-matrix adpater for my rewrite of the Kevin Bacon example. Apparently, there's a little extra work to find an edge given a couple of vertices).

Update (06/06/07) I committed some files that hosted the original implementations of several computed metrics - they aren't very pretty and pretty non-boost conformant. I spent a little time renovating the degree_distribution computation.

Degree Distributions

This is actually a fairly trivial computation since we're just looking at the degree of each vertex and then building a histogram from it. As of right now, the signature basically looks like this:

template <class BidirectionalGraph, class RandomAccessContainer>
void degree_distribution(BidirectionalGraph&, RandomAccessContainer&);

That should give some ideas about the concept requirements for the parameters. Specifically, the BidirectionalGraph is required since this method calls the degree() function to compute the distribution. We also required a RandomAccessContainer since the distribution is a histogram indexed by the degree of a vertex. Incidentally, the container is required to be Resizable (preferably effeciently).

It might be worth noting that both [un]directed_graphs satisfy the requirements of this function. Only an adjacency_list templated over directedS may not be type compatible with the property.

Interestingly, we can extend this relatively simple method to a set of 3 - in_degree_distribution() and out_degree_distribution() using a similar approach.

On a side note... I lied just a little bit. The method actually returns the maximum degree in the distribution, but I've been considering changing it to return a pair containing both the minimum and the maximum. I figure, we're doing a little data gathering, lets grab some more information at essentially no cost.

Various Concept Notes

On a side note, I started codifying the Boost.Graph graph concepts into a concepts header just to see if I could make it work - I haven't succeeded yet. Still, it's a good excercise and makes you think about concept hierarchies, nested requirements and the like. Also, i don't like the keyword concept_map. Not the idea itself - the keyword. If I'm not mistaken, this keyword replaces model from earlier proposals. Alas...

(Jeremy: very cool! Yes, the concept_map keyword royally sucks. It turned out that model was already used in tons of C++ code, so we'd break that code if we turned model into a keyword.)

(Andrew: I was wondering about that... what about the word binding or something similar. Conceptually, it seems to match since you're "binding" additional code onto an exsiting type so that it models a concept. The only downside might be that it overloads the UML terminology for template instantiation. Maybe a syntactic trick like template specialization.)

Since I've been codigying graph concepts, I should point out that IncidenceGraph and EdgeListGraph both define source() and target() methods, so they're a little redundant. I think it would be appropriate to remove those methods from the requirements of EdgeListGraph since they don't really have anything to do with the listing or enumerating of edges. Just a thought...

(Jeremy: actually, source() and target() are pretty important to that concept. It would be better to refactor them into a common base concept.)

(Andrew: Yeah, I figured that out a couple hours later. A slight refactoring might be in order.)