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.82k stars 96 forks source link

Has graph supported finding all paths between Vertex A and Vertex B ？ #59

Closed evanscat closed 2 years ago

dominikbraun commented 2 years ago

No, at the time being, graph only supports finding the shortest path between two vertices. Finding all paths efficiently is one of the hardest problems in graph theory.

If you can specialize your use case with a framework of assumptions that are safe to make, you can implement your own path search using BFS or DFS - but providing a built-in function in the library that works for all use cases in all graphs is close to impossible. It might be easier in directed graphs, maybe I'll come up with an algorithm for this in the future.

evanscat commented 2 years ago

We use graph in power grid topological analysising. The graph among power grid are always DAG and the most common use case is to find all power supply path. I'll use BFS or DFS to implement my own algorithm.Thanks a lot!

dominikbraun commented 2 years ago

Thanks! If you want to further share your use cases or need guidance, just reach out.