search

pnevyk / gryf

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

Graph operations #4

Closed pnevyk closed 1 year ago

pnevyk commented 3 years ago

There should be a module which provides various standard graph operations like edge contraction, graph complement, intersection, union, etc. These don't require any special support from the underlying storage and thus can be generic. There should be probably also standard traits which would be implemented by these operations (similar to std::ops).

Things to consider:

pnevyk commented 2 years ago

These operations may be lazy as are adapters in std::iter fore example. In most cases, implementing graph traits for these adapters should not cause too much overhead. Anyway, it would be always possible to materialize ("collect") the adapters into a concrete graph storage.

pnevyk commented 2 years ago

First example (complement) implemented in 5db59b524bebf49a3027839ce6cfbdb1c78dbdb9.

pnevyk commented 1 year ago

Operations moved to adapt module in #69. I also removed the Op* traits, because they probably did not bring any value and the hack with C = () generic parameter was hacky.

I am going to close this issue, because there is a precedent for an operation type, and now it remains to add operations that are missing.