8. Graphs and Path

Objective: In this lecture, we'll examine the graph and show how to solve the shortest path problems. Topics include:

In this lecture unit, we show:

formal definition of a graph and its components,
the data structure used to represent a graph, and
algorithms for solving two variants of the shortest-path problem, with complete C++ implementations.

8.1 Definitions

A graph consists of a set of vertices and a set of edges that connect the vertices. Notation: G = (V,E).
Each edge is a pair (v,w) where v, w in V. If the pair is ordered, the graph is called a direcetd graph (or digraph). (In this chapter, all graphs are directed.)
Sometimes an edge has a third component, called the edge cost (or weight) that measures the cost of traveling the edge.
Vertex v is adjacent to vertex w if there is an edge from v to w.
A path in a graph is a sequence of vertcies connected by edges. The (unweighted) path length is the number of edges on that path. The weighted path length is the sum of the costs of edges on the path.
A simple path is a path in which all vertices are distinct, except that the first and last vertices can be the same.
A cycle in a directed graph is a path that begins and ends at the same vertex and contains at least one edge.
A directed acyclic graph (DAG) is a directed graph containing no cycles.
A graph is dense if the number of edges is large (gradratic with respect to the number of vertices, i.e. |E| = theta(|V|^2)). Typically graphs are not dense. Instead, they are sparse.

8.2 Representation

Adjacency matrix
Let G = (V,E) be a [di]graph with n vertices, n <= 1. Let the vertices be denoted by 0, 1, ..., n-1. The adjacency matrix A of G is an n * n array such that A[i][j] is 1 if edge (i,j) exists in G and 0 otherwise.
The adjacency matrix of an undirected graph is symmetric.
If the [di]graph is weighted with the cost function cost, simply store the cost cost(i,j) in A[i][j]. If an edge does not exist, 0, or INFINITY can be stored, depending on application.
Advantages:
- Very simple
- For unweighted graphs, can use only one bit per entry.
Disadvantages:
- Space requirement is proportional to n^2.
- Any algorithm on G takes time at least proportional to n^2.
Adjacency lists
An array Adj of n linked lists, one for each vertex, such that Adj[i] is the list of all vertices adjacent from i.
Lemma 1 Let G be a digraph. Then
```
  n-1
  SUM |Adj[i]| = |E|.
  i=0
```
Lemma 2 Let G be a graph. Then
```
  n-1
  SUM |Adj[i]| = 2|E|.
  i=0
```
Theorem 7 The space requirement of the adjacency-list representation is O(|V| + |E|).
Advantages:
- More space efficient for sparse [di]graphs.
- More time efficient for most graph algorithms for sparse [di]graphs.
- No special symbol for edges that don't exist.
Disadvantages:
- More complicated structure.
- No quick ways to determine if (i,j) in E.
- Some applications may require storing also the inverse adjacency lists.
Example: For the graph
```
             1       2       3

         0       4               5

             6       7       8
```
The adjacency matrix is
```
   0  1  0  0  0  0  1  0  0
   1  0  1  0  0  0  1  0  0
   0  1  0  1  1  0  0  1  1
   0  0  1  0  0  1  0  0  1
   0  0  1  0  0  0  1  1  0
   0  0  0  1  0  0  0  0  1
   1  1  0  0  1  0  0  1  0
   0  0  1  0  1  0  1  0  1
   0  0  1  1  0  1  0  1  0
```
The adjacency (and inverse adjacency) lists are given by:
```
   Adj[0] : 1  6
   Adj[1] : 0  2  6
   Adj[2] : 1  3  4   7  8
   Adj[3] : 2  5  8
   Adj[4] : 2  6  7
   Adj[5] : 3  8
   Adj[6] : 0  1  4  7
   Adj[7] : 2  4  6  8
   Adj[8] : 2  3  5  7
```

8.3 The Graph Class Interface (I)

The first major data structure is a map that for any vertex name, gives a pointer to the Vertex object that represents it.

The second major data structure is the Vertex object that stores information about all the vertices.

name: Name of the vertex
adj: The list of adjacent vertices
dist: Length of the shortest path from the starting vertex to this vertex
prev: The previous vertex on the shortest path to this vertex

struct Vertex;

// Basic item stored in adjancy list.
struct Edge
{
                  // 1st vertex in edge is implicit
   Vertex *dest;  // 2nd vertex in edge
   double  cost;  // Edge cost

   Edge(Vertex *d = 0, double c = 0.0)
      : dest(d), cost(c) {}
};

struct Vertex
{
   string         name;    // vertex name
   vector<Edge>   adj;     // Adj. vertices (and costs)
   double         dist;    // cost
   Vertex        *prev;    // Previous vertex on  path
   int            scratch; // Used in algorithm

   Vertex(const string& nm): name(nm) { reset(); }

   void reset()
   {
      dist = INFINITY;
      prev = NULL;
      scratch = 0;
   }
};

8.4 The Graph Class Interface (II)

class Graph
{
public:
   Graph() {}
   ~Graph();

   void addEdge(const string &sourceName,
                const string &destName, double cost);
   void printPath(const string &dsetName) const;
   void unweighted(const string &startName);
   void dijkstra(const string &startName);
   void acyclic(const string &startName);

private:
   Vextex *getVertex(const string &vertexName);
   void printPath(const Vertex &dest) const;
   void clearAll();

   typedef map<string, Vertex *, less<string>> vmap;

    // Copy semantics are disabled.
   Graph(const Graph &rhs) {}
   const Graph &operator=(const Graph &rhs)
   {
      return *this;
   }

   vmap vertexMap;
};

8.5 Implementation

Graph::~Graph()
{
   vmap::iterator itr;
   for (itr = vertexMap.begin(), itr != vertexMap.end(); ++itr)
   {
      delete (*itr).second;
   }
}

//
// If vertexName is not present, add it to vertexMap.
// In either case, return a pointer to the Vertex.
//
Vertex *Graph::getVertex(const string &vertexName)
{
   vmap::iterator itr = vertexMap.find(vertexName);
   if (itr == vertexMap.end())
   {
      Vertex *newv = new Vertex(vertexName);
      vertexMap[vertexName] = newv;
      return newv;
   }

   return (*itr).second;
}

//
// Add a new edge to the graph
//
void Graph::addEdge(const string &sourceName, const string &destName,
                    double cost)
{
   Vertex *v = getVertex(sourceName);
   Vertex *w = getVertex(destName);
   v->adj.push_back(Edge(w, cost));
}

//
// Initialize the vertex output info prior to
// running any shortest path algorithm.
//
void Graph::clearAll()
{
   vmap::iterator itr;
   for (itr = vertexMap.begin(); itr != vertexMap.end(); ++itr)
   {
      (*itr).second->reset();
   }
}

//
// Recursive routine to print shortest path to
// dest after running shortest path algorithm.
// The path is known to exist.
//
void Graph::printPath(const Vertex &dest) const
{
   if (dest.prev != NULL)
   {
      printPath(*dest.prev);
      cout << " To ";
   }

   cout << dest.name;
}

//
// Driver routine to handle unreachables and print
// total cost.  It calls recursive routine to print
// shortest path to destName after a shortest path
// algorithm has run.
//
void Graph::printPath(const string &destName) const
{
   vmap::const_iterator itr = vertexMap.find(destName);
   if (itr == vertexMap.end())
   {
      throw GraphException("Dest. vertex not found");
   }

   const Vertex &w = *(*itr).second;

   if (w.dist == INFINITY)
   {
      cout << destName << " is unreachable";
   }
   else
   {
      cout << "(cost is: " << w.dist << ") ";
      printPath(w);
   }

   cout << endl;
}

8.6 A Simple Program

//
// A simple main that reads the file given by arg[1] and
// then calls processRequest to compute shortest paths.
// Skip error checking in order to concentrate on the basics.
//
int main(int argc, char argv[])
{
   if (argc != 2)
   {
      cerr << "Usage: " << argv[0] << " graphfile"
           << endl;
      return 1;
   }

   ifstream inFile(argv[1]);

   if (!inFile)
   {
      cerr << "Cannot open " << argv[0] << endl;
      return 1;
   }

   cout << "Reading file... " << endl;
   string oneLine;

   // Read the edges; add them to g.
   Graph g;
   while (!getline(inFile, oneLine).eof())
   {
      string source, dest;
      double cost;
      istringstream st(oneLine);

      st >> source >> dest >> cost;

      if (st.fail())
      {
         cerr << "Bad line; " << oneLine << endl;
      }
      else
      {
         g.addEdge(source, dest, cost);
      }
   }

   cout << "File read" << endl <, endl;

   while (processRequest(cin, g))
     ;

  return 0;
}

//
// Porcess a request; return false if end of file.
//
bool processRequest(istream &in, Graph &g)
{
   string startName, destName;

   cout << "Enter start node: ";

   if (!(in >> startName))
   {
      return false;
   }

   cout << "Enter destination node: ";

   if (!(in >> destName))
   {
      return false;
   }

   try
   {
      g.unweighted(startName);
      g.printPath(destName);
   }
   catch
   {
      cerr << e.toString() << endl;
   }

   return true;
}

8.7 Single-Source Shortest Path (Unweighed)

Problem statement: Find the shortest path (measured by number of edges) from a designated vertex S to every vertex.
A breadth-first search processes vertices in layers, from the closest to the most distant from the source node. All vertices in the same layer have the same length from the source vertex. The length truns out to be the length of their shortest paths from the siourceource node.

Implementation:

//
// Single-Source unweighted shortest-path alg.
//
void Graph::unweighted(const string &startName)
{
   vmap::iterator itr = vertexMap.find(startName);
   if (itr == vertexMap.end())
   {
      throw GraphException(startName + " is not a vertex");
   }

   clearAll();
   Vertex *start = (*itr).second;
   start->dist = 0;
   Queue<Vertex *> q;
   q.enqueue(start);

   while (!q.empty())
   {
      Vertex *v = q.dequeue()

      for (int i = 0; i < v->adj.size(); i++)
      {
         Edge e = v->adj[i];
         Vertex *w = e.dest;

         if (w->dist == INFINITY)
         {
            w->dist = v.dist + 1;
            w->prev = v;
            q.enqueue(w);
         }
      }
   }
}

8.8 Single-Source Shortest Path (Positive-Weighed)

Problem statement: Find the shortest path (measured by total cost) from a designated vertex S to every vertex. All edge costs are nonnegative.
Dijkstra's Algorithm: Let S be the set of vertices to which shortest paths from the starting vertex have been constructed, and let d[v] be the length of a shortest path to v passing through only those vertices in S. The Dijkstra's Algorithm works as follows: At each stage, add an a not in S to S that minimizes d[a].
- If the next shortest path is to vertex u, then all intermediate vertices on the path must be in S.
- The next u to add to S must be the one that minimizes d[u] among all vertices not in S.
- Afteradding u to S, for each x not in S, if d[u] + cost(u,x) < d[x], then d[x] should be updated to d[u] + cost(u,x).

Implementation:

//
// structure stored in priority queue for
// Dijkstra's algorithm
//
struct Path
{
   Vertex *dest;  // w
   double  cost;  // d(w)

   Path(Vertex *d = 0, double c = 0.0) : dest(d), cost(c) {}

   bool operator>(const Path &rhs) const { return cost > rhs.cost; }

   bool operator<(const Path &rhs) const { return cost < rhs.cost; }
};

void Graph::dijkstra(const string &startName)
{
   priority_queue<Path, vector<Path>, greater<Path>> pq;
   Path vrec;  // Stores the result of a deleteMin

   vmap::iterator itr = vertexMap.find(startName);

   if (itr == vertexMap.end())
   {
      throw GraphException(startName + " is not a vertex");
   }

   clearAll();
   vertex *start = (*itr).second;
   start->dist = 0;
   pq.push(Path(start, 0));

   int nodesSeen = 0;
   for ( ; nodesSeen < vertexmap.size(); nodesSeen++)
   {
      do
      {
         // find an unvisited vertex
         if (pq.empty())
         {
            return;
         }
         vrec = pq.top();
         pq.pop();
      } while (vrec.dest->scratch != 0);

      Vertex *v = vrec.dest;
      v->scratch = 1;

      for (int i = 0; i < v->adj.size(); i++)
      {
         Edge e = v->adj[i];
         Vertex *w = e.dest;
         double cvw = e.cost;

         if (cvw < 0)
         {
            throw GraphException("Negative edge seen");
         }

         if (w->dist > v->dist + cvw)
         {
            w->dist = v->dist + cvw;
            w->prev = v;
            pq.insert(Path(w, w->dist));
         }
      }
   }
}

The running time of Dijkstra's algorithm is O(|E| lg |V|).