org.metasyntactic.math
Interface DirectedGraph

All Superinterfaces:

Graph

public interface DirectedGraph

extends Graph

Nested Class Summary

static class

DirectedGraph.DirectedEdge

Nested classes inherited from class org.metasyntactic.math.Graph

Graph.Path

Method Summary

int	inDegree(java.lang.Object vertex) In a directed graph, the in-degree of a vertex is the number of edges entering it.
boolean	isStronglyConnected() A directed class is strongly connected if every two vertices are reachable from each other.
int	outDegree(java.lang.Object vertex) In a directed graph, the out-degree of a vertex is the number of edges leaving it
UndirectedGraph	toUndirectedGraph() Given a directed graph G = (V, E), the undirected graph of G is the undirected graph G' = (V, E'), where (u, v) ∈ E' if and only if u ≠ v and (u, v) ∈ E.

Methods inherited from interface org.metasyntactic.math.Graph

addEdge, addVertex, areAdjacent, containsEdge, containsVertex, degree, getEdges, getVertices, induce, isReachable, isSubgraph

Method Detail

toUndirectedGraph

public UndirectedGraph toUndirectedGraph()

Given a directed graph G = (V, E), the undirected graph of G is the undirected graph G' = (V, E'), where (u, v) ∈ E' if and only if u ≠ v and (u, v) ∈ E. That is, the undirected version contains the edges of G "with their directions removed" and with self-loops eliminated. (Since (u, v) and (v, u) are the same edge in an undirected graph, the undirected version of a directed graph contains it only once, even if the directed graph contains both edges (u, v) and (v, u).)

isStronglyConnected

public boolean isStronglyConnected()

A directed class is strongly connected if every two vertices are reachable from each other.

Returns:

true If this directed graph is strongly connected

outDegree

public int outDegree(java.lang.Object vertex)

In a directed graph, the out-degree of a vertex is the number of edges leaving it

Parameters:

vertex - The vertex you want to find out how many edges leave from

Returns:

the number of edges leaving this vertex

inDegree

public int inDegree(java.lang.Object vertex)

In a directed graph, the in-degree of a vertex is the number of edges entering it.

Parameters:

vertex - The vertex you want to find out how many edges enter

Returns:

The number of edges entering this vertex