ioftools / networkxMiCe / networkxmaster / networkx / algorithms / connectivity / utils.py @ 5cef0f13
History  View  Annotate  Download (3.22 KB)
1 
# * coding: utf8 *


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, SpringerVerlag, 2005.

39 
http://www.informatik.uniaugsburg.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] AbdolHossein 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
