Graph Representations
and Algorithms
Representation of a Graph
A Graph G is a set of Vertices and Edges G = {V, E}
Routers
Consider
the graph shown above. This graph
illustrates a set of routers connecting several networks on the various
campuses of a large (hypothetical)
A Graph interface (to
be implemented with GraphMatrix or GraphList)
//package teneyck.graphstuff;
import java.util.*; //Iterator
public interface Graph {
public void add(Object label);
//precondition: label is a non-null label for a vertex
//post_condition: a vertex with label is added to the graph
// if a vertex with label is already present, no
// action
public void addEdge(Object vrtx1, Object vrtx2, Comparable label);
//precondition: vrtx1 and vrtx2 are labels of existing vertices
//post-condition: and edge (possibly directed) is inserted between
// vrtx1 and vrtx2.
public Object remove(Object label);
//precondition: label is non-null vertex label
//post-condition: vertex with this label is removed, if found
public Object removeEdge(Object vrtx1, Object vrtx2);
//precondition: vertex1 and vertex2 are existing vertex labels
//post-condition: edge is removed and its label returned
public Object get(Object label);
//precondition: none
//post-condition: returns the label of the indicated vertex
public Vertex getVertex(Object label);
//precondition: none
//post-condition: returns the Vertex of the indicated label
public Edge getEdge(Object vrtx1, Object vrtx2);
//post-condition: returns label of edge between the two verices
public boolean contains(Object label);
//post-condition: returns true if vertex with this label is present
public boolean containsEdge(Object vrtx1, Object vrtx2);
//post-condition: returns true if edge between vertices exists
public boolean visit(Object label);
//post-condition: sets visited flag to true, returns previous value
public boolean visitEdge(Edge e);
//post-condition: sets visited flag on edge, returns previous value
public boolean isVisited(Object label);
//post-condition: returns value of visited flag of labeled vertex
public boolean isVisitedEdge(Edge e);
//post-condition: returns value of visited flag on edge
public void reset( );
//post-condition: resets all visited flags to false
public int size( );
//post-condition: returns the number of vertices in the graph
public int degree(Object label);
//precondition: label identifies an existing vertex
//post-condition: returns the number of vertices adjacent to vertex
public int edgeCount( );
//post-condition: returns the number of edges in the graph;
public Iterator iterator( );
//post-condition: returns an iterator across all vertices in the graph
public Iterator neighbors(Object label);
//precondition: label identifies an existing vertex
//post-condition: returns an iterator over the adjacent, out-going
// vertices from the labeled vertex
public Iterator edges( );
//post-condition: returns an iterator over edges in the graph
// each edge is visited once.
public void clear( );
//post-condition: removes all vertices (and edges) from the graph
public boolean isEmpty( );
//post-condition: returns true if graph contains no vertices
public boolean isDirected( );
//post-condition: returns true is edges of graph are directed
}
A
graph can be represented by either an Adjacency Matrix or an Adjacency List
Adjacency Matrix
Representation
In
the Adjacency Matrix Representation, we represent the graph as an n x n boolean matrix whose rows and
columns represent the source vertex and destination vertex number of an
edge. An entry of true in a position such as row = 0, column = 1 indicates that there
is an edge from vertex 0 to vertex 1. In
this example there are 25 possible directed edges, but only 8 exist. This is symptomatic of the inefficiency of
the adjacency matrix approach.
In
an undirected graph, whenever there is an edge connecting vertices i and j there will also be a connection
between j and i. The matrix representing an undirected graph
will be symmetrical.
In
our implementation of GraphMatrix we have the
following data structures:
protected
int size; //allocation size for the graph
protected Edge
data[][]; //the implementation
will use an array of edges
//the
absence of an edge will be indicated by null
protected Hashtable dict; //translates
labels into vertices
protected List freeList; //available indices in matrix
protected
boolean directed;
Adjacency List
Representation
In
the Adjacency List representation, an array, indexed by the vertex number, of
linked lists is maintained where each vertex entry holds a list of other
vertices that are neighbors via a directed edge from the indexed vertex to that
neighbor. In this representation, only
the actual edges appear. One does not
have to traverse an entire row of possibilities to find the neighbors of a
given vertex. For an undirected graph,
if, for instance, vertex 1 appears in the adjacency list of vertex 0, then
vertex 0 will also appear in the adjacency list of vertex 1.
In
our implementation of GraphList we have the following
data structures:
protected
int size; //allocation size for the graph
protected List
data[]; //the implementation
will use an
//array
of vertices with linked Lists of edges
protected Hashtable dict; //translates
labels into vertices
protected List freeList; //available indices in the graph
protected
boolean directed;
We extend
class Vertex to add a linked list of edges (to other adjacent vertices) as a
data field
class GraphListVertex
extends Vertex {
protected
List adjacencies;
public
GraphListVertex (Object key)
//post: constructs a new vertex with an empty
list of adjacencies
super(key); //init Vertex fields
adjacencies
= new LinkedList(
);
}
Depth-first search
public static List depthFirstSearch (Graph g) {
//pre: G is non-null
//post: returns list of
vertices in reverse order of when visited
List myList = new
LinkedList( )
Iterator itr = g.iterator(
);
itr.reset( );
while
(itr.hasNext( ) ) {
Object vertex = itr.next(
);
if (!g.isVisited(vertex)
)
DFS(g, vertex, myList);
}
return
myList;
}
static protected void DFS
(Graph g, Object n, List verts) {
//post: performs depth-first
search of all vertices reachable
// from vertex
labeled n and add each unvisited vertex
// to list verts
g.visit(n);
Iterator itr = g.neighbors(n);
while
(itr.hasNext( ) ) {
Object neighbor = itr.next(
);
if (!isVisited(neighbor)
)
DFS(g, neighbor, verts);
}
verts.add(n);
}
breadth-first search
public static List breadthFirstSearch (Graph g)
{
//pre: G is non-null
//post: returns list of
vertices in reverse order of when visited
List myList = new
LinkedList( )
Iterator itr = g.iterator(
);
itr.reset( );
while
(itr.hasNext( ) ) {
Object vertex = itr.next(
);
if (!g.isVisited(vertex)
)
BFS(g, vertex, myList);
}
return
myList;
}
static protected void BFS
(Graph g, Object n, List verts) {
//post: performs depth-first
search of all vertices reachable
// from vertex
labeled n and add each unvisited vertex
// to list verts
g.visit(n);
Queue q = new Queue( );
q.enqueue(n);
while
(!q.isEmpty( ) ) {
Object temp = q.dequeue(
);
verts.add(temp);
Iterator
itr = g. neighbors(temp);
while (itr.hasNext(
) ) {
Object neighbor = itr.next( );
if (!isVisited(neighbor) ) {
g.visit(neighbor);
q.enqueue(neighbor);
}
}
}
}
Directed Acyclic
Graph (DAG)
To
determine whether a directed graph is acyclic we
perform a depth-first search with one additional feature. We give each vertex the attribute of
color. An unvisited vertex will be
colored white. When a vertex is first
visited, it will be colored gray and placed on a stack. When all of the unvisited neighbors of a
vertex have been visited, that vertex will be popped off the stack and colored
black. If during our depth-first search,
we encounter a gray vertex, a cycle has been discovered, and the graph we are examining
is NOT acyclic.
If we complete the DFS without encountering a gray vertex, the graph is
found to be acyclic.
If we never encounter a gray or black vertex in our DFS, the graph is a
tree.
Classification of edges
Given the tree depicted below:
In the depth-first search of this graph starting from vertex A, the vertices are discovered and visits are finished in the order shown in the table above. At time 3 (after C is discovered), vertices A, B, C are gray and vertex D is white. The edge from C to A is an edge to a destination vertex that is gray Þ edge is a back edge. At time 5 (after D is discovered), vertex C is black, and since f[C] < d[D], the intervals [d[C],f[C]] and [d[D],f[D]] are disjoint and this edge is a cross edge. At time 7, all of the vertices except A are black, and the dfs(D) from A to D finds that D is black. Therefore d[A] < d[D] < f[D] < f[A] (the interval [d[D],f[D]] is entirely inside [d[A],f[A]]) and the edge from A to D is a forward edge. The labeling of edges is dependent upon the order in which adjacent edges are visited. In the example above, if D preceded B on the adjacency list for vertex A, the edges (A, D) and (D, C) would be tree edges, (C, A) would be a back edge, (A, B) would be a tree edge, and (B, C) and (B, D) would be cross edges.
Topological Sort
A topological sort of a directed acyclic graph (dag) G = (V, E) produces a linear ordering of the vertices such that if there exists an edge (u, v) in E, then vertex u will precede vertex v in the ordering. A topological sort is performed by the following algorithm:
TOPOLOGICAL-SORT (G)
1 call DFS(G) to compute finishing times f [v] for each vertex v.
2
as each vertex is finished, insert it into the
front of a linked list
3
return
the linked list of vertices
Implementation of Graph for Airline
Schedule Problem
/*
* Graph.java
*
* Created on
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
package airlineschedule;
import java.util.*;
import java.io.*;
/**
*
* @author Jim Ten Eyck
*/
public class Graph {
private Map<String,City> cityTable;
private Collection allCities;
/** Creates a new instance of Graph
* @param String: mame of file containing city names
*/
public Graph(String fileName) {
cityTable = new TreeMap<String,City>();
try {
Scanner scan = new Scanner(new FileInputStream(fileName));
while (scan.hasNext()){
String cityName = scan.next();
cityTable.put(cityName,
//cities.add(
}
}
catch (IOException e) {
System.err.println(e);
}
}
/**
* Creates a list of adjacent edges in each City in the graph
* @param String: file name for file of adjacent cities with
* flight information
*/
public void addEdges(String fileName) {
try {
Scanner scan = new Scanner(new FileInputStream(fileName));
while (scan.hasNext()){
String depart = scan.next();
String dest = scan.next();
int flightNum = scan.nextInt();
double cost = scan.nextDouble();
Edge theEdge = new Edge(
flightNum, cost);
City source = cityTable.get(depart);
source.addEdge(theEdge);
}
}
catch (IOException e) {
System.err.println(e);
}
}
/**
* @retrun -- Iterator<City> an iterator on a Collection
* of all City objects in the graph
*/
public Iterator<City> getCities() {
allCities = cityTable.values();
Iterator<City> itr = allCities.iterator();
return itr;
}
/**
* @param String name of a city
* @return City object of that name or null if not present
**/
public City getCity(String name) {
if(cityTable.containsKey(name))
return cityTable.get(name);
else
return null;
}
public boolean contains(String name) {
return cityTable.containsKey(name);
}
public int numCities( ) {
return cityTable.size();
}
}
public class City implements Comparable {
private static int vertexNumber = 0;
private String name;
private EdgeList neighborList;
private boolean marked;
private int cityNumber;
/** Creates a new instance of City with its (empty) list of adjacent edges
* Creates the EdgeList instance variable
* Initializes the city name (String)
* Initializes the cityNumber and increments static vertexNumber
* Initializes the boolean instance variable marked to false
* @param String -- name
*/
public City(String name) {
this.name = name;
this.marked = false;
this.neighborList = new EdgeList();
this.cityNumber = City.vertexNumber++;
}