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​

info

If you want to execute this algorithm on graph projections, subgraphs or portions of the graph, be sure to check out the guide on How to run a MAGE module on subgraphs.

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;

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;