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.
