# set_cover ## 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)`​

#### 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;``