pldl package

Submodules

pldl.cover module

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