Graph normalization

An integer graph is a graph \(G = (V,E)\) such that \(V \subseteq \mathbb{N}\), \(\min(V) = 0\), \(\max(V) = |V| - 1\), namely its nodes are integers starting from 0 and do not have holes.

BisPy is able to work only with integer graphs, this is why we provide this class to go back and forth between the actual graph and an isomorphic representation.

convert_to_integer_graph(graph)

Convert the given graph to an isomorphic integer graph.

Parameters

graph (Graph) – The input graph.

Return type

Tuple[Graph, Dict[Any, int]]

Returns

A tuple whose items are:

  1. The integer ismorphic graph;

  2. A dict which may be used to recover the original graph.

check_normal_integer_graph(graph)

Check whether the given graph is integer.

Parameters

graph (Graph) – The input graph.

Return type

bool

back_to_original(partition, node_to_idx)

Convert the given partition of the nodes of an integer graph to the representation which uses nodes from the original graph using the mapping returned by convert_to_integer_graph().

Parameters

  • partition (List[Tuple[int]]) – The partition of the set of nodes of an integer graph.

  • node_to_idx (Tuple[Graph, Dict[Any, int]]) – The mapping returned by convert_to_integer_graph().

Return type

List[Tuple[Any]]