|
|
import networkx as nx |
|
|
from networkx.utils.decorators import not_implemented_for, py_random_state |
|
|
|
|
|
__all__ = ["randomized_partitioning", "one_exchange"] |
|
|
|
|
|
|
|
|
@not_implemented_for("directed", "multigraph") |
|
|
@py_random_state(1) |
|
|
@nx._dispatch(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. |
|
|
""" |
|
|
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", "multigraph") |
|
|
@py_random_state(2) |
|
|
@nx._dispatch(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. |
|
|
""" |
|
|
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()) |
|
|
|
|
|
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 |
|
|
|
