ix.util
Class Graphs

java.lang.Object
  ix.util.Graphs

public final class Graphs
extends java.lang.Object

Static graph utilities.

Method Summary

static DAGTransitiveClosure	dagTransitiveClosure(DirectedGraph g) Transitive closure of a directed acyclic graph (DAG).
static java.util.Map	findLongestPathLengths(DirectedGraph g) DAG Longest-path-lengths algorithm.
static BoundedGraph	makeBoundedGraph(DirectedGraph g) Makes a BoundedGraph from a DirectedGraph by adding start and finish nodes.
static BoundedGraph	makeBoundedGraph(DirectedGraph g, Function0 nodeFactory) Makes a BoundedGraph from a DirectedGraph by adding start and finish nodes.
static DirectedGraph	makeDirectedGraph(java.util.Collection roots, Function1 f) Makes a directed graph from a collection of root vertices and a function that maps each vertex to its successors.
static DirectedGraph	makeDirectedGraph(java.util.Map map) Makes a directed graph from a map that maps each vertex to its successors.
static DirectedGraph	makeReflexive(DirectedGraph g) Returns a graph in which each vertex has an edge back to itself.
static java.util.Set	maximalElements(DirectedGraph g) Returns a set containing the vertices that have no successors.
static java.util.Set	minimalElements(DirectedGraph g) Returns a set containing the vertices that have no predecessors.
static java.util.Map	toMap(java.util.Map m, DirectedGraph g) Extends a map by adding a mapping from each vertex in a directed graph to the vertex's successors in that graph.
static java.util.List	topologicalSort(DirectedGraph g) DAG topological sort, returning ancestors before descendents.
static FullTransitiveClosure	transitiveClosure(DirectedGraph g) Transitive closure of a relation.
static DirectedGraph	transpose(DirectedGraph g) Returns a graph in which vertex-to-successor edges go in the opposite direction from those in the original graph.

Methods inherited from class java.lang.Object

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

Method Detail

makeDirectedGraph

public static DirectedGraph makeDirectedGraph(java.util.Map map)

Makes a directed graph from a map that maps each vertex to its successors.

See Also:

toMap(Map, DirectedGraph)

makeDirectedGraph

public static DirectedGraph makeDirectedGraph(java.util.Collection roots,
                                              Function1 f)

Makes a directed graph from a collection of root vertices and a function that maps each vertex to its successors.

toMap

public static java.util.Map toMap(java.util.Map m,
                                  DirectedGraph g)

Extends a map by adding a mapping from each vertex in a directed graph to the vertex's successors in that graph.

Returns:

the modified map.

See Also:

makeDirectedGraph(Map)

minimalElements

public static java.util.Set minimalElements(DirectedGraph g)

Returns a set containing the vertices that have no predecessors.

maximalElements

public static java.util.Set maximalElements(DirectedGraph g)

Returns a set containing the vertices that have no successors.

makeReflexive

public static DirectedGraph makeReflexive(DirectedGraph g)

Returns a graph in which each vertex has an edge back to itself.

transpose

public static DirectedGraph transpose(DirectedGraph g)

Returns a graph in which vertex-to-successor edges go in the opposite direction from those in the original graph.

topologicalSort

public static java.util.List topologicalSort(DirectedGraph g)

DAG topological sort, returning ancestors before descendents.

See Also:

TopologicalSorter

dagTransitiveClosure

public static DAGTransitiveClosure dagTransitiveClosure(DirectedGraph g)

Transitive closure of a directed acyclic graph (DAG).

See Also:

transitiveClosure(DirectedGraph), DAGTransitiveClosure

transitiveClosure

public static FullTransitiveClosure transitiveClosure(DirectedGraph g)

Transitive closure of a relation. The graph is allowed to contain cycles.

See Also:

dagTransitiveClosure(DirectedGraph), FullTransitiveClosure

findLongestPathLengths

public static java.util.Map findLongestPathLengths(DirectedGraph g)

DAG Longest-path-lengths algorithm.

Finds distances from the root vertices by finding the number of steps in the longest path along successor links from a roots without predecessors to each vertex, where the length of each link is 1. (The term "root" implies no predecessors, but the algorithm begins with a topological sort that should straighten things out if a root happens to have some.)

The results are returned in a Map that maps vertices to distances. Vertices must be represented by objects that are equals-unique. The distance values are represented by IntRefs.

This is O(v+e) where v is the number of vertices and e the number of edges (links to successors).

Translated from the O-Plan TF compiler's graph utilities.

makeBoundedGraph

public static BoundedGraph makeBoundedGraph(DirectedGraph g)

Makes a BoundedGraph from a DirectedGraph by adding start and finish nodes. The start and finish will be plain Objects. Note that the start and finish are always added, even if the graph already contains a unique minimal or maximal node.

makeBoundedGraph

public static BoundedGraph makeBoundedGraph(DirectedGraph g,
                                            Function0 nodeFactory)

Makes a BoundedGraph from a DirectedGraph by adding start and finish nodes. The start and finish are created by calling the nodeFactory. Note that the start and finish are always added, even if the graph already contains a unique minimal or maximal node.