Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 `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 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.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD