# Graphs/ADT

### From charlesreid1

Graphs abstract data types.

See also: Graphs/Java/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

Members:

- Nearly every implementation of a graph maintains two lists: a list of vertices and a list of edges

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

# Code

See http://git.charlesreid1.com/cs/java repository, graphs folder.

# Flags