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