Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / steinertree.py @ 5cef0f13

History | View | Annotate | Download (2.76 KB)

1
from itertools import combinations, chain
2

    
3
from networkx.utils import pairwise, not_implemented_for
4
import networkx as nx
5

    
6
__all__ = ['metric_closure', 'steiner_tree']
7

    
8

    
9
@not_implemented_for('directed')
10
def metric_closure(G, weight='weight'):
11
    """  Return the metric closure of a graph.
12

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

16
    Parameters
17
    ----------
18
    G : NetworkX graph
19

20
    Returns
21
    -------
22
    NetworkX graph
23
        Metric closure of the graph `G`.
24

25
    """
26
    M = nx.Graph()
27

    
28
    Gnodes = set(G)
29

    
30
    # check for connected graph while processing first node
31
    all_paths_iter = nx.all_pairs_dijkstra(G, weight=weight)
32
    u, (distance, path) = next(all_paths_iter)
33
    if Gnodes - set(distance):
34
        msg = "G is not a connected graph. metric_closure is not defined."
35
        raise nx.NetworkXError(msg)
36
    Gnodes.remove(u)
37
    for v in Gnodes:
38
        M.add_edge(u, v, distance=distance[v], path=path[v])
39

    
40
    # first node done -- now process the rest
41
    for u, (distance, path) in all_paths_iter:
42
        Gnodes.remove(u)
43
        for v in Gnodes:
44
            M.add_edge(u, v, distance=distance[v], path=path[v])
45

    
46
    return M
47

    
48

    
49
@not_implemented_for('multigraph')
50
@not_implemented_for('directed')
51
def steiner_tree(G, terminal_nodes, weight='weight'):
52
    """ Return an approximation to the minimum Steiner tree of a graph.
53

54
    Parameters
55
    ----------
56
    G : NetworkX graph
57

58
    terminal_nodes : list
59
         A list of terminal nodes for which minimum steiner tree is
60
         to be found.
61

62
    Returns
63
    -------
64
    NetworkX graph
65
        Approximation to the minimum steiner tree of `G` induced by
66
        `terminal_nodes` .
67

68
    Notes
69
    -----
70
    Steiner tree can be approximated by computing the minimum spanning
71
    tree of the subgraph of the metric closure of the graph induced by the
72
    terminal nodes, where the metric closure of *G* is the complete graph in
73
    which each edge is weighted by the shortest path distance between the
74
    nodes in *G* .
75
    This algorithm produces a tree whose weight is within a (2 - (2 / t))
76
    factor of the weight of the optimal Steiner tree where *t* is number of
77
    terminal nodes.
78

79
    """
80
    # M is the subgraph of the metric closure induced by the terminal nodes of
81
    # G.
82
    M = metric_closure(G, weight=weight)
83
    # Use the 'distance' attribute of each edge provided by the metric closure
84
    # graph.
85
    H = M.subgraph(terminal_nodes)
86
    mst_edges = nx.minimum_spanning_edges(H, weight='distance', data=True)
87
    # Create an iterator over each edge in each shortest path; repeats are okay
88
    edges = chain.from_iterable(pairwise(d['path']) for u, v, d in mst_edges)
89
    T = G.edge_subgraph(edges)
90
    return T