sgtl.algorithms.cheeger_cut#
- sgtl.algorithms.cheeger_cut(graph: Graph) Tuple[Set[int], Set[int]] #
Given a graph G, find the cheeger cut. Returns a pair of lists containing the vertex indices of the two sides of the cut.
- Parameters:
graph – The graph on which to operate.
- Returns:
Two sets containing the vertices on each side of the cheeger cut.
- Example:
>>> import sgtl.graph >>> import sgtl.algorithms >>> graph = sgtl.graph.path_graph(10) >>> cut = sgtl.algorithms.cheeger_cut(graph) >>> sorted(cut, key=(lambda x: min(x))) [{0, 1, 2, 3, 4}, {5, 6, 7, 8, 9}]