dataStructures
Class AdjacencyWDigraph

java.lang.Object
  |
  +--dataStructures.Graph
        |
        +--dataStructures.AdjacencyWDigraph
Direct Known Subclasses:
AdjacencyWGraph

public class AdjacencyWDigraph
extends Graph


Constructor Summary
AdjacencyWDigraph()
           
AdjacencyWDigraph(int theVertices)
           
 
Method Summary
 void allPairs(Operable[][] c, int[][] kay)
          dynamic programming all pairs shortest paths algorithm compute c[i][j] and kay[i][j] for all i and j
 java.lang.Object btSalesperson(int[] bestTour, Operable theZero)
          traveling salesperson by backtracking
 int degree(int i)
          this method is undefined for directed graphs
 int edges()
           
 boolean existsEdge(int i, int j)
           
 int inDegree(int i)
           
 java.util.Iterator iterator(int i)
          create and return an iterator for vertex i
 java.lang.Object leastCostBBSalesperson(int[] bestTour, Operable theZero)
          least-cost branch-and-bound code to find a shortest tour
static void main(java.lang.String[] args)
          test program for Graph methods
 int outDegree(int i)
           
 void output()
          output the adjacency matrix
 void putEdge(java.lang.Object theEdge)
          put edge e into the digraph; if the edge is already there, update its weight to e.weight
 void removeEdge(int i, int j)
          remove the edge (i,j)
 void shortestPaths(int sourceVertex, Operable[] distanceFromSource, int[] predecessor)
          find shortest paths from sourceVertex
 int vertices()
           
 
Methods inherited from class dataStructures.Graph
bellmanFord, bfs, bipartiteCover, connected, dfs, findPath, kruskal, labelComponents, topologicalOrder, verifyDirected, verifyUndirected, verifyWeighted, verifyWeightedUndirected
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AdjacencyWDigraph

public AdjacencyWDigraph(int theVertices)

AdjacencyWDigraph

public AdjacencyWDigraph()
Method Detail

vertices

public int vertices()
Returns:
number of vertices
Overrides:
vertices in class Graph

edges

public int edges()
Returns:
number of edges
Overrides:
edges in class Graph

existsEdge

public boolean existsEdge(int i,
                          int j)
Returns:
true iff (i,j) is an edge
Overrides:
existsEdge in class Graph

putEdge

public void putEdge(java.lang.Object theEdge)
put edge e into the digraph; if the edge is already there, update its weight to e.weight
Throws:
java.lang.IllegalArgumentException - when theEdge is invalid
Overrides:
putEdge in class Graph

removeEdge

public void removeEdge(int i,
                       int j)
remove the edge (i,j)
Overrides:
removeEdge in class Graph

degree

public int degree(int i)
this method is undefined for directed graphs
Overrides:
degree in class Graph

outDegree

public int outDegree(int i)
Returns:
out-degree of vertex i
Throws:
java.lang.IllegalArgumentException - when i is not a valid vertex
Overrides:
outDegree in class Graph

inDegree

public int inDegree(int i)
Returns:
in-degree of vertex i
Throws:
java.lang.IllegalArgumentException - when i is not a valid vertex
Overrides:
inDegree in class Graph

output

public void output()
output the adjacency matrix

iterator

public java.util.Iterator iterator(int i)
create and return an iterator for vertex i
Throws:
java.lang.IllegalArgumentException - when i is an invalid vertex
Overrides:
iterator in class Graph

shortestPaths

public void shortestPaths(int sourceVertex,
                          Operable[] distanceFromSource,
                          int[] predecessor)
find shortest paths from sourceVertex
Returns:
shortest distances in distanceFromSource
Throws:
java.lang.IllegalArgumentException - when sourceVertex is not a vertex of the graph

allPairs

public void allPairs(Operable[][] c,
                     int[][] kay)
dynamic programming all pairs shortest paths algorithm compute c[i][j] and kay[i][j] for all i and j

btSalesperson

public java.lang.Object btSalesperson(int[] bestTour,
                                      Operable theZero)
traveling salesperson by backtracking
Parameters:
theZero - zero weight
bestTour - bestTour[1:n] is set to best tour
Returns:
cost of best tour

leastCostBBSalesperson

public java.lang.Object leastCostBBSalesperson(int[] bestTour,
                                               Operable theZero)
least-cost branch-and-bound code to find a shortest tour
Parameters:
theZero - zero weight
bestTour - bestTour[i] set to i'th vertex on shortest tour
Returns:
cost of shortest tour

main

public static void main(java.lang.String[] args)
test program for Graph methods