

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object ix.util.Graphs
public final class Graphs
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 Longestpathlengths 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 vertextosuccessor 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 

public static DirectedGraph makeDirectedGraph(java.util.Map map)
toMap(Map, DirectedGraph)
public static DirectedGraph makeDirectedGraph(java.util.Collection roots, Function1 f)
public static java.util.Map toMap(java.util.Map m, DirectedGraph g)
makeDirectedGraph(Map)
public static java.util.Set minimalElements(DirectedGraph g)
public static java.util.Set maximalElements(DirectedGraph g)
public static DirectedGraph makeReflexive(DirectedGraph g)
public static DirectedGraph transpose(DirectedGraph g)
public static java.util.List topologicalSort(DirectedGraph g)
TopologicalSorter
public static DAGTransitiveClosure dagTransitiveClosure(DirectedGraph g)
transitiveClosure(DirectedGraph)
,
DAGTransitiveClosure
public static FullTransitiveClosure transitiveClosure(DirectedGraph g)
dagTransitiveClosure(DirectedGraph)
,
FullTransitiveClosure
public static java.util.Map findLongestPathLengths(DirectedGraph g)
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 equalsunique. The distance values are represented
by IntRef
s.
This is O(v+e) where v is the number of vertices and e the number of edges (links to successors).
Translated from the OPlan TF compiler's graph utilities.
public static BoundedGraph makeBoundedGraph(DirectedGraph g)
public static BoundedGraph makeBoundedGraph(DirectedGraph g, Function0 nodeFactory)


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 