netlistx package

Submodules

netlistx.cover module

Cover Algorithms with Reverse-Delete Post-Processing (cover.py)

This module implements primal-dual approximation algorithms for various covering problems in graphs, with enhanced post-processing using the reverse-delete technique.

The main purpose is to find minimal sets of vertices that “cover” certain structures in a graph, such as all edges, cycles, or odd cycles.

The algorithms use a two-phase approach: 1. Primal-Dual Selection: Iteratively builds a solution by selecting elements

with minimum reduced cost (gap).

2. Reverse-Delete Post-Processing: Removes redundant elements from the solution in reverse order of selection to ensure minimality.

Key functions: - pd_cover: Core primal-dual algorithm with reverse-delete post-processing - min_vertex_cover: Find minimum weighted vertex cover in a graph - min_hyper_vertex_cover: Find minimum weighted vertex cover in a hypergraph - min_cycle_cover: Find minimum weighted set of vertices covering all cycles - min_odd_cycle_cover: Find minimum weighted set of vertices covering all odd cycles

The algorithms are useful in electronic design automation (EDA) for problems like logic optimization and circuit analysis.

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

Find minimum weighted set of vertices covering all cycles.

A cycle cover is a set of vertices such that removing them from the graph eliminates all cycles.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial cycle cover (default: empty set).

Returns:

A tuple of (minimum cycle cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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)
({2}, 1)

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

Find minimum weighted vertex cover in a hypergraph using primal-dual.

In a hypergraph, each hyperedge (net) can connect multiple vertices. A vertex cover must include at least one vertex from each hyperedge.

Parameters:

• hyprgraph – The hypergraph with nets and modules attributes.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

Returns:

A tuple of (minimum vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

Examples

>>> class MockHyprgraph:
...     def __init__(self, nets, ugraph):
...         self.nets = nets
...         self.ugraph = ugraph
>>> hyprgraph = MockHyprgraph(["N1", "N2"], {"N1": [0, 1], "N2": [1, 2]})
>>> weight = {0: 1, 1: 1, 2: 1}
>>> soln = set()
>>> min_hyper_vertex_cover(hyprgraph, weight, soln)
({1}, 1)

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

Find minimum weighted set of vertices covering all odd cycles.

An odd cycle cover is a set of vertices such that removing them from the graph eliminates all cycles with odd length.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial odd cycle cover (default: empty set).

Returns:

A tuple of (minimum odd cycle cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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)
({2}, 1)

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

Find minimum weighted vertex cover using primal-dual with reverse-delete.

A vertex cover is a set of vertices where every edge in the graph has at least one endpoint in the set.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

Returns:

A tuple of (minimum vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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, 2, 3}, 3)

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

Primal-dual approximation algorithm with reverse-delete post-processing.

This is a core algorithm that finds a minimal weighted cover by combining primal-dual selection with reverse-delete refinement.

Parameters:

• violate (Callable) – A callable that returns a generator of violating sets. Each set contains elements where at least one must be added to the cover.

• weight (MutableMapping) – A mutable mapping from elements to their weights.

• soln (Set) – The initial solution set (may be empty or contain pre-selected elements).

Returns:

A tuple containing the minimal cover set and its total weight.

Return type:

Tuple[Set, Union[int, float]]

The algorithm maintains a “gap” for each element, representing the remaining budget. In each iteration, it selects the element with minimum gap from a violating set. After all violations are resolved, it performs reverse-delete to remove any redundant elements.

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}, 3)

netlistx.cover_ai module

Cover Algorithms with Reverse-Delete Post-Processing (cover.py)

This module implements primal-dual approximation algorithms for various covering problems in graphs, with enhanced post-processing using the reverse-delete technique.

The main purpose is to find minimal sets of vertices that “cover” certain structures in a graph, such as all edges, cycles, or odd cycles.

The algorithms use a two-phase approach: 1. Primal-Dual Selection: Iteratively builds a solution by selecting elements

with minimum reduced cost (gap).

2. Reverse-Delete Post-Processing: Removes redundant elements from the solution in reverse order of selection to ensure minimality.

Key functions: - pd_cover: Core primal-dual algorithm with reverse-delete post-processing - min_vertex_cover: Find minimum weighted vertex cover in a graph - min_hyper_vertex_cover: Find minimum weighted vertex cover in a hypergraph - min_cycle_cover: Find minimum weighted set of vertices covering all cycles - min_odd_cycle_cover: Find minimum weighted set of vertices covering all odd cycles

The algorithms are useful in electronic design automation (EDA) for problems like logic optimization and circuit analysis.

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

Find minimum weighted set of vertices covering all cycles.

A cycle cover is a set of vertices such that removing them from the graph eliminates all cycles.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial cycle cover (default: empty set).

Returns:

A tuple of (minimum cycle cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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

Find minimum weighted vertex cover in a hypergraph using primal-dual.

In a hypergraph, each hyperedge (net) can connect multiple vertices. A vertex cover must include at least one vertex from each hyperedge.

Parameters:

• hyprgraph – The hypergraph with nets and modules attributes.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

Returns:

A tuple of (minimum vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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

Find minimum weighted set of vertices covering all odd cycles.

An odd cycle cover is a set of vertices such that removing them from the graph eliminates all cycles with odd length.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial odd cycle cover (default: empty set).

Returns:

A tuple of (minimum odd cycle cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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

Find minimum weighted vertex cover using primal-dual with reverse-delete.

A vertex cover is a set of vertices where every edge in the graph has at least one endpoint in the set.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

Returns:

A tuple of (minimum vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

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

Primal-dual approximation algorithm with reverse-delete post-processing.

This is a core algorithm that finds a minimal weighted cover by combining primal-dual selection with reverse-delete refinement.

Parameters:

• violate (Callable) – A callable that returns a generator of violating sets. Each set contains elements where at least one must be added to the cover.

• weight (MutableMapping) – A mutable mapping from elements to their weights.

• soln (Set) – The initial solution set (may be empty or contain pre-selected elements).

Returns:

A tuple containing the minimal cover set and its total weight.

Return type:

Tuple[Set, Union[int, float]]

The algorithm maintains a “gap” for each element, representing the remaining budget. In each iteration, it selects the element with minimum gap from a violating set. After all violations are resolved, it performs reverse-delete to remove any redundant elements.

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: Any, 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)

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

netlistx.graph_algo.min_vertex_cover_fast(ugraph: Any, 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)

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

netlistx.hadlock module

Hadlock’s Algorithm for Planar MAX-CUT

Hadlock’s algorithm solves the Maximum Cut problem on planar graphs in polynomial time by transforming it into a minimum weight perfect matching problem on the planar dual graph.

The algorithm works as follows:

1. Find a planar embedding of the input graph.

2. Construct the dual graph where each face becomes a vertex.

3. Identify odd faces — faces whose boundary has an odd number of edges.

4. Build a complete graph on the odd-face vertices with edge weights equal to shortest-path distances in the dual graph.

5. Find a minimum weight perfect matching (MWPM) on this complete graph.

6. The primal edges that correspond to dual edges on the shortest paths between matched faces are the excluded edges.

7. The remaining primal edges form the maximum cut.

Reference

Hadlock, F. O. (1975). “Finding a Maximum Cut of a Planar Graph in Polynomial Time.” SIAM Journal on Computing, 4(3), 221-225.

netlistx.hadlock.solve_hadlock_max_cut(G: Graph, weight: str = 'weight') → Set[Tuple[Any, Any]]

Solve MAX-CUT for a planar graph using Hadlock’s algorithm.

The graph is first decomposed into biconnected components (blocks), which are solved independently. Because edges in different blocks cannot belong to the same cycle, the MAX-CUT is the disjoint union of the per-block cuts, and solving each block separately is significantly faster (smaller dual graphs, fewer odd faces, smaller MWPM instances).

Parameters:

• G (nx.Graph) – A planar graph. Edge weights should be stored under the attribute given by weight (default: 'weight'). If an edge lacks this attribute, weight 1 is assumed.

• weight (str) – Edge attribute name for weights.

Returns:

A set of (u, v) edges (sorted tuples) that form the maximum cut. The edges are guaranteed to form a bipartite subgraph.

Return type:

set of tuple

Raises:

nx.NetworkXException – If G is not planar.

Examples

>>> import networkx as nx
>>> from netlistx.hadlock import solve_hadlock_max_cut, validate_max_cut

Build a simple triangle with weights:

>>> G = nx.Graph()
>>> G.add_edge(0, 1, weight=5)
>>> G.add_edge(1, 2, weight=10)
>>> G.add_edge(2, 0, weight=3)
>>> cut = solve_hadlock_max_cut(G)
>>> is_ok, val = validate_max_cut(G, cut)
>>> is_ok
True
>>> val  # should be total - min_weight = 18 - 3 = 15
15

netlistx.hadlock.validate_max_cut(G: Graph, cut_edges: Set[Tuple[Any, Any]], weight: str = 'weight') → Tuple[bool, float]

Validate that cut_edges forms a valid bipartite cut of G.

A valid cut must induce a bipartite subgraph (i.e. no odd cycles). The function also computes the total weight of the cut.

Parameters:

• G (nx.Graph) – The original graph.

• cut_edges (set of tuple) – Edges in the proposed cut.

• weight (str) – Edge attribute name for weights (default: 'weight').

Returns:

is_validbool

True if the cut subgraph is bipartite.

cut_weightfloat

Sum of weights of all edges in the cut.

Return type:

(is_valid, cut_weight)

netlistx.netlist module

Netlist.py

This code defines a set of classes and functions for working with netlists, which are representations of electronic circuits. The main purpose of this code is to provide tools for creating, manipulating, and analyzing netlists.

The code doesn’t take any direct inputs or produce any outputs on its own. Instead, it defines classes and functions that can be used by other parts of a program to work with netlists.

The main class in this code is the Netlist class. It represents a netlist as a graph, where modules (like electronic components) are connected by nets (like wires). The Netlist class takes three inputs when created: a graph representing the connections, a list of modules, and a list of nets.

The Netlist class provides several methods to get information about the netlist, such as the number of modules, nets, nodes, and pins. It also allows you to get the weight of modules and nets, which could represent things like the size or importance of components in the circuit.

The code includes several helper functions to create specific types of netlists. For example, create_inverter() creates a netlist representing a simple inverter circuit, while create_random_hgraph() creates a random netlist with a specified number of modules and nets.

The code uses graph theory concepts to represent the netlist. It uses the NetworkX library to handle the graph operations. The graph is represented as nodes (modules and nets) connected by edges (connections between modules and nets).

One important aspect of the code is how it handles the weights of modules and nets. It uses a RepeatArray class (which is not defined in this file) to efficiently store weights when many components have the same weight.

The code also includes functions for reading netlists from JSON files and for creating specific test netlists. These functions could be useful for testing or demonstrating the capabilities of the Netlist class.

Overall, this code provides a foundation for working with netlists in Python. It allows programmers to create, manipulate, and analyze netlists, which could be useful in electronic design automation tools or circuit analysis software.

class netlistx.netlist.Netlist(ugraph: Graph, modules: range | List[Any], nets: range | List[Any])

Bases: object

cost_model: int = 0

get_max_degree() → int

The function get_max_degree returns the maximum degree of nodes in a graph. :return: the maximum degree of the nodes in the graph.

get_module_weight(v: int) → int

The function get_module_weight returns the weight of a module given its index.

Parameters:

v – The parameter v in the get_module_weight function is of type size_t. It represents the index or key of the module weight that you want to retrieve

Returns:

the value of self.module_weight[v].

get_net_weight(_: Any) → int

The function get_net_weight returns an integer value.

Parameters:

_ – The underscore (_) in the function signature is a convention in Python to indicate that the parameter is not used within the function. It is often used when a parameter is required by the function signature but not actually used within the function’s implementation. In this case, the underscore (_) is used as a placeholder for

Returns:

An integer value of 1 is being returned.

num_pads: int = 0

number_of_modules() → int

The function “number_of_modules” returns the number of modules. :return: The method is returning the value of the attribute num_modules.

number_of_nets() → int

The function “number_of_nets” returns the number of nets. :return: The number of nets.

number_of_nodes() → int

The function “number_of_nodes” returns the number of nodes in a graph. :return: The number of nodes in the graph.

number_of_pins() → int

The function number_of_pins returns the number of edges in a graph. :return: The number of edges in the graph.

class netlistx.netlist.SimpleGraph(*args, backend=None, **kwargs)

Bases: Graph

The SimpleGraph class is a subclass of nx.Graph that defines default attributes for edges and nodes.

all_edge_dict = {'weight': 1}

edge_attr_dict_factory() → Dict

Returns the default edge attribute dictionary.

node_attr_dict_factory() → Dict

Returns the default edge attribute dictionary.

single_edge_dict() → Dict

Returns the default edge attribute dictionary.

class netlistx.netlist.TinyGraph(*args, backend=None, **kwargs)

Bases: Graph

The TinyGraph class is a subclass of nx.Graph that initializes a graph with a specified number of nodes and provides methods for creating node dictionaries and adjacency list dictionaries.

adjlist_outer_dict_factory() → MapAdapter

Returns a MapAdapter for adjacency list outer dictionaries.

cheat_adjlist_outer_dict() → MapAdapter

Returns a MapAdapter for adjacency list outer dictionaries.

cheat_node_dict() → MapAdapter

Returns a MapAdapter for node dictionaries.

init_nodes(n: int) → None

node_dict_factory() → MapAdapter

Returns a MapAdapter for node dictionaries.

num_nodes = 0

netlistx.netlist.create_drawf() → Netlist

The function create_drawf creates a graph and netlist object with specified nodes, edges, and weights.

Returns:

an instance of the Netlist class, which is created using the SimpleGraph class and some predefined modules and nets.

netlistx.netlist.create_inverter() → Netlist

Create a simple inverter netlist.

The inverter consists of: - One AND gate (a0) - Two input pads (p1, p2) - Two nets (n0, n1)

Net n0 connects input pad p1 to AND gate input, AND gate output. Net n1 connects AND gate input to output pad p2.

Returns:

A Netlist representing the inverter circuit.

Return type:

Netlist

netlistx.netlist.create_inverter2() → Netlist

Create a simple inverter netlist using numeric node IDs.

Similar to create_inverter() but uses integer node IDs (0-4) instead of string names. This variant uses modules 0-2 and nets 3-4.

Returns:

A Netlist representing the inverter circuit.

Return type:

Netlist

netlistx.netlist.create_random_hgraph(N: int = 30, M: int = 26, eta: float = 0.1) → Netlist

Create a random bipartite hypergraph for testing.

Uses van der Corput quasi-random sequences to distribute nodes uniformly in 2D space, then creates edges based on distance threshold.

Parameters:

• N (int) – Number of module nodes (default: 30).

• M (int) – Number of net nodes (default: 26).

• eta (float) – Edge probability/density parameter (default: 0.1).

Returns:

A Netlist with randomly distributed nodes and edges.

Return type:

Netlist

netlistx.netlist.create_test_netlist() → Netlist

The function create_test_netlist creates a test netlist with nodes, edges, module weights, and net weights. :return: an instance of the Netlist class, which represents a netlist with modules and nets.

netlistx.netlist.form_graph(N: int, M: int, _: Any, eta: float, seed: int | None = None) → Graph

Form N by N grid of nodes, connect nodes within eta.

mu and eta are relative to 1/(N-1)

Parameters:

• t (float) – the best-so-far optimal value

• pos ([type]) – [description]

• eta ([type]) – [description]

Keyword Arguments:

seed ([type]) – [description] (default: {None})

Returns:

[description]

Return type:

[type]

netlistx.netlist.read_json(filename: str) → Netlist

The function read_json reads a JSON file, converts it into a graph, and creates a netlist object with module and net weights.

Parameters:

filename – The filename parameter is the name of the JSON file that contains the data you want to read

Returns:

an object of type Netlist.

netlistx.netlist.read_yosys_json(filename: str) → Netlist

Read a Yosys JSON file and convert it to a Netlist object.

Parameters:

filename – Path to Yosys JSON file

Returns:

Netlist object representing the circuit

netlistx.netlist.vdc(n: int, base: int = 2) → float

[summary]

Parameters:

n ([type]) – [description]

Keyword Arguments:

base (int) – [description] (default: {2})

Returns:

[description]

Return type:

[type]

Examples

>>> vdc(0)
0.0
>>> vdc(1)
0.5
>>> vdc(2)
0.25
>>> vdc(3)
0.75

netlistx.netlist.vdcorput(n: int, base: int = 2) → List[float]

[summary]

Parameters:

n (int) – number of vectors

Keyword Arguments:

base (int) – [description] (default: {2})

Returns:

[description]

Return type:

[type]

Examples

>>> vdcorput(4)
[0.0, 0.5, 0.25, 0.75]

netlistx.netlist_algo module

Min Maximal Matching Algorithm

This code implements a function called min_maximal_matching which is designed to find a minimum weighted maximal matching in a hypergraph. Let’s break down what this means and how the function works.

The purpose of this code is to select a set of edges (called “nets” in this context) from a hypergraph in such a way that the total weight of the selected edges is minimized, while ensuring that no more edges can be added to the set without overlapping with already selected edges. This is useful in various optimization problems, such as circuit design or resource allocation.

The function takes four inputs:

1. hyprgraph: A representation of the hypergraph structure.

2. weight: A dictionary-like object that assigns weights to each edge in the hypergraph.

3. matchset: An optional set of pre-selected edges (defaults to an empty set if not provided).

4. dep: An optional set of vertices that are already covered by the matching (defaults to an empty set if not provided).

The output of the function is a tuple containing two elements:

1. The final set of matched edges (nets).

2. The total weight of the selected matching.

The algorithm works by iteratively selecting edges to add to the matching. It starts with an empty matching (unless a pre-defined matching is provided) and gradually builds it up. Here’s a simplified explanation of how it achieves its purpose:

1. It initializes some variables, including a copy of the weight dictionary called gap.

2. It then loops through all the edges (nets) in the hypergraph.

3. For each edge, it checks if any of its vertices are already covered by the current matching. If so, it skips this edge.

4. If the edge is not skipped, it looks for the edge with the minimum weight (considering the current gap values) that connects to any of the vertices of the current edge.

5. It adds this minimum-weight edge to the matching, updates the total cost, and marks all its vertices as covered.

6. It then updates the gap values for the remaining edges to reflect this selection.

The algorithm uses a primal-dual approach, which means it maintains two cost values: a primal cost (the actual weight of the selected edges) and a dual cost (a lower bound on the optimal solution). This helps ensure that the algorithm produces a solution that is within a certain factor of the optimal solution.

Some important logic flows in this code include the selection of the minimum-weight edge, the updating of the gap values, and the maintenance of the covered vertices set. These steps work together to gradually build up the matching while trying to minimize the total weight.

In summary, this algorithm provides a way to find a good (though not necessarily optimal) set of non-overlapping edges in a hypergraph, with the goal of minimizing the total weight of the selected edges. This can be useful in various optimization scenarios where you need to select a set of items that don’t conflict with each other while minimizing some cost metric.

netlistx.netlist_algo.min_maximal_matching(hyprgraph: Netlist, weight: MutableMapping, matchset: Set[Any] | None = None, dependents: Set[Any] | None = None) → Tuple[Set[Any], int | float]

The min_maximal_matching function performs minimum weighted maximal matching using a primal-dual approximation algorithm.

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 not clear from the code snippet what the exact data structure of the hypergraph is, but it likely contains information about the vertices and edges of

• weight (MutableMapping) – The weight parameter is a mutable mapping that represents the weights of the hypergraph edges. It is used to determine the weight of each edge in the matching. The keys of the weight mapping correspond to the hypergraph edges, and the values represent their weights

• matchset (Optional[Set]) – The matchset parameter is a set that represents the pre-defined matching. It contains the hyperedges (nets) that are already matched

• dependents (Optional[Set]) – The dependents parameter is a set that represents the set of vertices that are covered by the current matching. It is initially set to an empty set, and is updated during the execution of the algorithm

Returns:

The function min_maximal_matching returns a tuple containing the matchset (a set of matched elements) and the total primal cost (an integer or float representing the total weight of the matching).

Examples

>>> class MockUgraph:
...     def __init__(self, net_to_modules, module_to_nets):
...         self.net_to_modules = net_to_modules
...         self.module_to_nets = module_to_nets
...     def __getitem__(self, key):
...         if key in self.net_to_modules:
...             return self.net_to_modules[key]
...         return self.module_to_nets[key]
>>> class MockHyprgraph:
...     def __init__(self, nets, ugraph):
...         self.nets = nets
...         self.ugraph = ugraph
>>> ugraph = MockUgraph({"N1": [0, 1], "N2": [1, 2], "N3": [2, 3]}, {0: ["N1"], 1: ["N1", "N2"], 2: ["N2", "N3"], 3: ["N3"]})
>>> hyprgraph = MockHyprgraph(["N1", "N2", "N3"], ugraph)
>>> weight = {"N1": 1, "N2": 2, "N3": 1}
>>> matchset = set()
>>> dependents = set()
>>> result, cost = min_maximal_matching(hyprgraph, weight, matchset, dependents)
>>> result == {'N1', 'N3'} and cost == 2
True

netlistx.rand_cover module

Randomized Approximation Algorithm for Minimum Weighted Vertex Cover (MWVC)

Implements Pitt’s randomized algorithm (1985) for solving the minimum weighted vertex cover problem. The algorithm achieves an expected approximation ratio of 2.

The algorithm processes each edge in the graph. For each uncovered edge (u, v), it randomly selects one endpoint to add to the cover, with probability proportional to the weight of the other endpoint:

P(pick u) = w(v) / (w(u) + w(v)) P(pick v) = w(u) / (w(u) + w(v))

This biases the selection toward the lighter vertex, which is the key insight for the weighted case.

Reference:

L. Pitt, “A Simple Probabilistic Approximation Algorithm for Vertex Cover,” Technical Report, Yale University, 1985.

netlistx.rand_cover.rand_hyper_vertex_cover(hyprgraph: Any, weight: MutableMapping, coverset: Set | None = None, seed: int | None = None) → Tuple[Set, int | float]

Find a minimum weighted vertex cover in a hypergraph using Pitt’s randomized algorithm generalized to hyperedges.

In a hypergraph, each hyperedge (net) can connect multiple vertices. A vertex cover must include at least one vertex from each hyperedge.

For each uncovered net with vertices {v1, …, vk}, the algorithm picks vertex vi with probability inversely proportional to its weight:

P(pick vi) = (1/w(vi)) / sum(1/w(vj) for vj in net)

This is the natural generalization of Pitt’s rule: for a standard edge (k=2), this reduces to w(v)/(w(u)+w(v)).

Parameters:

• hyprgraph (Any) – The hypergraph with nets and modules attributes.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

• seed (Optional[int]) – Random seed for reproducible results (default: None).

Returns:

A tuple of (vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

Examples

>>> class MockHyprgraph:
...     def __init__(self, nets, ugraph):
...         self.nets = nets
...         self.ugraph = ugraph
>>> hyprgraph = MockHyprgraph(["N1", "N2"], {"N1": [0, 1], "N2": [1, 2]})
>>> weight = {0: 1, 1: 1, 2: 1}
>>> soln, cost = rand_hyper_vertex_cover(hyprgraph, weight, seed=42)
>>> isinstance(soln, set)
True
>>> isinstance(cost, (int, float))
True
>>> # Verify it's a valid cover: each net has at least one endpoint in soln
>>> all(any(v in soln for v in hyprgraph.ugraph[net]) for net in hyprgraph.nets)
True

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

Find a minimum weighted vertex cover using Pitt’s randomized algorithm.

This is a randomized 2-approximation algorithm for the minimum weighted vertex cover problem. For each uncovered edge, it selects an endpoint to add to the cover with probability inversely proportional to its weight.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

• seed (Optional[int]) – Random seed for reproducible results (default: None).

Returns:

A tuple of (vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

Examples

>>> ugraph = nx.Graph()
>>> ugraph.add_edges_from([(0, 1), (0, 2), (1, 2)])
>>> weight = {0: 1, 1: 2, 2: 3}
>>> soln, cost = rand_vertex_cover(ugraph, weight, seed=42)
>>> isinstance(soln, set)
True
>>> isinstance(cost, (int, float))
True
>>> # Verify it's a valid vertex cover
>>> all(u in soln or v in soln for u, v in ugraph.edges())
True

netlistx.rand_cover_gpu module

GPU-Accelerated Randomized Vertex Cover using Pitt’s Algorithm

Runs multiple independent Pitt trials in parallel on the GPU via Numba CUDA. Each CUDA thread executes one complete Pitt trial (edge iteration + random vertex selection). After all trials complete, the best (lowest cost) cover is returned.

This Monte Carlo approach exploits GPU parallelism by making each trial independent, requiring no inter-thread synchronization during execution.

Reference:

L. Pitt, “A Simple Probabilistic Approximation Algorithm for Vertex Cover,” Technical Report, Yale University, 1985.

netlistx.rand_cover_gpu.rand_vertex_cover_gpu(ugraph: Graph, weight: MutableMapping, coverset: Set | None = None, num_trials: int = 1024, seed: int | None = None) → Tuple[Set, int | float]

Find a minimum weighted vertex cover using GPU-accelerated Pitt’s algorithm.

Runs num_trials independent randomized Pitt trials in parallel on the GPU and returns the cover with the lowest total weight.

Parameters:

• ugraph (nx.Graph) – The input undirected graph.

• weight (MutableMapping) – A mapping from vertices to their weights.

• coverset (Optional[Set]) – Optional initial vertex cover (default: empty set).

• num_trials (int) – Number of parallel Monte Carlo trials (default: 1024).

• seed (Optional[int]) – Random seed for reproducible results (default: None).

Returns:

A tuple of (best vertex cover set, total weight).

Return type:

Tuple[Set, Union[int, float]]

Examples

>>> ugraph = nx.Graph()
>>> ugraph.add_edges_from([(0, 1), (0, 2), (1, 2)])
>>> weight = {0: 1, 1: 1, 2: 1}
>>> soln, cost = rand_vertex_cover_gpu(ugraph, weight, num_trials=64, seed=42)
>>> isinstance(soln, set)
True
>>> all(u in soln or v in soln for u, v in ugraph.edges())
True

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: int) → int

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

netlistx.skeleton.main(args: List[str]) → None

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: List[str]) → Namespace

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() → None

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: int) → None

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

netlistx.tsp module

Traveling Salesman Problem (TSP) Algorithms

This module implements approximation algorithms for the Metric TSP, including the Christofides algorithm (3/2-approximation) and the 2-Opt local search heuristic for refinement.

The main entry point is solve_christofides_2opt_tsp(), which runs Christofides to obtain an initial tour and then refines it with 2-Opt.

Metric TSP

A complete graph \(G = (V, E)\) with edge weights \(w_{ij}\) satisfying the triangle inequality:

\[w_{ik} \le w_{ij} + w_{jk} \quad \forall i,j,k \in V\]

Christofides Algorithm (1976)

1. Compute a Minimum Spanning Tree (MST) of G.

2. Find the set \(O\) of vertices with odd degree in the MST.

3. Compute a Minimum Weight Perfect Matching (MWPM) on \(O\).

4. Combine MST and matching into a multigraph (all degrees become even).

5. Find an Eulerian circuit in the multigraph.

6. Shortcut repeated vertices to obtain a Hamiltonian cycle.

The resulting tour has weight at most \(\frac{3}{2}\) times the optimal.

2-Opt Heuristic

Iteratively reverse segments of the tour to eliminate crossings, producing a locally optimal tour with no self-intersections.

References

• Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie Mellon University.

• Karlin, A.R., Klein, N., Oveis Gharan, S. (2020). A (Slightly) Improved Approximation Algorithm for Metric TSP. STOC 2021.

netlistx.tsp.calculate_total_distance(path: Sequence[Any], G: Graph) → float

Calculate the total length of a Hamiltonian path or cycle.

Parameters:

• path (Sequence[Any]) – Sequence of nodes representing the TSP tour (last node should equal the first for a closed cycle).

• G (nx.Graph) – The complete graph with edge weights (weight attribute on each edge).

Returns:

Total distance of the path.

Return type:

float

Example

>>> import networkx as nx
>>> G = nx.complete_graph(3)
>>> G[0][1]['weight'] = 1.0
>>> G[1][2]['weight'] = 2.0
>>> G[0][2]['weight'] = 3.0
>>> calculate_total_distance([0, 1, 2, 0], G)
6.0

netlistx.tsp.christofides_tsp(G: Graph) → List[Any]

Solve Metric TSP using the Christofides approximation algorithm.

The algorithm produces a Hamiltonian cycle whose total weight is at most 3/2 times the optimal.

Steps:

1. Minimum Spanning Tree (MST) of G.

2. Identify odd-degree vertices in the MST.

3. Minimum Weight Perfect Matching (MWPM) on odd-degree vertices.

4. Combine MST + matching into an Eulerian multigraph.

5. Find an Eulerian circuit.

6. Shortcut repeated nodes to produce a Hamiltonian cycle.

Parameters:

G (nx.Graph) – Complete graph with edge weight attributes satisfying the triangle inequality (Metric TSP).

Returns:

Hamiltonian cycle as a list of nodes (last == first).

Return type:

List[Any]

Example

>>> G = nx.complete_graph(5)
>>> for u, v in G.edges():
...     G[u][v]['weight'] = 1.0  # uniform → any tour works
>>> tour = christofides_tsp(G)
>>> len(tour) == 6  # 5 nodes + return to start
True
>>> calculate_total_distance(tour, G) > 0
True

netlistx.tsp.make_l1_graph(n: int, seed: int = 42) → Tuple[Graph, Dict[Any, Tuple[float, float]]]

Create a complete graph with random Manhattan (L1) edge weights.

Manhattan distance \(|\Delta x| + |\Delta y|\) satisfies the triangle inequality, so the graph is a valid Metric TSP instance.

Parameters:

• n – Number of nodes (cities).

• seed – Random seed for reproducibility.

Returns:

(G, pos) where G is the complete graph with weight attributes and pos maps node → (x, y).

Example

>>> G, pos = make_l1_graph(5)
>>> G[0][1]['weight'] >= 0
True

netlistx.tsp.make_l2_graph(n: int, seed: int = 42) → Tuple[Graph, Dict[Any, Tuple[float, float]]]

Create a complete graph with random Euclidean (L2) edge weights.

The graph is a valid Metric TSP instance (triangle inequality holds).

Parameters:

• n – Number of nodes (cities).

• seed – Random seed for reproducibility.

Returns:

(G, pos) where G is the complete graph with weight attributes and pos maps node → (x, y).

Example

>>> G, pos = make_l2_graph(5)
>>> len(G.nodes())
5
>>> G.number_of_edges()
10
>>> G[0][1]['weight'] > 0
True

netlistx.tsp.solve_christofides_2opt_tsp(G: Graph) → List[Any]

Solve Metric TSP using Christofides + 2-Opt refinement.

This is the recommended entry point. It first computes a 3/2-approximate tour via christofides_tsp(), then refines it with two_opt() local search to typically reduce the tour length further (often close to optimal for moderate \(n\)).

Parameters:

G (nx.Graph) – Complete graph with edge weight attributes satisfying the triangle inequality.

Returns:

Refined Hamiltonian cycle (last node == first).

Return type:

List[Any]

Example

>>> G = nx.complete_graph(6)
>>> for u, v in G.edges():
...     G[u][v]['weight'] = 1.0  # uniform weights
>>> tour = solve_christofides_2opt_tsp(G)
>>> len(tour) == 7
True
>>> nodes_visited = tour[:-1]
>>> sorted(nodes_visited) == list(range(6))
True

netlistx.tsp.two_opt(path: List[Any], G: Graph) → List[Any]

Refine a TSP tour using the 2-opt local search heuristic.

The 2-opt heuristic iteratively replaces crossing edge pairs (i-1, i) and (j-1, j) with (i-1, j-1) and (i, j) (by reversing the segment [i, j-1]) whenever it reduces total distance. This continues until a local optimum is reached.

Parameters:

• path (List[Any]) – Initial TSP tour (list of nodes, last == first).

• G (nx.Graph) – The complete graph with edge weights.

Returns:

2-opt refined tour (locally optimal).

Return type:

List[Any]

Example

>>> G = nx.complete_graph(4)
>>> pts = [(0, 0), (1, 0), (1, 1), (0, 1)]
>>> for u, v in G.edges():
...     G[u][v]['weight'] = ((pts[u][0]-pts[v][0])**2
...                        + (pts[u][1]-pts[v][1])**2)**0.5
>>> tour = two_opt([0, 1, 2, 3, 0], G)
>>> calculate_total_distance(tour, G) <= 5.0
True

Module contents