Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.29 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors:  Aric Hagberg (hagberg@lanl.gov) and Dan Schult (dschult@colgate.edu)
10
#
11
"""
12
Provides functions for finding and testing for locally `(k, l)`-connected
13
graphs.
14

15
"""
16
import copy
17
import networkx as nx
18

    
19
__all__ = ['kl_connected_subgraph', 'is_kl_connected']
20

    
21

    
22
def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False):
23
    """Returns the maximum locally `(k, l)`-connected subgraph of `G`.
24

25
    A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
26
    graph there are at least `l` edge-disjoint paths of length at most `k`
27
    joining `u` to `v`.
28

29
    Parameters
30
    ----------
31
    G : NetworkX graph
32
        The graph in which to find a maximum locally `(k, l)`-connected
33
        subgraph.
34

35
    k : integer
36
        The maximum length of paths to consider. A higher number means a looser
37
        connectivity requirement.
38

39
    l : integer
40
        The number of edge-disjoint paths. A higher number means a stricter
41
        connectivity requirement.
42

43
    low_memory : bool
44
        If this is True, this function uses an algorithm that uses slightly
45
        more time but less memory.
46

47
    same_as_graph : bool
48
        If True then return a tuple of the form `(H, is_same)`,
49
        where `H` is the maximum locally `(k, l)`-connected subgraph and
50
        `is_same` is a Boolean representing whether `G` is locally `(k,
51
        l)`-connected (and hence, whether `H` is simply a copy of the input
52
        graph `G`).
53

54
    Returns
55
    -------
56
    NetworkX graph or two-tuple
57
        If `same_as_graph` is True, then this function returns a
58
        two-tuple as described above. Otherwise, it returns only the maximum
59
        locally `(k, l)`-connected subgraph.
60

61
    See also
62
    --------
63
    is_kl_connected
64

65
    References
66
    ----------
67
    .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
68
            Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
69
            2004. 89--104.
70

71
    """
72
    H = copy.deepcopy(G)    # subgraph we construct by removing from G
73

    
74
    graphOK = True
75
    deleted_some = True  # hack to start off the while loop
76
    while deleted_some:
77
        deleted_some = False
78
        # We use `for edge in list(H.edges()):` instead of
79
        # `for edge in H.edges():` because we edit the graph `H` in
80
        # the loop. Hence using an iterator will result in
81
        # `RuntimeError: dictionary changed size during iteration`
82
        for edge in list(H.edges()):
83
            (u, v) = edge
84
            # Get copy of graph needed for this search
85
            if low_memory:
86
                verts = set([u, v])
87
                for i in range(k):
88
                    for w in verts.copy():
89
                        verts.update(G[w])
90
                G2 = G.subgraph(verts).copy()
91
            else:
92
                G2 = copy.deepcopy(G)
93
            ###
94
            path = [u, v]
95
            cnt = 0
96
            accept = 0
97
            while path:
98
                cnt += 1  # Found a path
99
                if cnt >= l:
100
                    accept = 1
101
                    break
102
                # record edges along this graph
103
                prev = u
104
                for w in path:
105
                    if prev != w:
106
                        G2.remove_edge(prev, w)
107
                        prev = w
108
#                path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
109
                try:
110
                    path = nx.shortest_path(G2, u, v)  # ??? should "Cutoff" be k+1?
111
                except nx.NetworkXNoPath:
112
                    path = False
113
            # No Other Paths
114
            if accept == 0:
115
                H.remove_edge(u, v)
116
                deleted_some = True
117
                if graphOK:
118
                    graphOK = False
119
    # We looked through all edges and removed none of them.
120
    # So, H is the maximal (k,l)-connected subgraph of G
121
    if same_as_graph:
122
        return (H, graphOK)
123
    return H
124

    
125

    
126
def is_kl_connected(G, k, l, low_memory=False):
127
    """Returns True if and only if `G` is locally `(k, l)`-connected.
128

129
    A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
130
    graph there are at least `l` edge-disjoint paths of length at most `k`
131
    joining `u` to `v`.
132

133
    Parameters
134
    ----------
135
    G : NetworkX graph
136
        The graph to test for local `(k, l)`-connectedness.
137

138
    k : integer
139
        The maximum length of paths to consider. A higher number means a looser
140
        connectivity requirement.
141

142
    l : integer
143
        The number of edge-disjoint paths. A higher number means a stricter
144
        connectivity requirement.
145

146
    low_memory : bool
147
        If this is True, this function uses an algorithm that uses slightly
148
        more time but less memory.
149

150
    Returns
151
    -------
152
    bool
153
        Whether the graph is locally `(k, l)`-connected subgraph.
154

155
    See also
156
    --------
157
    kl_connected_subgraph
158

159
    References
160
    ----------
161
    .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
162
            Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
163
            2004. 89--104.
164

165
    """
166
    graphOK = True
167
    for edge in G.edges():
168
        (u, v) = edge
169
        # Get copy of graph needed for this search
170
        if low_memory:
171
            verts = set([u, v])
172
            for i in range(k):
173
                [verts.update(G.neighbors(w)) for w in verts.copy()]
174
            G2 = G.subgraph(verts)
175
        else:
176
            G2 = copy.deepcopy(G)
177
        ###
178
        path = [u, v]
179
        cnt = 0
180
        accept = 0
181
        while path:
182
            cnt += 1  # Found a path
183
            if cnt >= l:
184
                accept = 1
185
                break
186
            # record edges along this graph
187
            prev = u
188
            for w in path:
189
                if w != prev:
190
                    G2.remove_edge(prev, w)
191
                    prev = w
192
#            path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
193
            try:
194
                path = nx.shortest_path(G2, u, v)  # ??? should "Cutoff" be k+1?
195
            except nx.NetworkXNoPath:
196
                path = False
197
        # No Other Paths
198
        if accept == 0:
199
            graphOK = False
200
            break
201
    # return status
202
    return graphOK