112 lines
3.5 KiB
Python
112 lines
3.5 KiB
Python
|
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)
|
||
|
|
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)
|
||
|
|
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())
|
||
|
|
# 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
|