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