pldl package

Submodules

pldl.cover module

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

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

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

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

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

pldl.graph_algo module

Minimum vertex cover for weighed graphs. 1. Support Lazy evalution

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

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

pldl.netlist module

pldl.netlist_algo module

pldl.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 = pldl.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

pldl.skeleton.fib(n)

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

pldl.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"]).

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

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

pldl.skeleton.setup_logging(loglevel)

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

Module contents