ca.uqac.lif.petitpoucet

Class GraphUtilities

java.lang.Object

ca.uqac.lif.petitpoucet.GraphUtilities

public class GraphUtilities
extends java.lang.Object

Utility methods for transforming lineage graphs.

Author:

Sylvain Hallé

Constructor Summary

Constructors

Constructor and Description
GraphUtilities()

Method Summary

Modifier and Type	Method and Description
static java.util.List<Node>	flatten(java.util.List<Node> roots) Out of a list of lineage graph roots, creates another set of graphs where nested nodes are exploded.
static Node	flatten(Node root) Out of a single-rooted lineage graph, creates another graph where nested nodes are exploded.
static boolean	isLeaf(Node n) Determines if a node is a leaf.
static java.util.List<Node>	simplify(java.util.List<Node> roots) Simplifies a list of lineage graphs.
static Node	simplify(Node root) Simplifies a single-rooted lineage graph.
static java.util.List<Node>	squash(java.util.List<Node> roots) Out of a list of lineage graphs, creates another graph where only Boolean nodes and leaves are kept.
static Node	squash(Node root) Out of a single-rooted lineage graph, creates another graph where only Boolean nodes and leaves are kept.
protected static void	squash(Node parent, int pin_index, Pin<? extends Node> pin, java.util.Set<Node> visited, java.util.Map<Node,Node> duplicates)
protected static Node	squash(Node root, java.util.Set<Node> visited, java.util.Map<Node,Node> duplicates) Out of a single-rooted lineage graph, creates another graph where only Boolean nodes and leaves are kept.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphUtilities

public GraphUtilities()

Method Detail

simplify

public static Node simplify(Node root)

Simplifies a single-rooted lineage graph. This method is the combined application of squash() and flatten().

Parameters:

root - The root of the original graph

Returns:

The root of the squashed graph

simplify

public static java.util.List<Node> simplify(java.util.List<Node> roots)

Simplifies a list of lineage graphs. This method is the combined application of squash(List) and flatten().

Parameters:

roots - The roots of the original graphs

Returns:

The roots of the squashed graphs

flatten

public static Node flatten(Node root)

Out of a single-rooted lineage graph, creates another graph where nested nodes are exploded.

Parameters:

root - The root of the original graph

Returns:

The root of the simplified graph

flatten

public static java.util.List<Node> flatten(java.util.List<Node> roots)

Out of a list of lineage graph roots, creates another set of graphs where nested nodes are exploded.

The operation is less trivial than it seems, as one cannot simply flatten the graph starting from each root separately. Any node shared between two sub-graphs will result in two copies. One must therefore pass the set of copies already produced in a previous flattening operation to the next one.

Parameters:

roots - The root of the original graph

Returns:

The list of roots of the simplified graphs

squash

public static java.util.List<Node> squash(java.util.List<Node> roots)

Out of a list of lineage graphs, creates another graph where only Boolean nodes and leaves are kept.

Parameters:

roots - The roots of the original graph

Returns:

The roots of the squashed graph

squash

protected static Node squash(Node root,
                             java.util.Set<Node> visited,
                             java.util.Map<Node,Node> duplicates)

Out of a single-rooted lineage graph, creates another graph where only Boolean nodes and leaves are kept.

Parameters:

root - The root of the original graph

visited - A set of already visited nodes

duplicates - A map keeping track of original nodes and their copies in the resulting graph

Returns:

The root of the squashed graph

squash

public static Node squash(Node root)

Out of a single-rooted lineage graph, creates another graph where only Boolean nodes and leaves are kept.

Parameters:

root - The root of the original graph

Returns:

The root of the squashed graph

squash

protected static void squash(Node parent,
                             int pin_index,
                             Pin<? extends Node> pin,
                             java.util.Set<Node> visited,
                             java.util.Map<Node,Node> duplicates)

isLeaf

public static boolean isLeaf(Node n)

Determines if a node is a leaf.

Parameters:

n - The node

Returns:

true if the node is a leaf, false otherwise.