kth.csc.inda
Class MatrixGraph

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

public class MatrixGraph
extends java.lang.Object
implements Graph

A graph with a fixed number of vertices implemented using an adjacency matrix. Space complexity is Θ(n2), where n is the number of vertices.

Version:
2013-01-01
Author:
Stefan Nilsson

Field Summary
 
Fields inherited from interface kth.csc.inda.Graph
NO_COST
 
Constructor Summary
MatrixGraph(int n)
          Constructs a MatrixGraph 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

MatrixGraph

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

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. Time complexity: O(n), where n is the number of vertices.

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)
                         throws java.lang.IllegalArgumentException
Returns an iterator of vertices adjacent to v. Time complexity: O(n), where n is the number of vertices.

Specified by:
neighbors in interface Graph
Parameters:
v - vertex
Returns:
an iterator of vertices adjacent to v
Throws:
java.lang.IllegalArgumentException - if v is out of range

hasEdge

public boolean hasEdge(int v,
                       int w)
                throws java.lang.IllegalArgumentException
Returns true if there is an edge from v to w. Time complexity: O(1).

Specified by:
hasEdge in interface Graph
Parameters:
v - vertex
w - vertex
Returns:
true if there is an edge from v to w.
Throws:
java.lang.IllegalArgumentException - if v or w are out of range

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. Time complexity: O(1).

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)
         throws java.lang.IllegalArgumentException
Inserts a directed edge. (No edge cost is assigned.) Time complexity: O(1).

Specified by:
add in interface Graph
Parameters:
from - vertex
to - vertex
Throws:
java.lang.IllegalArgumentException - if from or to are out of range

add

public void add(int from,
                int to,
                int c)
         throws java.lang.IllegalArgumentException
Inserts an edge with edge cost c. Time complexity: O(1).

Specified by:
add in interface Graph
Parameters:
from - vertex
to - vertex
c - edge cost, c >= 0
Throws:
java.lang.IllegalArgumentException - if from or to are out of range

addBi

public void addBi(int v,
                  int w)
           throws java.lang.IllegalArgumentException
Inserts two edges between v and w. (No edge cost is assigned.) Time complexity: O(1).

Specified by:
addBi in interface Graph
Parameters:
v - vertex
w - vertex
Throws:
java.lang.IllegalArgumentException - if v or w are out of range

addBi

public void addBi(int v,
                  int w,
                  int c)
           throws java.lang.IllegalArgumentException
Inserts edges with edge cost c between v and w. Time complexity: O(1).

Specified by:
addBi in interface Graph
Parameters:
v - vertex
w - vertex
c - edge cost, c >= 0
Throws:
java.lang.IllegalArgumentException - if v or w are out of range

remove

public void remove(int from,
                   int to)
            throws java.lang.IllegalArgumentException
Removes the edge. Time complexity: O(1).

Specified by:
remove in interface Graph
Parameters:
from - vertex
to - vertex
Throws:
java.lang.IllegalArgumentException - if from or to are out of range

removeBi

public void removeBi(int v,
                     int w)
              throws java.lang.IllegalArgumentException
Removes the edges between v and w. Time complexity: O(1).

Specified by:
removeBi in interface Graph
Parameters:
v - vertex
w - vertex
Throws:
java.lang.IllegalArgumentException - if v or w are out of range

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