Graph Utilities API

mmot.graph_utilities.ConvertToTree(undirected_graph, root_node)

Starting from an undirected graph, this function constructs a tree with the specified vertex as the root node. Vertices are duplicated if necessary to define the tree.

Parameters:

• undirected_graph (igraph.Graph) – Undirected graph defining pairwise costs

• root_node (int) – Index of the vertex that in the undirected graph that will serve as the root node of the tree.

Returns:

A directed graph containing a tree with the specified root node. This

tree might have multiple vertices corresponding to the same marginal distribution. This duplication is necessary to handle general pairwise cost structures. The mapping of the tree vertices to the vertices in the undirected graph is provided by the second output of this function.

list(int)A mapping from vertices in the tree to the vertices (i.e., marginals)

in the original undirected graph. The i-th component of this list contains the index of the undirected vertex that matches the i-th vertex in the tree.

list(list(int))A list of lists containing the vertices in each layer of the tree.

layers[i] contains the indices of vertices in layer i of the tree. layers[0] contains the vertices that are farthest from the root node. layers[-1] contains just the root node.

Return type:

igraph.Graph