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