Implementation of Graph
Warning: The implementation
of several methods has been left as an exercise.
The table
below indicates where methods are implemented and the time complexity of these methods. Some methods are implemented in more than one
place. When this happens, each entry
overrides the entries to its left. When an entry says "based on iterator" or
"traverse iterator" or "uses size," then the time complexity depends
on the iterator or size method.
|
|
Graph Implementation
|
Abstract
Container
|
Abstract
Graph
|
Linked
Directed
Graph
|
Linked
Undirected
Graph
|
|
|
constructor ()
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
|
|
constructor
(Collection col)
|
|
O(n)
|
O(n)
|
O(n)
|
|
|
constructor
(Iterator iter)
|
|
O(n)
|
O(n)
|
O(n)
|
|
|
|
|
|
|
|
| void
|
addEdge
(Object fromLabel,
Object toLabel,
Object edgeLabel)
|
|
|
O(1)
|
O(1)
|
| void
|
addVertex
(Object label)
|
|
abstract
|
O(1)
|
|
| void
|
clear ()
|
O(1)
|
O(1)
|
|
|
| void
|
clearEdgeMarks ()
|
|
travserse edges iterator
|
|
|
| void
|
clearVertexMarks ()
|
|
travserse vertices iterator
|
|
|
| Object
|
clone ()
|
|
|
exercise
|
|
| Collection
|
collectionView ()
|
based on iterator
|
|
|
|
| boolean
|
containsEdge
(Object fromLabel,
Object toLabel)
|
|
uses getEdge method
|
|
|
| boolean
|
containsVertex
(Object label)
|
|
O(1)
|
|
|
| Iterator
|
edges ()
|
|
abstract
|
O(1)
|
O(1)
|
| boolean
|
equals (Object other)
|
|
exercise
|
|
|
| Edge
|
getEdge
(Object fromLabel,
Object toLabel)
|
|
abstract
|
O(m/n)
|
|
| Vertex
|
getVertex (Object labe)
|
|
O(1)
|
|
|
| int
|
hashCode ()
|
traverse iterator
|
exercise
|
|
|
| Iterator
|
incidentEdges (Vertex
vertex)
|
|
|
O(1)
|
|
| boolean
|
isEmpty
|
uses size method
|
|
|
|
| Iterator
|
iterator ()
|
abstract
|
O(1)
|
|
|
| Iterator
|
neighboringVertices
(Vertex vertex)
|
|
|
O(1)
|
|
| boolean
|
removeEdge
(Object fromLabel,
Objec toLabel)
|
|
|
O(m/n)
|
O(m/n)
|
| boolean
|
removeVertex
(Object label)
|
|
|
O (max(m,n))
|
O (max(m,n))
|
| int
|
size ()
|
O(1)
|
|
|
|
| int
|
sizeEdges ()
|
|
O(1)
|
|
|
| int
|
sizeVertices ()
|
|
O(1)
|
|
|
| Object []
|
toArray ()
|
traverse iterator
|
|
|
|
| String
|
toString ()
|
traverse iterator
|
traverse vertices and edges iterators
|
|
|
| Iterator
|
vertices ()
|
|
O(1)
|
|
|
Notes on the above
· n = number of vertices
· m = number of edges
· m/n = max (average number of edges
leaving each vertex, 1)
·
Complexity of
methods based on assumption that the underlying Map of vertices has basic operations of
O(1).