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;