Add minimum steiner tree function #389
Labels
enhancement
New feature or request
Comments
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jul 20, 2021
This commit adds a metric closure function to retworkx. The metric closure of a graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in the graph. This is the first step towards implementing the minimum steiner graph function because the first step for that is to compute the metric closure for the graph. Additionally, this function is entirely self contained to a new rust module steiner_tree.rs (which we'll eventually add the steiner_tree() function too) in the interest of showing the eventual organizational structure we want for Qiskit#300 (although having an algorithms namespace might make sense for Qiskit#300). In a separate PR addressing Qiskit#300 we should start to reorganize the rust code in lib.rs like this to make things easier to find. Partially implements Qiskit#389
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jul 20, 2021
This commit adds a metric closure function to retworkx. The metric closure of a graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in the graph. This is the first step towards implementing the minimum steiner graph function because the first step for that is to compute the metric closure for the graph. Additionally, this function is entirely self contained to a new rust module steiner_tree.rs (which we'll eventually add the steiner_tree() function too) in the interest of showing the eventual organizational structure we want for Qiskit#300 (although having an algorithms namespace might make sense for Qiskit#300). In a separate PR addressing Qiskit#300 we should start to reorganize the rust code in lib.rs like this to make things easier to find. Partially implements Qiskit#389
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jul 20, 2021
This commit adds a metric closure function to retworkx. The metric closure of a graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in the graph. This is the first step towards implementing the minimum steiner graph function because the first step for that is to compute the metric closure for the graph. Additionally, this function is entirely self contained to a new rust module steiner_tree.rs (which we'll eventually add the steiner_tree() function too) in the interest of showing the eventual organizational structure we want for Qiskit#300 (although having an algorithms namespace might make sense for Qiskit#300). In a separate PR addressing Qiskit#300 we should start to reorganize the rust code in lib.rs like this to make things easier to find. Partially implements Qiskit#389
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jul 20, 2021
This commit adds a metric closure function to retworkx. The metric closure of a graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in the graph. This is the first step towards implementing the minimum steiner graph function because the first step for that is to compute the metric closure for the graph. Additionally, this function is entirely self contained to a new rust module steiner_tree.rs (which we'll eventually add the steiner_tree() function too) in the interest of showing the eventual organizational structure we want for Qiskit#300 (although having an algorithms namespace might make sense for Qiskit#300). In a separate PR addressing Qiskit#300 we should start to reorganize the rust code in lib.rs like this to make things easier to find. Partially implements Qiskit#389
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jul 20, 2021
This commit adds a new method, edge_subgraph(), to the PyGraph and PyDiGraph classes for generating a edge induced subgraph from a graph object. Related to Qiskit#389
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jul 20, 2021
This commit adds a function to find an approximation of the minimum Steiner tree using the algorithm described in "A fast algorithm for Steiner tree" Kou, Markowsky & Berman (1981). https://link.springer.com/article/10.1007/BF00288961 This algorithm produces a tree whose weight is within a (2 - (2 / t)) factor of the weight of the optimal Steiner tree where t is the number of terminal nodes. Closes Qiskit#389
4 tasks
|
After reading the original paper, it seems that some steps in the original algorithm are missing from NetworkX function (steps 4 and 5 to be specific). I tried to find an example that breaks the function but couldn't find any. Depending on how you choose the minimum spanning tree in step 3, steps 4 and 5 might be unnecessary. Although you have almost done all the work in #392, i mention here for future reference that there is a similar algorithm with the same approximation ratio but better runtime complexity (https://people.mpi-inf.mpg.de/~mehlhorn/ftp/SteinerTrees.pdf). |
mtreinish
added a commit
that referenced
this issue
Aug 4, 2021
* Add metric closure function This commit adds a metric closure function to retworkx. The metric closure of a graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in the graph. This is the first step towards implementing the minimum steiner graph function because the first step for that is to compute the metric closure for the graph. Additionally, this function is entirely self contained to a new rust module steiner_tree.rs (which we'll eventually add the steiner_tree() function too) in the interest of showing the eventual organizational structure we want for #300 (although having an algorithms namespace might make sense for #300). In a separate PR addressing #300 we should start to reorganize the rust code in lib.rs like this to make things easier to find. Partially implements #389 * Move docs to Other Algorithms section * Fix allocation size for output vector * Rework disconnected graph logic The previous check for a disconnected graph only caught graphs with completely disconnected nodes and didn't detect all disconnected graphs. This commit fixes the logic by check the first node in the graph has a path to all other nodes. * Fix handling of empty graph to not overflow * Update src/lib.rs Co-authored-by: Ivan Carvalho <[email protected]> * Rework final loop to be over hashmap instead of indices Co-authored-by: Ivan Carvalho <[email protected]>
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Aug 4, 2021
This commit adds a function to find an approximation of the minimum Steiner tree using the algorithm described in "A fast algorithm for Steiner tree" Kou, Markowsky & Berman (1981). https://link.springer.com/article/10.1007/BF00288961 This algorithm produces a tree whose weight is within a (2 - (2 / t)) factor of the weight of the optimal Steiner tree where t is the number of terminal nodes. Closes Qiskit#389
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Aug 5, 2021
This commit adds a function to find an approximation of the minimum Steiner tree using the algorithm described in "A fast algorithm for Steiner tree" Kou, Markowsky & Berman (1981). https://link.springer.com/article/10.1007/BF00288961 This algorithm produces a tree whose weight is within a (2 - (2 / t)) factor of the weight of the optimal Steiner tree where t is the number of terminal nodes. Closes Qiskit#389
mtreinish
added a commit
that referenced
this issue
Aug 9, 2021
This commit adds a new method, edge_subgraph(), to the PyGraph and PyDiGraph classes for generating a edge induced subgraph from a graph object. Related to #389
mtreinish
added a commit
that referenced
this issue
Aug 13, 2021
* Add steiner_tree function This commit adds a function to find an approximation of the minimum Steiner tree using the algorithm described in "A fast algorithm for Steiner tree" Kou, Markowsky & Berman (1981). https://link.springer.com/article/10.1007/BF00288961 This algorithm produces a tree whose weight is within a (2 - (2 / t)) factor of the weight of the optimal Steiner tree where t is the number of terminal nodes. Closes #389 * Add more tests * Switch to iterating over node indices in metric_closure In #390 one of the last changes made to the PR before merging was: 3353b4b which changed the final loop constructing the metric closure edges from iterating over node indices and pulling the path from the hashmap for that index to just iterating over the hashmap. That however had the unintended side effect of introducing non-determinism to the output as the iteration order over a hashmap isn't guaranteed. This was causing failures in the steiner tree function as the metric closure edge order can affect the computed tree. This commit fixes this by switching back to using the node id order for the final output generation and adds a comment as to why. * Fix release notes * Apply suggestions from code review Co-authored-by: georgios-ts <[email protected]> * Split out edge deduplication to separate function * Attempt to avoid cycles by using src and target in sort Co-authored-by: georgios-ts <[email protected]> * Remove input graph usage in edge deduplication Co-authored-by: georgios-ts <[email protected]> * Move steiner_tree() to Tree docs section * Add test case with equal distances This adds a test case with an input graph that has equal distances. It is a test based on a review comment [1] that was previously producing an incorrect output (that wasn't even a tree). After fixing the underlying issue it would be good to have this tested to ensure we don't regress on it in the future. [1] #392 (comment) Co-authored-by: georgios-ts <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
What is the expected enhancement?
Add a minimum steiner tree function equivalent to networkx's
steiner_tree()function: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.steinertree.steiner_tree.html#networkx.algorithms.approximation.steinertree.steiner_treeThe source can be found here: https://github.com/networkx/networkx/blob/80704838e60327f3e3a292f4fb4812039be843df/networkx/algorithms/approximation/steinertree.py
This will likely need to be done over 3 PRs, one adding
metric_closure(), one foredge_subgraph, and the last combines the first 2 to make thesteiner_treefunction.The text was updated successfully, but these errors were encountered: