Graph abstractions

[pnevyk]

Prepona was a huge inspiration in separating the graph abstraction from graph data storage. The question is how should we approach that to benefit from this separation to its fullest, but keeping the usage and API as convenient as possible.

Kind of obvious cases are having simple graph and multigraph. Somewhat orthogonally allowing and disallowing self-loops. Should we have four structs (LoopFreeSimpleGraph, SimpleGraph, LoopFreeMultiGraph, MultiGraph or is there a different, more flexible approach to tackle this (a marker type, constructor argument)?

Another level would be having graph types that would guarantee some certain property, like BipartiteGraph, TreeGraph, ConnectedGraph. This information may be exploited by using a simpler and faster algorithm that works only on certain classes of graph. There would be possibly some kind of indirection through traits (Bipartite, Tree, ...), which would be required by the algorithms, so that different implementations of the same property can be used.

There may be also tricks like starting with a sparse-friendly storage and switching to a dense one once the edge/vertex ratio exceeds a threshold.

Any other ideas?

[pnevyk]

The loop question might be approached with a marker type and a "property" trait. Similarly to EdgeType marker type, there could be a Loops marker type (with WithLoops, WithoutLoops) and there would be such an impl:

impl<...> LoopFree for SimpleGraph<..., WithoutLoops> {}

Or consts generics could be used having const Loops: bool and using SimpleGraph<..., false>.

Generally, there could be simply a set of property traits:

• LoopFree
• Bipartite, Tree, ...
• Finite (see Implicit graphs #3 )
• ...

(The naming in this comment is completely ad hoc)

[pnevyk]

Progress has been made in 4ae82fa and 42616e4.

The Guarantee trait is supposed to contain all interesting properties a graph can have (it is expected to grow throughout time). The properties must be such that it is always safe (in a sense of algorithms correctness) to return false as a default. In other words, if a property returns false, that should not break any algorithm. Essentially, a property is an additional guarantee over a general graph.