Implementation of Vertex

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.

	*Vertex Implementation*	*Abstract* *Vertex*	*Linked* *Vertex*
	constructor (Object label)	O(1)	O(1)

*void*	clearMark ()	O(1)
*Object*	getLabel ()	O(1)
*boolean*	isMarked ()	O(1)
*void*	setLabel (Object label)	O(1)
*void*	setMark ()	O(1)
*String*	toString	O(1)

*Protected methods needed by LinkedVertex in order to support LinkedDirectedGraph*

*void*	addEdgeTo (LinkedVertex toVertex, Object edgeLabel)		O(m/n)
*void*	addEdgeTo (LinkedVertex toVertex, GraphSubEdge subEdge)		O(m/n)
*GraphEdge*	getEdgeTo (LinkedVertex toVertex)		O(m/n)
*Iterator*	incidentEdges ()		O(1)
*Iterator*	neighboringVertices ()		O(1)
*boolean*	removeEdgeTo (LinkedVertex toVertex)		O(m/n)

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 the methods based on assumption that the underlying Map of vertices has basic operations of O(1).