dataStructures
Class Graph

java.lang.Object
  |
  +--dataStructures.Graph
Direct Known Subclasses:
AdjacencyDigraph, AdjacencyWDigraph, LinkedDigraph

public abstract class Graph
extends java.lang.Object


Constructor Summary
Graph()
           
 
Method Summary
 void bellmanFord(int s, Operable[] d, int[] p, Operable theZero)
          Bellman and Ford algorithm to find the shortest paths from vertex s.
 void bfs(int v, int[] reach, int label)
          breadth-first search reach[i] is set to label for all vertices reachable from vertex v
 int bipartiteCover(int[] theLabel, int[] theCover)
           
 boolean connected()
           
abstract  int degree(int i)
           
 void dfs(int v, int[] reach, int label)
          depth-first search reach[i] is set to label for all vertices reachable from vertex v
abstract  int edges()
           
abstract  boolean existsEdge(int i, int j)
           
 int[] findPath(int s, int d)
          find a path from s to d
abstract  int inDegree(int i)
           
abstract  java.util.Iterator iterator(int i)
           
 boolean kruskal(WeightedEdge[] spanningTreeEdges)
          find a min cost spanning tree using Kruskal's method
 int labelComponents(int[] c)
          label the components of an undirected graph
abstract  int outDegree(int i)
           
abstract  void putEdge(java.lang.Object theEdge)
           
abstract  void removeEdge(int i, int j)
           
 boolean topologicalOrder(int[] theOrder)
           
 void verifyDirected(java.lang.String theMethodName)
          verify that the graph is a directed graph
 void verifyUndirected(java.lang.String theMethodName)
          verify that the graph is an undirected graph
 void verifyWeighted(java.lang.String theMethodName)
          verify that the graph is a weighted graph
 void verifyWeightedUndirected(java.lang.String theMethodName)
          verify that the graph is a weighted undirected graph
abstract  int vertices()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Graph

public Graph()
Method Detail

vertices

public abstract int vertices()

edges

public abstract int edges()

existsEdge

public abstract boolean existsEdge(int i,
                                   int j)

putEdge

public abstract void putEdge(java.lang.Object theEdge)

removeEdge

public abstract void removeEdge(int i,
                                int j)

degree

public abstract int degree(int i)

inDegree

public abstract int inDegree(int i)

outDegree

public abstract int outDegree(int i)

iterator

public abstract java.util.Iterator iterator(int i)

bfs

public void bfs(int v,
                int[] reach,
                int label)
breadth-first search reach[i] is set to label for all vertices reachable from vertex v

dfs

public void dfs(int v,
                int[] reach,
                int label)
depth-first search reach[i] is set to label for all vertices reachable from vertex v

findPath

public int[] findPath(int s,
                      int d)
find a path from s to d
Returns:
the path in an array using positions 0 on up

verifyUndirected

public void verifyUndirected(java.lang.String theMethodName)
verify that the graph is an undirected graph
Throws:
UndefinedMethodException - if graph is directed

verifyDirected

public void verifyDirected(java.lang.String theMethodName)
verify that the graph is a directed graph
Throws:
UndefinedMethodException - if graph is undirected

verifyWeightedUndirected

public void verifyWeightedUndirected(java.lang.String theMethodName)
verify that the graph is a weighted undirected graph
Throws:
UndefinedMethodException - if graph is not weighted and undirected

verifyWeighted

public void verifyWeighted(java.lang.String theMethodName)
verify that the graph is a weighted graph
Throws:
UndefinedMethodException - if graph is not weighted

connected

public boolean connected()
Returns:
true iff graph is connected

labelComponents

public int labelComponents(int[] c)
label the components of an undirected graph
Returns:
the number of components set c[i] to be the component number of vertex i

topologicalOrder

public boolean topologicalOrder(int[] theOrder)
Parameters:
theOrder[0:n-1] - is set to a topological order when such an order exists
Returns:
false iff the digraph has no topological order

bipartiteCover

public int bipartiteCover(int[] theLabel,
                          int[] theCover)
Parameters:
theLabel - is bipartite labeling, theLabel[i] = 1 iff i is in A
theCover - theCover[i], i >= 0 is set to the cover (if there is one)
Returns:
-1 if the bipartite graph has no cover

kruskal

public boolean kruskal(WeightedEdge[] spanningTreeEdges)
find a min cost spanning tree using Kruskal's method
Parameters:
spanningTreeEdges[0:n-2] - has the min-cost-tree edges when done
Returns:
false iff the weighted undirected graph is not connected

bellmanFord

public void bellmanFord(int s,
                        Operable[] d,
                        int[] p,
                        Operable theZero)
Bellman and Ford algorithm to find the shortest paths from vertex s. Graph may have edges with negative cost but should not have a cycle with negative cost.
Parameters:
theZero - equals zero weight
Returns:
shortest distances from s are returned in d