(1st) pages 344-355 (Section 9.1.1 and 9.2.1)
(2nd) pages 544-550 (Section 12.2.1 and 12.2.1)
A cycle is a path
Proof of Proposition 9.11/Proposition 12.11: PostScript and PDF
Implementation of a simple graph by means of an edge list: PostScript and PDF
In order to be able to remove an edge from the set of edges in O(1), we implement the set of edges by means of a List implemented by means of a doubly linked list.
List edges = new DLList();The interface Edge is implemented by the class
public class ELEdge implements Edge { private Object element; // element stored in this edge private boolean isDirected; // this edge is directed? private Vertex origin; // origin of this edge if it is directed, otherwise one of the end vertices private Vertex destination; // destination of this edge if it is directed, otherwise the other end vertex private Position position // position of the List in which this edge is stored .... }A directed edge from vertex origin to vertex destination with element element can be added to edges as follows.
Edge edge = new ELEdge(element, true, origin, destination, null); Position position = edges.insertFirst(edge); edge.setPosition(position);The edge edge can now be removed from edges as follows.
edges.remove(edge.getPosition);