Graphs/ADT

Notes

Graphs are composed of three basic object types:

• Vertex/Node
• Edge
• Graph

The vertex stores information specific to the vertex - typically a data element, plus additional info required by the data structure used (see Graphs/Data Structures).

Vertex ADT

• element() - get the data element associated with this node

Edge ADT

• element() - get the data element associated with this edge

Graph ADT

Size/count methods:

• numVertices() - returns number of vertices on graph
• numEdges() - returns number of edges on graph

Sets methods:

• vertices() - return set of vertices V
• edges() - return set of edges E

Get methods:

• getEdge(u,v) - given two vertices, return the edge that connects them (if any)
• endVertices(e) - get a pair of vertices at the endpoints of the given edge
• opposite(v,e) - for a given vertex and edge, get the vertex at the other end of the edge
• outgoingEdges(v) - return a set of outgoing edges from vertex v
• incomingEdges(v) - return a set of incoming edges to vertex v

Modification methods:

• insertVertex(x) - insert a new Vertex object storing data element x
• insertEdge(u,v,y) - insert a new Edge object storing data element y that connects vertices u and v
• removeVertex(v) - remove vertex v and any connecting edges from the graph
• removeEdge(e) - remove edge e from the graph