"""
Graph Algorithms (graph_algo.py)
This code contains two main functions that work with graphs to solve optimization
problems. Let's break down what each function does in simple terms.
The first function, min_vertex_cover_fast, finds a minimum weighted vertex cover
in a graph. A vertex cover is a set of vertices that includes at least one
endpoint of every edge in the graph. The "weighted" part means that each vertex
has a weight, and we want to find a cover with the lowest total weight.
This function takes three inputs:
1. A graph (ugraph)
2. A dictionary of weights for each vertex (weight)
3. An optional set of vertices to start with (coverset)
It outputs two things:
1. The set of vertices that form the cover
2. The total weight of this cover
The function works by looking at each edge in the graph. If neither end of the
edge is in the cover yet, it adds the end with the higher weight to the cover.
It keeps track of the total weight and updates the remaining "gap" for each
vertex. This process continues until all edges are covered.
The second function, min_maximal_independant_set, finds a minimum weighted
maximal independent set in a graph. An independent set is a set of vertices
where no two vertices are connected by an edge. "Maximal" means we can't add any
more vertices to the set without breaking this rule. Like before, we want to
find such a set with the lowest total weight.
This function takes four inputs:
1. A graph (ugraph)
2. A dictionary of weights for each vertex (weight)
3. An optional set to start the independent set (indset)
4. An optional set of dependent vertices (dep)
It outputs:
1. The independent set of vertices
2. The total weight of this set
The function works by looking at each vertex in the graph. For each vertex and
its neighbors, it chooses the one with the lowest remaining weight to add to the
independent set. It then marks this vertex and all its neighbors as "dependent"
(they can't be added to the independent set). This process continues until all
vertices are either in the independent set or marked as dependent.
Both functions use a technique called a primal-dual algorithm, which is a way of
solving optimization problems. They both keep track of a "gap" for each vertex,
which helps ensure that the solution is close to optimal.
These functions are useful in various graph theory applications, such as network
design, scheduling problems, or resource allocation, where we need to find
efficient ways to cover a graph or select non-adjacent elements.
"""
import copy
from typing import Any, MutableMapping, Optional, Set, Tuple, Union
[docs]
def min_vertex_cover_fast(
ugraph: Any, weight: MutableMapping, coverset: Optional[Set] = None
) -> Tuple[Set, Union[int, float]]:
r"""
The `min_vertex_cover_fast` function performs minimum weighted vertex cover
using a primal-dual approximation algorithm (without post-processing).
:param ugraph: ugraph is a NetworkX graph object representing the graph on
which the minimum weighted vertex cover algorithm will be performed. It
contains the nodes and edges of the graph
:param weight: The `weight` parameter is a mutable mapping that represents
the weight of each vertex in the graph. It is used to determine the minimum
weighted vertex cover. The keys of the mapping are the vertices of the
graph, and the values are the corresponding weights
:type weight: MutableMapping
:param coverset: The `coverset` parameter is an optional set that represents
the current vertex cover. It is used to keep track of the vertices that are
included in the cover. If no coverset is provided, a new empty set is
created
:type coverset: Optional[Set]
:return: The function `min_vertex_cover_fast` returns a tuple containing the
vertex cover set and the total weight of the vertex cover.
.. svgbob::
:align: center
"({b, d, e}, 3)"
b c d e
#-----o-----#-----o
| \ / \
| \ / \
o #-----o
a e f
Examples:
>>> import networkx as nx
>>> from netlistx.graph_algo import min_vertex_cover_fast
>>> ugraph = nx.Graph()
>>> ugraph.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])
>>> weight = {0: 1, 1: 1, 2: 1, 3: 1, 4: 1}
>>> coverset = set()
>>> min_vertex_cover_fast(ugraph, weight, coverset)
({0, 1, 2, 3}, 4)
>>> ugraph = nx.Graph()
>>> ugraph.add_edges_from([(0, 1), (1, 2)])
>>> weight = {0: 1, 1: 2, 2: 1}
>>> coverset = set()
>>> min_vertex_cover_fast(ugraph, weight, coverset)
({0, 2}, 2)
"""
if coverset is None:
coverset = set()
total_dual_cost = 0 # for assertion
total_prml_cost = 0
gap = copy.copy(weight)
for utx, vtx in ugraph.edges():
if utx in coverset or vtx in coverset:
continue
if gap[utx] < gap[vtx]:
utx, vtx = vtx, utx # swap
coverset.add(vtx)
total_dual_cost += gap[vtx]
total_prml_cost += weight[vtx]
gap[utx] -= gap[vtx]
gap[vtx] = 0
assert total_dual_cost <= total_prml_cost
return coverset, total_prml_cost
[docs]
def min_maximal_independant_set(
ugraph: Any,
weight: MutableMapping,
indset: Optional[Set] = None,
dep: Optional[Set] = None,
) -> Tuple[Set, Union[int, float]]:
r"""
The `min_maximal_independant_set` function performs minimum weighted maximal
independent set using primal-dual algorithm.
:param ugraph: ugraph is an undirected graph represented using the NetworkX
library. It represents the graph structure and contains the vertices and
edges of the graph
:param weight: The `weight` parameter is a dictionary-like object that assigns
a weight to each vertex in the graph. The keys of the dictionary represent
the vertices, and the values represent their corresponding weights
:type weight: MutableMapping
:param indset: The `indset` parameter is a set that represents the current
independent set. It is initially set to `None` and is updated during the
execution of the `min_maximal_independent_set` function
:type indset: Optional[Set]
:param dep: The `dep` parameter is a set that represents the dependent vertices
in the graph. These are the vertices that are not included in the
independent set and are adjacent to vertices in the independent set. The
`coverset` function is used to add a vertex and its adjacent vertices to
the dependent set
:type dep: Optional[Set]
:return: The function `min_maximal_independant_set` returns a tuple containing
the minimum weighted maximal independent set (indset) and the total primal
cost (total_prml_cost).
.. svgbob::
:align: center
"({0, 3}, 2)"
0 2 4
#-----o-----o
\ / \ /
\ / \ /
o-----#
1 3
Examples:
>>> import networkx as nx
>>> from netlistx.graph_algo import min_maximal_independant_set
>>> ugraph = nx.Graph()
>>> ugraph.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])
>>> weight = {0: 1, 1: 1, 2: 1, 3: 1, 4: 1}
>>> indset = set()
>>> dep = set()
>>> min_maximal_independant_set(ugraph, weight, indset, dep)
({0, 3}, 2)
>>> ugraph = nx.Graph()
>>> ugraph.add_edges_from([(0, 1), (1, 2)])
>>> weight = {0: 1, 1: 2, 2: 1}
>>> indset = set()
>>> dep = set()
>>> min_maximal_independant_set(ugraph, weight, indset, dep)
({0, 2}, 2)
"""
if indset is None:
indset = set()
if dep is None:
dep = set()
def coverset(utx: Any) -> None:
dep.add(utx)
for vtx in ugraph[utx]:
dep.add(vtx)
gap = copy.copy(weight)
total_prml_cost = 0
total_dual_cost = 0
for utx in ugraph:
if utx in dep:
continue
if utx in indset: # pre-define indepentant
# coverset(utx)
continue
min_val = gap[utx]
min_vtx = utx
for vtx in ugraph[utx]:
if vtx in dep:
continue
if min_val > gap[vtx]:
min_val = gap[vtx]
min_vtx = vtx
indset.add(min_vtx)
coverset(min_vtx)
total_prml_cost += weight[min_vtx]
total_dual_cost += min_val
if min_vtx == utx:
continue
for vtx in ugraph[utx]:
gap[vtx] -= min_val
assert total_dual_cost <= total_prml_cost
return indset, total_prml_cost