Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1import networkx as nx
2from networkx.utils.decorators import not_implemented_for, py_random_state
4__all__ = ["randomized_partitioning", "one_exchange"]
7@not_implemented_for("directed")
8@not_implemented_for("multigraph")
9@py_random_state(1)
10@nx._dispatchable(edge_attrs="weight")
11def randomized_partitioning(G, seed=None, p=0.5, weight=None):
12 """Compute a random partitioning of the graph nodes and its cut value.
14 A partitioning is calculated by observing each node
15 and deciding to add it to the partition with probability `p`,
16 returning a random cut and its corresponding value (the
17 sum of weights of edges connecting different partitions).
19 Parameters
20 ----------
21 G : NetworkX graph
23 seed : integer, random_state, or None (default)
24 Indicator of random number generation state.
25 See :ref:`Randomness<randomness>`.
27 p : scalar
28 Probability for each node to be part of the first partition.
29 Should be in [0,1]
31 weight : object
32 Edge attribute key to use as weight. If not specified, edges
33 have weight one.
35 Returns
36 -------
37 cut_size : scalar
38 Value of the minimum cut.
40 partition : pair of node sets
41 A partitioning of the nodes that defines a minimum cut.
43 Examples
44 --------
45 >>> G = nx.complete_graph(5)
46 >>> cut_size, partition = nx.approximation.randomized_partitioning(G, seed=1)
47 >>> cut_size
48 6
49 >>> partition
50 ({0, 3, 4}, {1, 2})
52 Raises
53 ------
54 NetworkXNotImplemented
55 If the graph is directed or is a multigraph.
56 """
57 cut = {node for node in G.nodes() if seed.random() < p}
58 cut_size = nx.algorithms.cut_size(G, cut, weight=weight)
59 partition = (cut, G.nodes - cut)
60 return cut_size, partition
63def _swap_node_partition(cut, node):
64 return cut - {node} if node in cut else cut.union({node})
67@not_implemented_for("directed")
68@not_implemented_for("multigraph")
69@py_random_state(2)
70@nx._dispatchable(edge_attrs="weight")
71def one_exchange(G, initial_cut=None, seed=None, weight=None):
72 """Compute a partitioning of the graphs nodes and the corresponding cut value.
74 Use a greedy one exchange strategy to find a locally maximal cut
75 and its value, it works by finding the best node (one that gives
76 the highest gain to the cut value) to add to the current cut
77 and repeats this process until no improvement can be made.
79 Parameters
80 ----------
81 G : networkx Graph
82 Graph to find a maximum cut for.
84 initial_cut : set
85 Cut to use as a starting point. If not supplied the algorithm
86 starts with an empty cut.
88 seed : integer, random_state, or None (default)
89 Indicator of random number generation state.
90 See :ref:`Randomness<randomness>`.
92 weight : object
93 Edge attribute key to use as weight. If not specified, edges
94 have weight one.
96 Returns
97 -------
98 cut_value : scalar
99 Value of the maximum cut.
101 partition : pair of node sets
102 A partitioning of the nodes that defines a maximum cut.
104 Examples
105 --------
106 >>> G = nx.complete_graph(5)
107 >>> curr_cut_size, partition = nx.approximation.one_exchange(G, seed=1)
108 >>> curr_cut_size
109 6
110 >>> partition
111 ({0, 2}, {1, 3, 4})
113 Raises
114 ------
115 NetworkXNotImplemented
116 If the graph is directed or is a multigraph.
117 """
118 if initial_cut is None:
119 initial_cut = set()
120 cut = set(initial_cut)
121 current_cut_size = nx.algorithms.cut_size(G, cut, weight=weight)
122 while True:
123 nodes = list(G.nodes())
124 # Shuffling the nodes ensures random tie-breaks in the following call to max
125 seed.shuffle(nodes)
126 best_node_to_swap = max(
127 nodes,
128 key=lambda v: nx.algorithms.cut_size(
129 G, _swap_node_partition(cut, v), weight=weight
130 ),
131 default=None,
132 )
133 potential_cut = _swap_node_partition(cut, best_node_to_swap)
134 potential_cut_size = nx.algorithms.cut_size(G, potential_cut, weight=weight)
136 if potential_cut_size > current_cut_size:
137 cut = potential_cut
138 current_cut_size = potential_cut_size
139 else:
140 break
142 partition = (cut, G.nodes - cut)
143 return current_cut_size, partition