netlistx package

Submodules

netlistx.cover module

Cover.py

This code implements several algorithms for solving different types of covering problems in graphs. The main purpose is to find minimal sets of vertices or edges that “cover” certain structures in a graph, such as all edges, cycles, or odd cycles.

The code takes various inputs depending on the specific function being used. Generally, it requires a graph structure (either a regular graph or a hypergraph), a weight mapping for the vertices, and sometimes an optional initial cover set. The graphs are typically represented using the NetworkX library (nx.Graph).

The outputs produced by these functions are usually a tuple containing two elements: a set representing the minimal cover found, and a number representing the total weight or cost of that cover.

The code achieves its purpose through several different algorithms, but they all follow a similar pattern called the primal-dual approximation method. This method iteratively builds a solution by selecting elements that violate certain conditions and adding them to the cover set.

Here’s a breakdown of the main functions:

1. pd_cover: This is the core function that implements the primal-dual approximation algorithm. It takes a “violate” function that generates sets of violating elements, a weight mapping, and an initial solution set. It iteratively adds elements to the solution until no violations remain.

2. min_vertex_cover: This function finds a minimum weighted vertex cover in a graph. It uses pd_cover with a violate function that yields edges not covered by the current solution.

3. min_hyper_vertex_cover: Similar to min_vertex_cover, but works on hypergraphs where edges can connect more than two vertices.

4. min_cycle_cover: This function finds a minimum weighted set of vertices that cover all cycles in a graph. It uses a breadth-first search to find cycles and then uses pd_cover to select vertices that break these cycles.

5. min_odd_cycle_cover: Similar to min_cycle_cover, but specifically targets odd cycles in the graph.

The code uses several important data structures and algorithms. Graphs are represented using NetworkX, which provides efficient graph operations. The algorithms make heavy use of sets for storing covers and dictionaries for storing weights and other information. The cycle-finding algorithms use breadth-first search and clever bookkeeping to efficiently detect cycles in the graph.

Overall, this code provides a toolkit for solving various covering problems on graphs, which have applications in many areas of computer science and operations research. The algorithms implemented here provide approximate solutions to these problems, which are often NP-hard and thus difficult to solve exactly for large instances.

netlistx.cover.min_cycle_cover(ugraph: Graph, weight: MutableMapping, coverset: Set | None = None) → Tuple[Set, int | float]

The min_cycle_cover function performs minimum cycle cover using a primal-dual approximation

algorithm (without post-processing).

Parameters:

• ugraph (nx.Graph) – The ugraph parameter is a nx.Graph object representing the input graph. It contains the nodes and edges of the graph

• weight (MutableMapping) – The weight parameter is a dictionary that assigns a weight to each node in the graph. The weights are used to determine the minimum cycle cover

• coverset (Optional[Set]) – The coverset parameter is an optional set that contains the nodes that are already covered by previous cycles. It is used to keep track of the nodes that have already been included in the minimum cycle cover. If no coverset is provided, it is initialized as an empty set

Returns:

The function min_cycle_cover returns a tuple containing a set and either an integer or a float. The set represents the minimum cycle cover, and the integer or float represents the weight of the minimum cycle cover.

Examples

>>> 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}
>>> soln = set()
>>> min_cycle_cover(ugraph, weight, soln)
({0, 1, 2}, 3)

netlistx.cover.min_hyper_vertex_cover(hyprgraph, weight: MutableMapping, coverset: Set | None = None) → Tuple[Set, int | float]

The min_hyper_vertex_cover function performs minimum weighted vertex cover using a primal-dual approximation algorithm (without post-processing).

Parameters:

• hyprgraph – The hyprgraph parameter represents a hypergraph, which is a generalization of a graph where an edge can connect more than two vertices. It is likely represented as a data structure that contains information about the vertices and edges of the hypergraph

• weight (MutableMapping) – The weight parameter is a mutable mapping that assigns a weight to each vertex in the hypergraph. It is used to determine the minimum weighted vertex cover

• coverset (Optional[Set]) – The coverset parameter is an optional set that represents the current vertex cover. It contains the vertices that have been selected as part of the cover. If no coverset is provided, it defaults to an empty set

Returns:

The function min_hyper_vertex_cover returns a tuple containing two elements. The first element is a set representing the minimum weighted vertex cover, and the second element is either an integer or a float representing the weight of the vertex cover.

netlistx.cover.min_odd_cycle_cover(ugraph: Graph, weight: MutableMapping, coverset: Set | None = None) → Tuple[Set, int | float]

The min_odd_cycle_cover function performs minimum odd cycle cover using a primal-dual approximation algorithm (without post-processing).

Parameters:

• ugraph (nx.Graph) – The ugraph parameter is a nx.Graph object representing the input graph. It is used to define the graph structure and find cycles in the graph

• weight (MutableMapping) – The weight parameter is a dictionary that assigns a weight to each node in the graph

• coverset (Optional[Set]) – The coverset parameter is an optional set that represents the initial set of vertices that are covered by the minimum odd cycle cover. This set can be empty if no vertices are initially covered

Returns:

The function min_odd_cycle_cover returns a tuple containing a set and either an integer or a float. The set represents the minimum odd cycle cover, and the integer or float represents the weight of the cover.

Examples

>>> 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}
>>> soln = set()
>>> min_odd_cycle_cover(ugraph, weight, soln)
({0, 1, 2}, 3)

netlistx.cover.min_vertex_cover(ugraph: Graph, weight: MutableMapping, coverset: Set | None = None) → Tuple[Set, int | float]

The min_vertex_cover function performs minimum weighted vertex cover using a primal-dual approximation algorithm (without post-processing).

Parameters:

• ugraph (nx.Graph) – The parameter ugraph is a nx.Graph object, which represents the input graph. It is an undirected graph where each edge represents a connection between two vertices

• weight (MutableMapping) – The weight parameter is a dictionary that assigns a weight to each vertex in the graph. The weights are used to determine the minimum weighted vertex cover

• coverset (Optional[Set]) – The coverset parameter is an optional set that represents the current vertex cover solution. It is used to keep track of the vertices that are included in the cover. If no coverset is provided, an empty set is used as the initial cover

Returns:

The function min_vertex_cover returns a tuple containing two elements. The first element is a set representing the minimum weighted vertex cover, and the second element is either an integer or a float representing the weight of the minimum vertex cover.

Examples

>>> 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}
>>> soln = set()
>>> min_vertex_cover(ugraph, weight, soln)
({0, 1, 2, 3}, 4)

netlistx.cover.pd_cover(violate: Callable, weight: MutableMapping, soln: Set) → Tuple[Set, int | float]

The function pd_cover implements a primal-dual approximation algorithm for covering problems.

Parameters:

• violate (Callable) – The violate parameter is a callable function or oracle that returns a set of violate elements. It is used to generate sets of elements that violate the current solution. Each set represents a potential improvement to the solution

• weight (MutableMapping) – The weight parameter is a dictionary that represents the weight of each element. The keys of the dictionary are the elements, and the values are their corresponding weights

• soln (Set) – The soln parameter is a set that represents the current solution set. It initially contains no elements, and elements are added to it during the algorithm

Returns:

a tuple containing the updated solution set and the total primal cost.

Examples

>>> def violate_graph() -> Generator:
...     yield [0, 1]
...     yield [0, 2]
...     yield [1, 2]
>>> weight = {0: 1, 1: 2, 2: 3}
>>> soln = set()
>>> pd_cover(violate_graph, weight, soln)
({0, 1}, 4)

netlistx.graph_algo module

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.

netlistx.graph_algo.min_maximal_independant_set(ugraph, weight: MutableMapping, indset: Set | None = None, dep: Set | None = None) → Tuple[Set, int | float]

The min_maximal_independant_set function performs minimum weighted maximal independent set using primal-dual algorithm.

Parameters:

• 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

• weight (MutableMapping) – 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

• indset (Optional[Set]) – 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

• dep (Optional[Set]) – 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

Returns:

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).

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)

netlistx.graph_algo.min_vertex_cover_fast(ugraph, weight: MutableMapping, coverset: Set | None = None) → Tuple[Set, int | float]

The min_vertex_cover_fast function performs minimum weighted vertex cover using a primal-dual approximation algorithm (without post-processing).

Parameters:

• 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

• weight (MutableMapping) – 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

• coverset (Optional[Set]) – 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

Returns:

The function min_vertex_cover_fast returns a tuple containing the vertex cover set and the total weight of the vertex cover.

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)

netlistx.netlist module

netlistx.netlist_algo module

netlistx.skeleton module

This is a skeleton file that can serve as a starting point for a Python console script. To run this script uncomment the following lines in the [options.entry_points] section in setup.cfg:

console_scripts =
     fibonacci = netlistx.skeleton:run

Then run pip install . (or pip install -e . for editable mode) which will install the command fibonacci inside your current environment.

Besides console scripts, the header (i.e. until _logger…) of this file can also be used as template for Python modules.

Note

This skeleton file can be safely removed if not needed!

References

• https://setuptools.readthedocs.io/en/latest/userguide/entry_point.html

• https://pip.pypa.io/en/stable/reference/pip_install

netlistx.skeleton.fib(n)

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

netlistx.skeleton.main(args)

Wrapper allowing fib() to be called with string arguments in a CLI fashion

Instead of returning the value from fib(), it prints the result to the stdout in a nicely formatted message.

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--verbose", "42"]).

netlistx.skeleton.parse_args(args)

Parse command line parameters

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--help"]).

Returns:

command line parameters namespace

Return type:

argparse.Namespace

netlistx.skeleton.run()

Calls main() passing the CLI arguments extracted from sys.argv

This function can be used as entry point to create console scripts with setuptools.

netlistx.skeleton.setup_logging(loglevel)

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

Module contents