search

pnevyk / gryf

Graph data structure library aspiring to be convenient, versatile, correct and performant.
MIT License
69 stars 1 forks source link

Graph abstractions #1

Open pnevyk opened 3 years ago

pnevyk commented 3 years ago

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 commented 3 years ago

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:

(The naming in this comment is completely ad hoc)

pnevyk commented 2 years ago

Progress has been made in 4ae82fafac4ef34387b30cbd56f26adbdc4acebc and 42616e453773f59bdbe7fed8ac0b7fb175bcf48d.

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.