Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / connectivity / utils.py @ 5cef0f13

History | View | Annotate | Download (3.22 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Utilities for connectivity package
4
"""
5
import networkx as nx
6

    
7
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>'])
8

    
9
__all__ = ['build_auxiliary_node_connectivity',
10
           'build_auxiliary_edge_connectivity']
11

    
12

    
13
def build_auxiliary_node_connectivity(G):
14
    r"""Creates a directed graph D from an undirected graph G to compute flow
15
    based node connectivity.
16

17
    For an undirected graph G having `n` nodes and `m` edges we derive a
18
    directed graph D with `2n` nodes and `2m+n` arcs by replacing each
19
    original node `v` with two nodes `vA`, `vB` linked by an (internal)
20
    arc in D. Then for each edge (`u`, `v`) in G we add two arcs (`uB`, `vA`)
21
    and (`vB`, `uA`) in D. Finally we set the attribute capacity = 1 for each
22
    arc in D [1]_.
23

24
    For a directed graph having `n` nodes and `m` arcs we derive a
25
    directed graph D with `2n` nodes and `m+n` arcs by replacing each
26
    original node `v` with two nodes `vA`, `vB` linked by an (internal)
27
    arc (`vA`, `vB`) in D. Then for each arc (`u`, `v`) in G we add one 
28
    arc (`uB`, `vA`) in D. Finally we set the attribute capacity = 1 for
29
    each arc in D.
30

31
    A dictionary with a mapping between nodes in the original graph and the
32
    auxiliary digraph is stored as a graph attribute: H.graph['mapping'].
33

34
    References
35
    ----------
36
    .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and
37
        Erlebach, 'Network Analysis: Methodological Foundations', Lecture
38
        Notes in Computer Science, Volume 3418, Springer-Verlag, 2005.
39
        http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
40

41
    """
42
    directed = G.is_directed()
43

    
44
    mapping = {}
45
    H = nx.DiGraph()
46

    
47
    for i, node in enumerate(G):
48
        mapping[node] = i
49
        H.add_node('%dA' % i, id=node)
50
        H.add_node('%dB' % i, id=node)
51
        H.add_edge('%dA' % i, '%dB' % i, capacity=1)
52

    
53
    edges = []
54
    for (source, target) in G.edges():
55
        edges.append(('%sB' % mapping[source], '%sA' % mapping[target]))
56
        if not directed:
57
            edges.append(('%sB' % mapping[target], '%sA' % mapping[source]))
58
    H.add_edges_from(edges, capacity=1)
59

    
60
    # Store mapping as graph attribute
61
    H.graph['mapping'] = mapping
62
    return H
63

    
64

    
65
def build_auxiliary_edge_connectivity(G):
66
    """Auxiliary digraph for computing flow based edge connectivity
67

68
    If the input graph is undirected, we replace each edge (`u`,`v`) with
69
    two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute
70
    'capacity' for each arc to 1. If the input graph is directed we simply
71
    add the 'capacity' attribute. Part of algorithm 1 in [1]_ .
72

73
    References
74
    ----------
75
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. (this is a
76
        chapter, look for the reference of the book).
77
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
78
    """
79
    if G.is_directed():
80
        H = nx.DiGraph()
81
        H.add_nodes_from(G.nodes())
82
        H.add_edges_from(G.edges(), capacity=1)
83
        return H
84
    else:
85
        H = nx.DiGraph()
86
        H.add_nodes_from(G.nodes())
87
        for (source, target) in G.edges():
88
            H.add_edges_from([(source, target), (target, source)], capacity=1)
89
        return H