Package jline.util.graph

Class DirectedGraph

java.lang.Object
jline.util.graph.DirectedGraph
public class DirectedGraph extends Object
A directed graph data structure with weighted edges represented as an adjacency matrix.

This class provides graph algorithms for directed graphs including cycle detection, topological sorting, and connectivity analysis. It's particularly useful for routing matrix analysis, dependency resolution, and network topology validation.

Key graph algorithms supported:

  • Directed Acyclic Graph (DAG) detection
  • Topological sorting using Kahn's algorithm
  • Adjacency matrix-based representation
  • Weighted edge support
  • Column filtering for selective analysis

Since:
1.0
See Also:

  • Constructor Details

    • DirectedGraph

      public DirectedGraph(Matrix param, Set<Integer> colsToIgnore)
      Constructs a directed graph with the given adjacency matrix and column filter.
      Parameters:
      param - adjacency matrix [V x V] where entry (i,j) represents edge weight from vertex i to j
      colsToIgnore - set of column indices to ignore during graph operations, can be null

    • DirectedGraph

      public DirectedGraph(Matrix param)
      Constructs a directed graph with the given adjacency matrix (no column filtering).
      Parameters:
      param - adjacency matrix [V x V] where entry (i,j) represents edge weight from vertex i to j

  • Method Details

    • isDAG

      public static boolean isDAG(Matrix adj)
      Tests if the given adjacency matrix represents a Directed Acyclic Graph (DAG).
      Parameters:
      adj - adjacency matrix [V x V] to test for cycles
      Returns:
      true if the graph is acyclic, false if cycles are detected

    • kahn

      public static Matrix kahn(Matrix adj)
      Performs topological sorting using Kahn's algorithm.

      This method computes a topological ordering of vertices in a directed graph. If the graph contains cycles, the returned ordering will be incomplete.

      Parameters:
      adj - adjacency matrix [V x V] representing the directed graph
      Returns:
      matrix containing topologically sorted vertex indices, incomplete if graph has cycles

    • addEdge

      public void addEdge(int s, int d, double weight)

    • stronglyconncomp

      public DirectedGraph.SCCResult stronglyconncomp()
      Strongly connected components, with the bottom ones (BSCCs) flagged.

      I[v] is the 1-based component index of vertex v, components numbered by decreasing size (ties broken by discovery order). recurrent[c] is true when no edge leaves component c; for the transition graph of a Markov chain those components are exactly its recurrent classes and the rest are transient.

      Tarjan's algorithm with an explicit depth-first stack. The recursion is unrolled deliberately: this runs on CTMC/DTMC state spaces whose graphs routinely contain paths far longer than the JVM stack can carry, and a recursive formulation overflows on them.

    • toMatrix

      public Matrix toMatrix()