“Modern” adjacency list with incidence containers

“Modern” adjacency list with incidence containers

An extension to the Edge list graph data structure, where each vertex also stores a sequence of edges that are incident on it

• The edge sequence itself should have pointers to the incidence containers in which it is contained for efficiency

Note

This is the adjacency list type covered at The University of Sydney

Use a doubly linked list as the container for $V$ and $E$ for optimal time complexity

Using an array is easier but things like removeEdge will become $O(n)$ due to increased deletion time complexity

Time complexities

Where $n$ is the # of vertices, $m$ is the # of edges

Operation	Complexity	Notes
Space	$O(n+m)$	E list $O(m)$, V list $O(n)$, incidence list composed of edges, so $O(2m)=O(m)$
insertVertex(x)	$O(1)$	Add to V sequence
insertEdge(u,v,x)	$O(1)$	Add to E sequence, update incidence containers for 2 vertices
removeVertex(v)	$O(deg(v))$	Traverse vertex’s incidence container for incident edges to remove
removeEdge(e)	$O(1)$	Remove self from its 2 incidence containers (pointers stored), remove from E
degree(v)	$O(1)$	Track size of incidence container
incidentEdges(v)	$O(deg(v))$	Traverse incidence container to return each
getEdge(u,v)	$O(min(deg(u),deg(v)))$	Get degree of the 2 vertices, traverse incidence of smaller to check existence of edge
endVerticesOf(e)	$O(1)$	Edge pointer given - return the relevant vertex pointers
opposite(v,e)	$O(1)$	Edge pointer given - return other vertex
vertices()	$O(n)$	Traverse V
edges()	$O(m)$	Traverse E
numVertices()	$O(1)$	Dependent on a counter variable
numEdges()	$O(1)$	Dependent on a counter variable

Directed graph information

See this link