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:

• UndirectedGraph
• Matrix

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DirectedGraph.SCCAuxResult
static class	DirectedGraph.SCCResult

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
void	addEdge(int s, int d, double weight)
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.
DirectedGraph.SCCResult	stronglyconncomp()
Matrix	toMatrix()

Methods inherited from class java.lang.Object

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

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()

toMatrix

public Matrix toMatrix()