Skip to content

Instantly share code, notes, and snippets.

@dineshdharme

dineshdharme/Suggestion.py

Created March 31, 2024 08:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dineshdharme/026fe4e7096c0f67f3b45c6fc1fa160f to your computer and use it in GitHub Desktop.
Save dineshdharme/026fe4e7096c0f67f3b45c6fc1fa160f to your computer and use it in GitHub Desktop.
Download ZIP
Rooted Minimum Spanning Tree in a Directed Graph.
Raw
Suggestion.py
https://stackoverflow.com/questions/78244909/graphframes-pyspark-route-compaction/78248893#78248893
You can possibly use
networkx's Edmond's algorithm to find minimum spanning arborescence rooted at a particular root in a given directed graph.
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.branchings.Edmonds.html
In graph theory, an arborescence is a directed graph having a distinguished vertex u (called the root) such that, for any other vertex v, there is exactly one directed path from u to v.
In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment