Package jline.util.graph

Class DirectedGraph

  • All Implemented Interfaces:
    
public class DirectedGraph

    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

    • Field Summary

      Fields 
      Modifier and Type Field Description

    • Constructor Summary

      Constructors 
      Constructor Description
      DirectedGraph(Matrix param, Set<Integer> colsToIgnore) Constructs a directed graph with the given adjacency matrix and column filter.
      DirectedGraph(Matrix param) Constructs a directed graph with the given adjacency matrix (no column filtering).

    • Enum Constant Summary

      Enum Constants 
      Enum Constant Description

    • Method Summary

      Modifier and Type Method Description
      static boolean isDAG(Matrix adj) Tests if the given adjacency matrix represents a Directed Acyclic Graph (DAG).
      static Matrix kahn(Matrix adj) Performs topological sorting using Kahn's algorithm.
      void addEdge(int s, int d, double weight)
      DirectedGraph.SCCResult stronglyconncomp()
      Matrix toMatrix()

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • DirectedGraph

        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

        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 Detail

      • isDAG

         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

         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

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