Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD