Skip to main content

set_cover

docs-source

Abstract#

The Set Cover problem is one of the problems in graph theory that tries to solve the least possible set of sets that covers all elements inside those sets. Given a set of n elements, and a collection of m sets containing them, the algorithm tries to identify the smallest sub-collection of sets whose union equal to all the elements. It is NP-complete, however solvable with techniques such as constraint programming. The current algorithm uses GEKKO optimizer as a constraint programming solver.

TraitValue
Module typemodule
ImplementationPython
Graph directionundirected
Edge weightsunweighted
Parallelismsequential

Procedures#

cp_solve(element_vertexes, set_vertexes)#

Input#

The input itself represents an element-set pair with each row of the lists.

  • element_vertexes: List[Vertex] ➡ List of element nodes in pairs
  • set_vertexes: List[Vertex] ➡ List of set nodes in pairs

Output#

  • containing_set ➡ minimal set of sets in which all the elements are contained

Usage#

CALL set_cover.cp_solve([(:Point), (:Point)], [(:Set), (:Set)])YIELD containing_set;

Example#

greedy(context, element_vertexes, set_vertexes)#

Not bad, not terrible.

Input#

The input itself represents an element-set pair with each row of the lists.

  • element_vertexes: List[Vertex] ➡ List of element nodes in pairs
  • set_vertexes: List[Vertex] ➡ List of set nodes in pairs

Output#

  • containing_set ➡ minimal set of sets in which all the elements are contained

Usage#

CALL set_cover.greedy([(:Point), (:Point)], [(:Set), (:Set)])YIELD containing_set;