Graphs
Definition
A graph is a pair (V, E), where
- V is a set of nodes, called vertices
- E is a collection of pairs of vertices, called edges
- Vertices and edges are positions and store elements
- Applications: Electronic circuits, Transportation networks, Computer Networks, Databases
Example:
- A vertex represents an airport and stores the three-letter airport code
- An edge represents a flight route between two airports and stores the mileage of the route
Edge Types
- Directed edge
- ordered pair of vertices (u,v)
- first vertex u is the origin
- second vertex v is the destination
- e.g., a flight
- Undirected edge
- unordered pair of vertices (u,v)
- e.g., a flight route
- Directed graph
- all the edges are directed
- e.g., flight network
- Undirected graph
- all the edges are undirected
- e.g., route network
Terminology
- End vertices (or endpoints) of an edge
- U and V are the endpoints of a
- Edges incident on a vertex
- a, d, and b are incident on V
- Adjacent vertices
- U and V are adjacent
- Degree of a vertex
- X has degree 5
- Parallel edges
- h and i are parallel edges
- Self-loop
- j is a self-loop
- Path
- sequence of alternating vertices and edges
- begins with a vertex
- ends with a vertex
- each edge is preceded and followed by its endpoints
- Simple path
- path such that all its vertices and edges are distinct
- Examples
- P1=(V,b,X,h,Z) is a simple path
- P2=(U,c,W,e,X,g,Y,f,W,d,V) is a path that is not simple
- Cycle
- circular sequence of alternating vertices and edges
- each edge is preceded and followed by its endpoints
- Simple cycle
- cycle such that all its vertices and edges are distinct
- Examples
- C1=(V,b,X,g,Y,f,W,c,U,a,↵) is a simple cycle
- C2=(U,c,W,e,X,g,Y,f,W,d,V,a,↵) is a cycle that is not simple
Properties
- Property 1
- Σv deg(v) = 2m
Proof: each edge is counted twice
- Σv deg(v) = 2m
- Property 2
- In an undirected graph with no self-loops and no multiple edges
m ≤ n (n − 1)/2
Proof: each vertex has degree at most (n − 1)
- In an undirected graph with no self-loops and no multiple edges
- What is the bound for a directed graph?
Graph ADT
- Vertices and edges
- are positions
- store elements
- Accessor methods
- aVertex()
- incidentEdges(v)
- endVertices(e)
- isDirected(e)
- origin(e)
- destination(e)
- opposite(v, e)
- areAdjacent(v, w)
- Update methods
- insertVertex(o)
- insertEdge(v, w, o)
- insertDirectedEdge(v, w, o)
- removeVertex(v)
- removeEdge(e)
- Generic methods
- numVertices()
- numEdges()
- vertices()
- edges()
Edge List Structure
- Vertex object
- element
- reference to position in vertex sequence
- Edge object
- element
- origin vertex object
- destination vertex object
- reference to position in edge sequence
- Vertex sequence
- sequence of vertex objects
- Edge sequence
- sequence of edge objects
Adjacency List Structure
- Edge list structure
- Incidence sequence for each vertex
- sequence of references to edge objects of incident edges
- Augmented edge objects
- references to associated positions in incidence sequences of end vertices
Adjacency Matrix Structure
- Edge list structure
- Augmented vertex objects
- Integer key (index) associated with vertex
- 2D adjacency array
- Reference to edge object for adjacent vertices
- Null for non nonadjacent vertices
- The “old fashioned” version just has 0 for no edge and 1 for edge
Asymptotic Performance
Code
package graphLib;
import java.io.Serializable;
import examples.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
/**
* A implementation of the Graph interface based on incidence lists (at each vertex a list of
* all the edges incident to this vertex are are stored).
* @author ps
*
* @param <V> the type of the elements stored at the vertices of this graph
* @param <E> the type of the elements stored at the edges of this graph
*/
public class IncidenceListGraph<V,E> implements Graph<V, E> {
/**
*
*/
private static final long serialVersionUID = 1L;
private HashSet<ILGVertex> vertices = new HashSet<ILGVertex>();
private HashSet<ILGEdge> edges = new HashSet<ILGEdge>();
private boolean isDirected = false;
public IncidenceListGraph (){
this(true);
}
public IncidenceListGraph (boolean isDirected){
this.isDirected = isDirected;
}
@Override
public Vertex<V> aVertex() {
if (numberOfVertices() > 0) return vertices.iterator().next();
else return null;
}
@Override
public int numberOfVertices() {
return vertices.size();
}
@Override
public int NumberOfEdges() {
return edges.size();
}
@Override
public boolean isDirected() {
return isDirected;
}
@Override
public Iterator<Vertex<V>> vertices() {
final Iterator<ILGVertex> it = vertices.iterator();
return new Iterator<Vertex<V>>() {
@Override
public boolean hasNext() {
return it.hasNext();
}
@Override
public Vertex<V> next() {
return it.next();
}
@Override
public void remove() {
it.remove();
}
};
}
@Override
public Iterator<Edge<E>> edges() {
final Iterator<ILGEdge> it = edges.iterator();
return new Iterator<Edge<E>>() {
@Override
public boolean hasNext() {
return it.hasNext();
}
@Override
public Edge<E> next() {
return it.next();
}
@Override
public void remove() {
it.remove();
}
};
}
@Override
public Iterator<Edge<E>> incidentEdges(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
final Iterator<Entry<ILGVertex,ILGEdge>> it = w.iEdges.entrySet().iterator();
return new Iterator<Edge<E>>() {
@Override
public boolean hasNext() {
return it.hasNext();
}
@Override
public Edge<E> next() {
return it.next().getValue();
}
@Override
public void remove() {
it.remove();
}
};
}
@Override
public Iterator<Edge<E>> incidentInEdges(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
if (! isDirected) throw new RuntimeException("undirected graph!");
final Iterator<Entry<ILGVertex,ILGEdge>> it = w.inIEdges.entrySet().iterator();
return new Iterator<Edge<E>>() {
@Override
public boolean hasNext() {
return it.hasNext();
}
@Override
public Edge<E> next() {
return it.next().getValue();
}
@Override
public void remove() {
it.remove();
}
};
}
@Override
public Iterator<Edge<E>> incidentOutEdges(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
if (! isDirected) throw new RuntimeException("undirected graph!");
final Iterator<Entry<ILGVertex,ILGEdge>> it = w.outIEdges.entrySet().iterator();
return new Iterator<Edge<E>>() {
@Override
public boolean hasNext() {
return it.hasNext();
}
@Override
public Edge<E> next() {
return it.next().getValue();
}
@Override
public void remove() {
it.remove();
}
};
}
@Override
public int degree(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
return w.iEdges.size();
}
@Override
public int inDegree(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
if (! isDirected) throw new RuntimeException("undirected graph!");
return w.inIEdges.size();
}
@Override
public int outDegree(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
if (! isDirected) throw new RuntimeException("undirected graph!");
return w.outIEdges.size();
}
@Override
public Vertex<V> origin(Edge<E> e) {
ILGEdge iEdge = (ILGEdge) e;
if (iEdge.thisGraph != this) throw new RuntimeException("Invalid Edge!");
if (! isDirected) throw new RuntimeException("undirected graph!");
return iEdge.from;
}
@Override
public Vertex<V> destination(Edge<E> e) {
ILGEdge iEdge = (ILGEdge) e;
if (iEdge.thisGraph != this) throw new RuntimeException("Invalid Edge!");
if (! isDirected) throw new RuntimeException("undirected graph!");
return iEdge.to;
}
@Override
public Vertex<V>[] endVertices(Edge<E> e) {
ILGEdge iEdge = (ILGEdge) e;
if (iEdge.thisGraph != this) throw new RuntimeException("Invalid Edge!");
Vertex <V> [] v = new Vertex[2];
v[0]=iEdge.from;
v[1]=iEdge.to;
return (Vertex<V> []) v;
}
@Override
public boolean areAdjacent(Vertex<V> v1, Vertex<V> v2) {
ILGVertex w1 = (ILGVertex) v1;
if (w1.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
ILGVertex w2 = (ILGVertex) v2;
if (w2.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
return (w1.iEdges.get(w2)!=null);
}
@Override
public Vertex<V> insertVertex(V elem) {
ILGVertex v = new ILGVertex(elem);
vertices.add(v);
return v;
}
@Override
public Edge<E> insertEdge(Vertex<V> from, Vertex<V> to, E elem) {
ILGVertex fromV = (ILGVertex) from;
if (fromV.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
ILGVertex toV = (ILGVertex) to;
if (toV.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
ILGEdge ed = new ILGEdge(elem, fromV, toV);
edges.add(ed);
return ed;
}
@Override
public E removeEdge(Edge<E> e) {
ILGEdge iEdge = (ILGEdge) e;
if (iEdge.thisGraph != this) throw new RuntimeException("Invalid Edge!");
if (isDirected){
iEdge.from.outIEdges.remove(iEdge.to);
iEdge.to.inIEdges.remove(iEdge.from);
}
iEdge.from.iEdges.remove(iEdge.to);
iEdge.to.iEdges.remove(iEdge.from);
edges.remove(iEdge);
iEdge.thisGraph = null;
return iEdge.element();
}
@Override
public V removeVertex(Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
// first we remove all edges!
Object [] el = new Object[degree(w)];
el = w.iEdges.entrySet().toArray();
for (Object e:el){
removeEdge((ILGEdge)((Map.Entry)e).getValue());
}
vertices.remove(w);
w.thisGraph=null;
return w.element;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString(){
StringBuffer sb = new StringBuffer();
String con = "---";
if (isDirected){
sb.append("Type: directed\n");
con = "-->";
}
else sb.append("Type: undirected\n");
sb.append("Vertices:\n");
Iterator<ILGVertex> it = vertices.iterator();
while (it.hasNext()){
ILGVertex v = it.next();
sb.append(" "+v.toString()+"\n");
Iterator<Edge<E>> eit;
if (! isDirected){
eit = incidentEdges(v);
if (eit.hasNext()) sb.append(" Incident Edges:\n");
while(eit.hasNext()){
Edge<E> e = eit.next();
sb.append(" "+e.toString()+"\n");
}
}
else {
eit = incidentOutEdges(v);
if (eit.hasNext()) sb.append(" outgoing Edges:\n");
while(eit.hasNext()){
Edge<E> e = eit.next();
sb.append(" "+e.toString()+"\n");
}
eit = incidentInEdges(v);
if (eit.hasNext()) sb.append(" incoming Edges:\n");
while(eit.hasNext()){
Edge<E> e = eit.next();
sb.append(" "+e.toString()+"\n");
}
}
}
sb.append("Edges:\n");
Iterator<ILGEdge> eit = edges.iterator();
while (eit.hasNext()){
ILGEdge ev= eit.next();
sb.append(ev.from.toString() +con+ev.to.toString()+" "+ev.toString()+"\n");
}
return sb.toString();
}
@Override
public Vertex<V> opposite(Edge<E> e, Vertex<V> v) {
ILGVertex w = (ILGVertex) v;
if (w.thisGraph != this) throw new RuntimeException("Invalid Vertex!");
ILGEdge iEdge = (ILGEdge) e;
if (iEdge.thisGraph != this) throw new RuntimeException("Invalid Edge!");
if (iEdge.from==w) return iEdge.to;
else if (iEdge.to==w) return iEdge.from;
else throw new RuntimeException(w+" is not an endpoint of "+iEdge);
}
private class ILGVertex extends IGLDecorable implements Vertex<V>{
private V element;
private IncidenceListGraph<V,E> thisGraph = IncidenceListGraph.this;
private HashMap<ILGVertex,ILGEdge> iEdges;
private HashMap<ILGVertex,ILGEdge> inIEdges;
private HashMap<ILGVertex,ILGEdge> outIEdges;
public ILGVertex(V e){
iEdges = new HashMap<ILGVertex,ILGEdge>(4);
if (isDirected){
inIEdges = new HashMap<ILGVertex,ILGEdge>(4);
outIEdges = new HashMap<ILGVertex,ILGEdge>(4);
}
element=e;
}
@Override
public V element() {
return element;
}
public String toString(){
if (element == null) return "null";
else return element.toString();
}
}
private class ILGEdge extends IGLDecorable implements Edge<E> {
private E element;
private Object thisGraph = IncidenceListGraph.this;
private ILGVertex from;
private ILGVertex to;
public ILGEdge(E e, ILGVertex from, ILGVertex to){
element=e;
this.from = from;
this.to = to;
if (isDirected){
if (from.outIEdges.containsKey(to)) throw new RuntimeException("Parallel edges not allowed!");
from.outIEdges.put(to,this);
to.inIEdges.put(from, this);
}
if (! isDirected && from.iEdges.containsKey(to)) throw new RuntimeException("Parallel edges not allowed!");
from.iEdges.put(to,this);
to.iEdges.put(from, this);
}
@Override
public E element() {
return element;
}
public String toString(){
if (element == null) return "null";
else return element.toString();
}
}
private class IGLDecorable implements Decorable {
private HashMap<Object,Object> attrs = new HashMap<Object,Object>(2);
private final Object DUMMY = new Serializable(){};
@Override
public Object get(Object attr) {
Object ret = attrs.get(attr);
if (ret==null) throw new RuntimeException("no attribute "+attr);
if (ret==DUMMY) ret=null;
return ret;
}
@Override
public boolean has(Object attr) {
Object o = attrs.get(attr);
return (o!=null);
}
@Override
public void set(Object attr, Object val) {
Object value = DUMMY;
if (val != null) value = val;
attrs.put(attr, value);
}
@Override
public Object destroy(Object attr) {
Object ret = attrs.get(attr);
if (ret != null) attrs.remove(attr);
return ret;
}
@Override
public void clearAll() {
attrs.clear();
}
}
}