sf.apps.clique.shrink

shrink(subgraph, graph)[source]

Shrinks an input subgraph until it forms a clique.

Proceeds by removing nodes in the input subgraph one at a time until the result is a clique that satisfies is_clique(). Upon each iteration, this function selects the node with lowest degree relative to the subgraph and removes it.

Example usage:

>>> graph = nx.barbell_graph(4, 0)
>>> subgraph = [0, 1, 2, 3, 4, 5]
>>> shrink(subgraph, graph)
[0, 1, 2, 3]
Parameters
  • subgraph (list[int]) – a subgraph specified by a list of nodes

  • graph (nx.Graph) – the input graph

Returns

a clique of size smaller than or equal to the input subgraph

Return type

list[int]