|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectkth.csc.inda.HashGraph
public class HashGraph
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.
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 |
---|
public HashGraph(int n)
java.lang.IllegalArgumentException
- if n < 0Method Detail |
---|
public int numVertices()
numVertices
in interface Graph
public int numEdges()
numEdges
in interface Graph
public int degree(int v) throws java.lang.IllegalArgumentException
degree
in interface Graph
v
- vertex
java.lang.IllegalArgumentException
- if v is out of rangepublic VertexIterator neighbors(int v)
neighbors
in interface Graph
v
- vertex
public boolean hasEdge(int v, int w)
hasEdge
in interface Graph
v
- vertexw
- vertex
public int cost(int v, int w) throws java.lang.IllegalArgumentException
cost
in interface Graph
v
- vertexw
- vertex
java.lang.IllegalArgumentException
- if v or w are out of rangepublic void add(int from, int to)
add
in interface Graph
from
- vertexto
- vertexpublic void add(int from, int to, int c)
add
in interface Graph
from
- vertexto
- vertexc
- edge cost, c >= 0public void addBi(int v, int w)
addBi
in interface Graph
v
- vertexw
- vertexpublic void addBi(int v, int w, int c)
addBi
in interface Graph
v
- vertexw
- vertexc
- edge cost, c >= 0public void remove(int from, int to)
remove
in interface Graph
from
- vertexto
- vertexpublic void removeBi(int v, int w)
removeBi
in interface Graph
v
- vertexw
- vertexpublic java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |