D graph library

[Joseph Rushton Wakeling]

On 05/10/2013 07:52 PM, H. S. Teoh wrote:
> I suppose we can make it an optional thing, such that algorithm A may
> ask for only an InputRange (and a graph with bidirectional range of
> nodes will still work) but algorithm B may ask for more, say a
> ForwardRange or RandomAccessRange. Each algorithm will require the
> minimum necessary to perform efficiently (though of course it can be
> special-cased to take advantage of additional features of a higher
> range, if that is available in a given instantiation).

Yes, algorithms should certainly ask for no more than they need.

> In fact, now that I think of it... most of the features you listed can
> arguably be optional: only a few algorithms (none that I know of,
> actually) require enumeration of edges, some algorithms may only require
> an input range of nodes, each of which gives an input range of edges,
> etc.. Would it make sense to define a set of graph properties (e.g., via
> templates ala std.range.is{Input,Forward,Bidirectional,...}Range, or
> hasLength, hasSwappableElements, etc.), and have each algorithm require
> whatever minimal subset of them is necessary to do the work? Because it
> makes little sense to require, say, a graph that returns a total count
> of nodes, if a given algorithm never needs to use that information
> anyway. This way, a structure for which the total number of nodes is
> expensive to compute can still be used with that algorithm.

That's a fair point.  I don't know that I like the idea of defining all those
different kinds of checks for different graph attributes, though.

> Not if the graph is computed on-the-fly. E.g. chess analysis
> applications in which the complete graph is infeasible to compute.

Well, it ought still to be possible to define a range -- albeit, not a
random-access one -- that covers all the edges in that graph.  It's just that
it'll take forever to finish.

Agree though that this is a case where an edges() property is probably not
desirable.

> In that case, I wonder if it's even necessary to unify the two graph
> types. Why not just have two separate types and have the type system
> sort out compatibility with algorithms for us?

That might be a possible solution, but whether directed or undirected (or
mixed), a graph will broadly have the same general public interface.

> Are there any algorithms that need to do something different depending
> on whether the input graph is bipartite or not? Just wondering if it's
> worth the trouble of introducing an additional field (it may well be
> necessary -- I admit my knowledge of graph algorithms is rather spotty).

Put it this way: sometimes, you might want to check if a graph _is_ bipartite,
that is, if its nodes can be divided into two disjoint sets A and B such that
links in the graph are always between nodes in the different sets, never between
nodes from the same set.  That could be a runtime test that you could apply to
any graph.

Then again, you might deliberately want to construct an explicitly bipartite
graph, and you might want to have checks and balances in place to make sure that
you don't accidentally add nodes between nodes in the same set.

> Right. Which brings me back to my idea that perhaps these graph
> properties should be optional, or perhaps we should have some kind of
> hierarchy of graph types (ala input range, forward range, bidirectional
> range, etc.), so that individual algorithms can choose which features
> are mandatory and which are optional.
> 
> (I really dislike algorithms that are artificially restricted just
> because the author decided that feature X is required, no matter if the
> algorithm doesn't even use it.)

Fair point.  _Algorithms_ should require the minimal number of constraints.
Most of my suggestions for range types etc. represent what I think is useful for
a general-purpose graph data type rather than what is absolutely necessary for
individual specialized applications.

Must dash again, so will catch up on your other points later ... ! :-)