sgtl.algorithms.cheeger_cut

sgtl.algorithms.cheeger_cut(graph: sgtl.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}]