inferlo.graphs.path_decomposition

inferlo.graphs.path_decomposition(graph: Graph) → List[array]

Path decomposition of a graph.

Splits vertices into layers, such that vertices in layer i are connected only with vertices from layers i-1, i and i+1.

Uses simple greedy algorithm. First layer always contains single vertex with id=0.

If graph is not connected, will decompose every connected component and concatenate results.

This is similar, but no identical to https://en.wikipedia.org/wiki/Pathwidth.

Parameters:

graph – Graph for which to compute decomposition. Its nodes must be labeled by consecutive integers, starting with 0.

Returns:

Path decomposition of given graph. List of np.arrays, where i-th array contains indices of nodes in i-th layer. Guaranteed that all layers are disjoint and together they contain all vertices from the graph.