kth.csc.inda
Class HashGraph

java.lang.Object
  extended by kth.csc.inda.HashGraph
All Implemented Interfaces:
Graph

public class HashGraph
extends java.lang.Object
implements Graph

A graph with a fixed number of vertices implemented using adjacency maps. Space complexity is Θ(n + m) where n is the number of vertices and m the number of edges.

Version:
[Date]
Author:
[Name]

Field Summary
 
Fields inherited from interface kth.csc.inda.Graph
NO_COST
 
Constructor Summary
HashGraph(int n)
          Constructs a HashGraph with n vertices and no edges.
 
Method Summary
 void add(int from, int to)
          Inserts a directed edge.
 void add(int from, int to, int c)
          Inserts an edge with edge cost c.
 void addBi(int v, int w)
          Inserts two edges between v and w.
 void addBi(int v, int w, int c)
          Inserts edges with edge cost c between v and w.
 int cost(int v, int w)
          Returns the edge cost if v and w are adjacent and an edge cost has been assigned, NO_COST otherwise.
 int degree(int v)
          Returns the degree of vertex v.
 boolean hasEdge(int v, int w)
          Returns true if there is an edge from v to w.
 VertexIterator neighbors(int v)
          Returns an iterator of vertices adjacent to v.
 int numEdges()
          Returns the number of edges in this graph.
 int numVertices()
          Returns the number of vertices in this graph.
 void remove(int from, int to)
          Removes the edge.
 void removeBi(int v, int w)
          Removes the edges between v and w.
 java.lang.String toString()
          Returns a string representation of this graph.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

HashGraph

public HashGraph(int n)
Constructs a HashGraph with n vertices and no edges. Time complexity: O(n)

Throws:
java.lang.IllegalArgumentException - if n < 0
Method Detail

numVertices

public int numVertices()
Returns the number of vertices in this graph. Time complexity: O(1).

Specified by:
numVertices in interface Graph
Returns:
the number of vertices in this graph

numEdges

public int numEdges()
Returns the number of edges in this graph. Time complexity: O(1).

Specified by:
numEdges in interface Graph
Returns:
the number of edges in this graph

degree

public int degree(int v)
           throws java.lang.IllegalArgumentException
Returns the degree of vertex v.

Specified by:
degree in interface Graph
Parameters:
v - vertex
Returns:
the degree of vertex v
Throws:
java.lang.IllegalArgumentException - if v is out of range

neighbors

public VertexIterator neighbors(int v)
Returns an iterator of vertices adjacent to v.

Specified by:
neighbors in interface Graph
Parameters:
v - vertex
Returns:
an iterator of vertices adjacent to v

hasEdge

public boolean hasEdge(int v,
                       int w)
Returns true if there is an edge from v to w.

Specified by:
hasEdge in interface Graph
Parameters:
v - vertex
w - vertex
Returns:
true if there is an edge from v to w.

cost

public int cost(int v,
                int w)
         throws java.lang.IllegalArgumentException
Returns the edge cost if v and w are adjacent and an edge cost has been assigned, NO_COST otherwise.

Specified by:
cost in interface Graph
Parameters:
v - vertex
w - vertex
Returns:
edge cost if available, NO_COST otherwise
Throws:
java.lang.IllegalArgumentException - if v or w are out of range

add

public void add(int from,
                int to)
Inserts a directed edge. (No edge cost is assigned.)

Specified by:
add in interface Graph
Parameters:
from - vertex
to - vertex

add

public void add(int from,
                int to,
                int c)
Inserts an edge with edge cost c.

Specified by:
add in interface Graph
Parameters:
from - vertex
to - vertex
c - edge cost, c >= 0

addBi

public void addBi(int v,
                  int w)
Inserts two edges between v and w. (No edge cost is assigned.)

Specified by:
addBi in interface Graph
Parameters:
v - vertex
w - vertex

addBi

public void addBi(int v,
                  int w,
                  int c)
Inserts edges with edge cost c between v and w.

Specified by:
addBi in interface Graph
Parameters:
v - vertex
w - vertex
c - edge cost, c >= 0

remove

public void remove(int from,
                   int to)
Removes the edge.

Specified by:
remove in interface Graph
Parameters:
from - vertex
to - vertex

removeBi

public void removeBi(int v,
                     int w)
Removes the edges between v and w.

Specified by:
removeBi in interface Graph
Parameters:
v - vertex
w - vertex

toString

public java.lang.String toString()
Returns a string representation of this graph.

Overrides:
toString in class java.lang.Object
Returns:
a String representation of this graph