stdgraph
No graph rewriting support
It looks to me that this library does not intend to offer algorithms (and therefore concepts) that would mutate the topology of graphs. Is this correct? Are these outside the scope of this library?
That's an area I was staying away from initially. It's an area that needs attention eventually.
Sent from Outlookhttp://aka.ms/weboutlook
From: Andrzej Krzemieński @.> Sent: Tuesday, June 24, 2025 3:26 PM To: stdgraph/graph-v2 @.> Cc: Subscribed @.***> Subject: [stdgraph/graph-v2] No graph rewriting support (Issue #171)
[https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 created an issue (stdgraph/graph-v2#171)https://github.com/stdgraph/graph-v2/issues/171
It looks to me that this library does not intend to offer algorithms (and therefore concepts) that would mutate the topology of graphs. Is this correct?
— Reply to this email directly, view it on GitHubhttps://github.com/stdgraph/graph-v2/issues/171, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB7NKEUQXHEXQ35USRNJP4T3FGQ6FAVCNFSM6AAAAACABIOVASVHI2DSMVQWIX3LMV43ASLTON2WKOZTGE3TGMBVGA4DOOI. You are receiving this because you are subscribed to this thread.Message ID: @.***>
I think this needs to be addressed, at least partially, in the initial release. Currently concepts are "optimized" for the non-modifying case. I predict that the same concepts would look quite different when we take graph rewriting into the scope.
The current design reflects the existing containers and algorithms in the STL. Algorithms will do something, typically given a range, and return a result without modifying the underlying container. General container mutation in the STL is limited to back_inserter, front_inserter and inserter (did I miss any?). Graphs can take many forms, so coming up with a general way to do that needs to be done carefully. That doesn't mean that it can't be done.
My first question is whether those existing adaptors can be used on vertices and edges. If not, then what are the requirements for them? From that, concepts might be derived.
My focus for over 5 years has been to get algorithms working for graphs without mutation, so I see myself focused on that for now, until things are more stable and fully functional. A better set of documentation is also important (thanks for your contributions so far).
That said, I also strongly believe that the design shouldn't box us in, but should be able to adapt to future needs. Support for vertices in a map for sparse vertex ids is one example. I also feel strongly that vertex ids shouldn't have to be integral (I can give examples). Supporting mutable algorithms can be another area. I think it's important to understand mutability requirements so they can help guide a good design and be communicated to others.
What are the use-cases for mutability beyond those supplied by the back_inserter, front_inserter and inserter adaptors? What are algorithm examples that require a mutable graph? Is the existing approach for passing a function object that returns a reference to a property sufficient for properties? (An important design decision has been to avoid the property maps in boost::graph.)
Sent from Outlookhttp://aka.ms/weboutlook
From: Andrzej Krzemieński @.> Sent: Wednesday, June 25, 2025 7:33 AM To: stdgraph/graph-v2 @.> Cc: Phil Ratzloff @.>; Comment @.> Subject: Re: [stdgraph/graph-v2] No graph rewriting support (Issue #171)
[https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 left a comment (stdgraph/graph-v2#171)https://github.com/stdgraph/graph-v2/issues/171#issuecomment-3004442648
I think this needs to be addressed, at least partially, in the initial release. Currently concepts are "optimized" for the non-modifying case. I predict that the same concepts would look quite different when we take graph rewriting into the scope.
— Reply to this email directly, view it on GitHubhttps://github.com/stdgraph/graph-v2/issues/171#issuecomment-3004442648, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB7NKEUXOHMRYHOOS77AQB33FKCKBAVCNFSM6AAAAACABIOVASVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTAMBUGQ2DENRUHA. You are receiving this because you commented.Message ID: @.***>