Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/connectivity/utils.py: 21%

1""" 

2Utilities for connectivity package 

3""" 

4 

5import networkx as nx 

6 

7__all__ = ["build_auxiliary_node_connectivity", "build_auxiliary_edge_connectivity"] 

8 

9 

10@nx._dispatchable(returns_graph=True) 

11def build_auxiliary_node_connectivity(G): 

12 r"""Creates a directed graph D from an undirected graph G to compute flow 

13 based node connectivity. 

14 

15 For an undirected graph G having `n` nodes and `m` edges we derive a 

16 directed graph D with `2n` nodes and `2m+n` arcs by replacing each 

17 original node `v` with two nodes `vA`, `vB` linked by an (internal) 

18 arc in D. Then for each edge (`u`, `v`) in G we add two arcs (`uB`, `vA`) 

19 and (`vB`, `uA`) in D. Finally we set the attribute capacity = 1 for each 

20 arc in D [1]_. 

21 

22 For a directed graph having `n` nodes and `m` arcs we derive a 

23 directed graph D with `2n` nodes and `m+n` arcs by replacing each 

24 original node `v` with two nodes `vA`, `vB` linked by an (internal) 

25 arc (`vA`, `vB`) in D. Then for each arc (`u`, `v`) in G we add one 

26 arc (`uB`, `vA`) in D. Finally we set the attribute capacity = 1 for 

27 each arc in D. 

28 

29 A dictionary with a mapping between nodes in the original graph and the 

30 auxiliary digraph is stored as a graph attribute: D.graph['mapping']. 

31 

32 References 

33 ---------- 

34 .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and 

35 Erlebach, 'Network Analysis: Methodological Foundations', Lecture 

36 Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. 

37 https://doi.org/10.1007/978-3-540-31955-9_7 

38 

39 """ 

40 directed = G.is_directed() 

41 

42 mapping = {} 

43 H = nx.DiGraph() 

44 

45 for i, node in enumerate(G): 

46 mapping[node] = i 

47 H.add_node(f"{i}A", id=node) 

48 H.add_node(f"{i}B", id=node) 

49 H.add_edge(f"{i}A", f"{i}B", capacity=1) 

50 

51 edges = [] 

52 for source, target in G.edges(): 

53 edges.append((f"{mapping[source]}B", f"{mapping[target]}A")) 

54 if not directed: 

55 edges.append((f"{mapping[target]}B", f"{mapping[source]}A")) 

56 H.add_edges_from(edges, capacity=1) 

57 

58 # Store mapping as graph attribute 

59 H.graph["mapping"] = mapping 

60 return H 

61 

62 

63@nx._dispatchable(returns_graph=True) 

64def build_auxiliary_edge_connectivity(G): 

65 """Auxiliary digraph for computing flow based edge connectivity 

66 

67 If the input graph is undirected, we replace each edge (`u`,`v`) with 

68 two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute 

69 'capacity' for each arc to 1. If the input graph is directed we simply 

70 add the 'capacity' attribute. Part of algorithm 1 in [1]_ . 

71 

72 References 

73 ---------- 

74 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. (this is a 

75 chapter, look for the reference of the book). 

76 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf 

77 """ 

78 if G.is_directed(): 

79 H = nx.DiGraph() 

80 H.add_nodes_from(G.nodes()) 

81 H.add_edges_from(G.edges(), capacity=1) 

82 return H 

83 else: 

84 H = nx.DiGraph() 

85 H.add_nodes_from(G.nodes()) 

86 for source, target in G.edges(): 

87 H.add_edges_from([(source, target), (target, source)], capacity=1) 

88 return H