D graph library

[Joseph Rushton Wakeling]

On 05/23/2013 01:55 AM, H. S. Teoh wrote:
> The algorithms themselves, of course, will obviously be geared toward
> these data types, but where possible, they should be made generic so
> that other data types satisfying the required APIs will be usable with
> them. So I think writing them as templates parametrized on input graph
> type (with signature constraints to ensure the type is usable with the
> algorithm) would be the way to go.

Another possibility is to have the algorithm extract the preferred data
structure from the underlying type, and we could probably do very good things
with compile-time constraints here.

For example, as I mentioned in another email, the igraph data type is
essentially just a list of links.  Their implementation of betweenness
centrality constructs an adjacency list internally in order to do the
calculation.  My guess is that there are some tradeoffs to do with scale that
make this worthwhile for them.

What _we_ can do, though, is have a compile time check for whether a particular
graph data type has an adjacency-list interface or not -- if so, it can be used;
if not, an adjacency list can be constructed; and we could also construct
"wrapping" data structures that layer on additional interfaces (e.g. the basic
graph type might just be a list of links, we could wrap an adjacency list around
that, and so on).

> And since the algorithms themselves will be templates, if the library
> exports, say, BipartiteGraph, then that can be a dedicated bipartite
> graph type that doesn't need to have any relation (though it could if it
> improves the implementation) to more general graph types. Some
> optimizations specific to bipartite graphs can be used in the
> implementation, for example.

Indeed, and alternatively or additionally we could implement a bipartite graph
type as a wrapper around the basic graph model, which might first check that any
existing graph is indeed bipartite and then give a bipartite-friendly external API.