No description, website, or topics provided.
Python
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
testdata
README.md
cover.py

README.md

Python SETCOVER

This is an implementation of SETCOVER in python, hacked together for a friend's PhD thesis. It computes the complete list of solutions for the given input set of subsets.

Features

  • Read input from a file
  • Computes all the solutions for a given input set of subsets
  • Verifies, that all vertices from 1 to MAX are present in the subsets. If vertices are missing, they are output in list form inside a warning.

Usage

Run the program with the input file as the first parameter. Optionally you can force new format file behaviour by specifying --new-file as the second parameter. Example:

python cover.py input.txt

Input file format

The input file contains one subset description per line. Each element has to be a parseable integer value. For example, a simple input file could look like this:

1 2 3 4 5 6 7
8 9 10 11 12 13 14
1 8
2 3 9 10
4 5 6 7 11 12 13 14

Older file format

Older versions used an input file format, where the first to lines contained the number of vertices and the number of subsets respectively. Those files are automatically detected and the first two lines will not be taken as subsets. The example from above would look like this:

14
5
1 2 3 4 5 6 7
8 9 10 11 12 13 14
1 8
2 3 9 10
4 5 6 7 11 12 13 14

Instead of the maximum value, the number of vertices in the first line will be used during verification of the completeness of the target superset.

Caveats

  • Caution! This code is far from perfect and I cannot guarantee, that it is usefull at all or will suit your needs.
  • Always make sure, you either specify old format files or use the --new-file option.
  • During runtime, the code outputs subset numbers with an offset of "-1", starting at 0. The final output list starts at 1.
  • Also it is horribly slow, due to the hackish implementation using python sets and the exhaustive nature of the search.