search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.8k stars 94 forks source link

depth info in TopologicalSort #123

Closed williamfzc closed 1 year ago

williamfzc commented 1 year ago

Hi :) This is a discussion.

While TopologicalSort is the appropriate API for our needs, it has a limitation in that the depth information of the nodes cannot be easily represented by a single slice. This can make it challenging to determine which nodes belong to which level after obtaining the sorted slice.

Are there any existed methods I have missed?

dominikbraun commented 1 year ago

Hi! One question upfront: Would it be feasible for you to store the depth information as a vertex attribute, or would that be too much manual effort?

williamfzc commented 1 year ago

Yes I agree. Currently what we want is, walking the whole graph, and getting and storing these depth informations to vertex attributions.

Both BFS and DFS require an initial node and cannot traverse the entire graph. In comparison, Topological Sort seems more appropriate.

dominikbraun commented 1 year ago

@williamfzc Ok, but I'm planning to add methods for running a DFS und BFS over the entire graph, not just over the nodes that are reachable from the start vertex. I've opened #124 for this.

williamfzc commented 1 year ago

@williamfzc Ok, but I'm planning to add methods for running a DFS und BFS over the entire graph, not just over the nodes that are reachable from the start vertex. I've opened #124 for this.

Good idea and lets continue in #124

dominikbraun commented 1 year ago

Maybe #61 could also be interesting in this context.