【未標明的翻譯皆出自‘有道翻譯’】

1、python 包 官方文檔鏈接 ：

Approximations and Heuristics — NetworkX 2.6rc1.dev0 documentation

復雜網(wǎng)絡軟件 — NetworkX 2.5 文檔 (osgeo.cn)

2、官方文檔里Steiner Tree所在位置如圖：

3、Steiner Tree 函數(shù)的介紹

metric_closure(G[,?weight])	Return the metric closure of a graph.
steiner_tree(G,?terminal_nodes[,?weight])	Return an approximation to the minimum Steiner tree of a graph.

• networkx.algorithms.approximation.steinertree.metric_closure

metric_closure(G,?weight='weight')[source]

Return the metric closure of a graph. 返回一個圖的度量閉包

The metric closure of a graph?G?is the complete graph in which each edge is weighted by the shortest path distance between the nodes in?G?.

圖G的度量閉包是一個完全圖，其中每條邊都被G中節(jié)點之間的最短路徑距離加權。

Parameters

G ：NetworkX graph

Returns ：NetworkX graph? ? Metric closure of the graph?G.

?

• networkx.algorithms.approximation.steinertree.steiner_tree

steiner_tree(G,?terminal_nodes,?weight='weight')[source]

Return an approximation to the minimum Steiner tree of a graph.?。返回圖的最小斯坦納樹的近似值。

The minimum Steiner tree of?G?w.r.t a set of?terminal_nodes?is a tree within?G?that spans those nodes and has minimum size (sum of edge weights) among all such trees.

G的最小Steiner樹(一組terminal_nodes)是G內(nèi)部跨越這些節(jié)點且在所有這些樹中具有最小大小(邊權和)的樹。

G的最小Steiner樹是一組G內(nèi)的樹，該樹跨越這些節(jié)點并且在所有此類樹中具有最小的大小（邊緣權重之和）。【谷歌翻譯】

The minimum Steiner tree can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of?G?induced by the terminal nodes, where the metric closure of?G?is the complete graph in which each edge is weighted by the shortest path distance between the nodes in?G?. 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 number of terminal nodes.

最小Steiner樹可以近似計算子圖的最小生成樹的度規(guī)關閉終端節(jié)點,引發(fā)的G, G的度量閉包是完全圖中每條邊的節(jié)點之間的最短路徑距離加權的G。該算法生成的樹的權值在最優(yōu)Steiner樹權值的(2 - (2 / t))因子之內(nèi)，其中t為終端節(jié)點數(shù)。

可以通過計算由終端節(jié)點terminal nodes引起的G度量封閉的子圖的最小生成樹來近似最小Steiner樹，其中G度量封閉是完整的圖，其中每個邊都由之間的最短路徑距離加權 G中的節(jié)點 。該算法生成的樹的權重在最佳Steiner樹的權重的（2-（2 / t））因子之內(nèi)，其中t是終端節(jié)點的數(shù)量。【谷歌翻譯】

Parameters

G :?NetworkX graph

terminal_nodes :?list? ? ? ? ?A list of terminal nodes for which minimum steiner tree is to be found.?要為其找到最小斯坦納樹的終端節(jié)點列表。

Returns?: NetworkX graph? ? ? ? Approximation to the minimum steiner tree of?G?induced by?terminal_nodes?.?由終端節(jié)點誘導的G最小steiner樹的逼近。

• Notes

For multigraphs, the edge between two nodes with minimum weight is the edge put into the Steiner tree.

對于多重圖，權值最小的兩個節(jié)點之間的邊是放入Steiner樹的邊。

• References

Steiner_tree_problem on Wikipedia.?https://en.wikipedia.org/wiki/Steiner_tree_problem

4、函數(shù)源碼 ：?networkx.algorithms.approximation.steinertree — NetworkX 2.6rc1.dev0 documentation

from itertools import chainfrom networkx.utils import pairwise, not_implemented_for import networkx as nx__all__ = ["metric_closure", "steiner_tree"][docs]@not_implemented_for("directed") def metric_closure(G, weight="weight"):"""Return the metric closure of a graph.The metric closure of a graph *G* is the complete graph in which each edgeis weighted by the shortest path distance between the nodes in *G* .Parameters----------G : NetworkX graphReturns-------NetworkX graphMetric closure of the graph `G`."""M = nx.Graph()Gnodes = set(G)# check for connected graph while processing first nodeall_paths_iter = nx.all_pairs_dijkstra(G, weight=weight)u, (distance, path) = next(all_paths_iter)if Gnodes - set(distance):msg = "G is not a connected graph. metric_closure is not defined."raise nx.NetworkXError(msg)Gnodes.remove(u)for v in Gnodes:M.add_edge(u, v, distance=distance[v], path=path[v])# first node done -- now process the restfor u, (distance, path) in all_paths_iter:Gnodes.remove(u)for v in Gnodes:M.add_edge(u, v, distance=distance[v], path=path[v])return M @not_implemented_for("directed") def steiner_tree(G, terminal_nodes, weight="weight"):"""Return an approximation to the minimum Steiner tree of a graph.The minimum Steiner tree of `G` w.r.t a set of `terminal_nodes`is a tree within `G` that spans those nodes and has minimum size(sum of edge weights) among all such trees.The minimum Steiner tree can be approximated by computing the minimumspanning tree of the subgraph of the metric closure of *G* induced by theterminal nodes, where the metric closure of *G* is the complete graph inwhich each edge is weighted by the shortest path distance between thenodes in *G* .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 number ofterminal nodes.Parameters----------G : NetworkX graphterminal_nodes : listA list of terminal nodes for which minimum steiner tree isto be found.Returns-------NetworkX graphApproximation to the minimum steiner tree of `G` induced by`terminal_nodes` .Notes-----For multigraphs, the edge between two nodes with minimum weight is theedge put into the Steiner tree.References----------.. [1] Steiner_tree_problem on Wikipedia.https://en.wikipedia.org/wiki/Steiner_tree_problem"""# H is the subgraph induced by terminal_nodes in the metric closure M of G.M = metric_closure(G, weight=weight)H = M.subgraph(terminal_nodes)# Use the 'distance' attribute of each edge provided by M.mst_edges = nx.minimum_spanning_edges(H, weight="distance", data=True)# Create an iterator over each edge in each shortest path; repeats are okayedges = chain.from_iterable(pairwise(d["path"]) for u, v, d in mst_edges)# For multigraph we should add the minimal weight edge keysif G.is_multigraph():edges = ((u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) for u, v in edges)T = G.edge_subgraph(edges)return T

5、函數(shù)使用

（待補充）

總結

以上是生活随笔為你收集整理的python networkx.algorithms.approximation.steinertree 介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。