Adjacency-List Class Template

#include <list>
#include <vector>

template <typename DataType>
class Digraph
{
public:
  /*** Functions for digraph operations ***/
  
private:
  /*** Class for data and adjacency lists ***/
  class VertexInfo
  {
  public:
     DataType data;
     list <int> adjacencyList;
  };
  
  /*** Data Members ***/
  vector <VertexInfo> v;
);
 

Figure 16.1 Digraph Class Template

/*--- Digraph.h ------------------------------------------------------------
                Header file for Digraph Class Template
 -------------------------------------------------------------------------*/
#include <list>
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>

template <typename DataType>
class Digraph
{
 public:
  /***** Function Members *****/
  DataType data(int k) const;
  /*-----------------------------------------------------------------------
    Retrieve data value in a given vertex.

    Precondition:  k is the number of a vertex.
    Postcondition: Data value stored in vertex k is returned.
   -----------------------------------------------------------------------*/

  void read(ifstream & inStream);
  /*-----------------------------------------------------------------------
    Input operation.

    Precondition:  ifstream inStream is open.  The lines in the file to
        which it is connected are organized so that the data item in a
        vertex is on one line and on the next line is the number of 
        vertices adjacent to it followed by a list of of these vertices.
    Postcondition: The adjacency list representation of this digraph 
         has been stored in myAdjacencyLists.
   -----------------------------------------------------------------------*/

 void display(ostream & out);
  /*-----------------------------------------------------------------------
    Output operation.

    Precondition:  ostream out is open.
    Postcondition: Each vertexb and its adjacency list have
        been output to out.
   -----------------------------------------------------------------------*/

  void depthFirstSearch(int start);
  /*-----------------------------------------------------------------------
    Depth first search of digraph via depthFirstSearchAux(), starting
    at vertex start.

    Precondition:  start is a vertex.
    Postcondition: All elements of unvisited are initialized to true.
   -----------------------------------------------------------------------*/

  void depthFirstSearchAux(int start, vector<bool> & unvisited);
  /*-----------------------------------------------------------------------
    Recursive depth first search of digraph, starting at vertex start.

    Precondition:  start is a vertex;  unvisited[i] is true if vertex i has
        not yet been visited, and is false otherwise.
    Postcondition: Vector unvisited has been updated.
   -----------------------------------------------------------------------*/

  vector<int> shortestPath(int start, int destination);
  /*-----------------------------------------------------------------------
    Find a shortest path in the digraph from vertex start to vertex
    destination.

    Precondition:  start and destination are vertices.
    Postcondition: A vector of vertices along the shortest path from
        start to destination is returned.
   -----------------------------------------------------------------------*/

 private:
  /***** "Head nodes" of adjacency lists *****/
   class VertexInfo
   {
    public: 
     DataType data;
     list<int> adjacencyList;
   };
   /***** Data member *****/
   vector<VertexInfo> myAdjacencyLists;
}; // end of Digraph class template declaration

//--- Definition of data()
template <typename DataType>
inline DataType Digraph<DataType>::data(int k) const
{ 
  return myAdjacencyLists[k].data;
}

//--- Definition of read()
template <typename DataType>
void Digraph<DataType>::read(ifstream & inStream)
{
  Digraph<DataType>::VertexInfo vi;
  int n,           // number of vertices adjacent to some vertex
      vertex;      // the number of a vertex

  // Put a garbage 0-th value so indices start with 1, as is customary
  myAdjacencyLists.push_back(vi); 

  // Construct adjacency list representation
  for (;;)
  {
    inStream >> vi.data;
    if (inStream.eof()) break;

    inStream >> n;
    list<int> adjList;      // construct empty list
    for (int i = 1; i <= n; i++)
    {
      inStream >> vertex;
      adjList.push_back(vertex);
    }
    vi.adjacencyList = adjList;
    myAdjacencyLists.push_back(vi);
  }
}

//--- Definition of display()
template <typename DataType>
void Digraph<DataType>::display(ostream & out)
{
  out << "Adjacency-List Representation: \n";
  for (int i = 1; i < myAdjacencyLists.size(); i++)
  {
    out << i << ": " <<  myAdjacencyLists[i].data << "--";
    for (list<int>::iterator 
          it = myAdjacencyLists[i].adjacencyList.begin();
          it != myAdjacencyLists[i].adjacencyList.end(); it++)
      out << *it << "  ";
    out << endl;
  }
}
  
//-- Definitions of depthFirstSearch() and depthFirstSearchAux()
template <typename DataType>
void Digraph<DataType>::depthFirstSearch(int start)
{
  vector<bool> unvisited(myAdjacencyLists.size(), true);
  depthFirstSearchAux(start, unvisited);
}


template <typename DataType>
void Digraph<DataType>::depthFirstSearchAux(
                                   int start, vector<bool> & unvisited)
{
  // Add statements here to process myAdjacencyLists[start].data
  cout << myAdjacencyLists[start].data << endl;

  unvisited[start] = false;
  // Traverse its adjacency list, performing depth-first 
  // searches from each unvisited vertex in it.
  for (list<int>::iterator 
         it = myAdjacencyLists[start].adjacencyList.begin();
         it != myAdjacencyLists[start].adjacencyList.end(); it++)
    // check if current vertex has been visited
    if (unvisited[*it])
      // start DFS from new node
      depthFirstSearchAux(*it, unvisited);  
}

//--- Definition of shortestPath()
template<typename DataType>
vector<int> Digraph<DataType>::shortestPath(int start, int destination)
{
  int n = myAdjacencyLists.size(); // number of vertices (#ed from 1)
  vector<int> distLabel(n,-1),     // distance labels for vertices, all
                                   // marked as unvisited (-1)
              predLabel(n);        // predecessor labels for vertices
  // Perform breadth first search from start to find destination,
  // labeling vertices with distances from start as we go.
  distLabel[start] = 0;
  int distance = 0,                // distance from start vertex
      vertex;                      // a vertex
  queue<int> vertexQueue;          // queue of vertices
  vertexQueue.push(start);
  while (distLabel[destination] < 0 && !vertexQueue.empty())
  {
    vertex = vertexQueue.front();
    vertexQueue.pop();
    if (distLabel[vertex] > distance)
      distance++;
    for (list<int>::iterator 
         it = myAdjacencyLists[vertex].adjacencyList.begin();
         it != myAdjacencyLists[vertex].adjacencyList.end(); it++)
      if (distLabel[*it] < 0)
      {
        distLabel[*it] = distance + 1;
        predLabel[*it] = vertex;
        vertexQueue.push(*it);
      }
  }
  distance++;

  // Now reconstruct the shortest path if there is one
  vector<int> path(distance+1);
  if (distLabel[destination] < 0)
    cout << "Destination not reachable from start vertex\n";
  else
  {
    path[distance] = destination;
    for (int k = distance - 1; k >= 0; k--)
      path[k] = predLabel[path[k+1]];
  }

  return path;
}
 

Figure 16.2 Shortest Paths in a Network

/*-------------------------------------------------------------------------
  Program to find the most direct route in an airline network from a given
  start city to a given destination city.  A digraph represented by its
  adjacency-list implementation is used for the network, and the
  information needed to construct it is read from networkFile.
 -------------------------------------------------------------------------*/
 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;

#include "Digraph.h"

int main()
{
  cout << "Enter name of network file: ";
  string networkFile;
  cin >> networkFile;
  ifstream inFile(networkFile.data());
  if (!inFile.is_open())
  {
    cerr << "*** Cannot open " << networkFile << " ***\n";
    exit(-1);
  }

  Digraph<string> d;
  d.read(inFile);
  cout << "The Digraph's ";
  d.display(cout);
  cout << endl;
  
  int start, destination;
  char response;
  do
  {
    cout << "Number of start city? ";
    cin >> start;
    cout << "Number of destination? ";
    cin >> destination;

    vector<int> path = d.shortestPath(start, destination);
    cout << "Shortest path is:\n";
    for (int k = 0; k < path.size() - 1; k++)
    {
      cout << setw(3) << path[k] << ' ' << d.data(path[k]) << endl;
      cout << "      |\n"
              "      v\n";
    }
    cout << setw(3) << destination << ' ' << d.data(destination) << endl;
    cout << "\nMore (Y or N)?";
    cin >> response;
  }
  while (response == 'y' || response == 'Y');
}
 

Figure 16.4 Graph Class Template

/*--- Graph.h -------------------------------------------------------------
                  Header file for Graph Class Template
 -------------------------------------------------------------------------*/

#include <vector>
#include <iostream>

template <typename DataType>
class Graph
{
 public:
  /***** Function Members *****/
  DataType data(int k) const;
  /*-----------------------------------------------------------------------
    Retrieve data value in a given vertex.

    Precondition:  k is the number of a vertex.
    Postcondition: Data value stored in vertex #k is returned.
   -----------------------------------------------------------------------*/

  void read(istream & in, int numVertices, int numEdges);
  /*-----------------------------------------------------------------------
    Input operation.

    Precondition:  istream in is open; numVertices and numEdges are the
        number of vertices and edges in the graph, respectively.
    Postcondition: The vertices and edges of the graph have been read 
        from in and the edge-list representation of this graph stored
        in myEdgeLists.
   -----------------------------------------------------------------------*/

  void depthFirstSearch(int start, vector<bool> & unvisited);
  /*-----------------------------------------------------------------------
    Depth first search of graph via depthFirstSearchAux(), starting
    at vertex start.

    Precondition:  start is a vertex.
    Postcondition: All elements of unvisited are initialized to true.
    -----------------------------------------------------------------------*/

  void depthFirstSearchAux(int start, vector<bool> & unvisited);
  /*-----------------------------------------------------------------------
    Recursive depth first search of graph, starting at vertex start.

    Precondition:  start is a vertex; unvisited[i] is true if vertex i has
        not yet been visited,  and is false otherwise.
    Postcondition: Vector unvisited has been updated.
   -----------------------------------------------------------------------*/

  bool isConnected();
  /*-----------------------------------------------------------------------
    Check if graph is connected.

    Precondition:  None.
    Postcondition: True is returned if graph is connected, false if not.
   -----------------------------------------------------------------------*/

 private:
  /***** Edge Nodes *****/
   class EdgeNode
   {
    public:
     int vertex[3];         // Use 1 and 2 for indices
     EdgeNode * link[3];    //   as is customary
   };
   typedef EdgeNode * EdgePointer;

  /***** "Head nodes" of edge lists *****/
  class VertexInfo
  { 
   public:
    DataType data;         // data value in vertex
    EdgePointer first;     // pointer to first edge node
  };

  /***** Data Members *****/
  vector<VertexInfo> myEdgeLists;
}; // end of Graph class template declaration

//--- Definition of data()
template <typename DataType>
inline DataType Graph<DataType>::data(int k) const
{
  return myEdgeLists[k].data;
}

//--- Definition of read()
template <typename DataType>
void Graph<DataType>::read(istream & in, int numVertices, int numEdges)
{
  Graph<DataType>::VertexInfo vi;

  // Put a garbage 0-th value so indices start with 1, as is customary
  myEdgeLists.push_back(vi); 

  // Create "head nodes"
  cout << "Enter label of vertex:\n";
  for (int i = 1; i <= numVertices; i++)
  {
    cout << "  " << i << ": ";
    in >> vi.data;
    vi.first = 0;
    myEdgeLists.push_back(vi);
  }

  int endpoint;       // endpoint of an edge   
  // Create edge lists
  cout << "Enter endpoints of edge\n";
  for (int i = 1; i <= numEdges; i++)
  {
    cout << "  " << i << ": ";
    EdgePointer newPtr = new EdgeNode;
    for (int j = 1; j <= 2; j++)
    {
      in >> endpoint;
      // insert new edge node at beginning
      // of edge list for endpoint
      newPtr->vertex[j] = endpoint;
      newPtr->link[j] = myEdgeLists[endpoint].first;
      myEdgeLists[endpoint].first = newPtr;
    }
  }
}

/*--- Utility function to check if all nodes have been visited.
   Precondition:  unvisited tells which nodes have not been 
         visited
   Postcondition: true is returned if all vertices, false if not.
  ---------------------------------------------------------------*/
bool anyLeft(const vector<bool> & unvisited)
{
  for (int i = 1; i < unvisited.size(); i++)
    if (unvisited[i])
      return true;
  return false;
}

//-- Definition of depthFirstSearch()
template <typename DataType>
void Graph<DataType>::depthFirstSearch(int start, vector<bool> & unvisited)
{
  // --- Insert statements here to process visited node
  // Mark start visited, and initialize pointer 
  // to its first edge node to begin DFS.
  unvisited[start] = false; 

  Graph<DataType>::EdgePointer ptr = myEdgeLists[start].first;
  while(anyLeft(unvisited) && ptr != 0)
  {
    // Determine which end of edge is start
    int startEnd = 1,   
        otherEnd = 2;
    if (ptr->vertex[1] != start)
    { startEnd = 2; otherEnd = 1;}

    // Start new (recursive) DFS from vertex at other end
    // if it hasn't already been visited
    int newStart = ptr->vertex[otherEnd];
    if (unvisited[newStart])
      depthFirstSearch(newStart, unvisited);
    // Move to next edge node
    ptr = ptr->link[startEnd];
  }
}

//-- Definition of isConnected()
template <typename DataType>
bool Graph<DataType>::isConnected()
{
  vector<bool> unvisited(myEdgeLists.size(), true);
  depthFirstSearch(1, unvisited);
  return !anyLeft(unvisited);
}
 

Figure 16.5 Graph Connectedness

/*-------------------------------------------------------------------------
  Program to determine if a graph is connected. If the graph is not
  connected, a list of unreachable vertices from the start vertex is
  provided to the user.
  ------------------------------------------------------------------------*/


#include <iostream>
using namespace std;

#include "Graph.h"

int main()
{
  int numVertices,         // number of vertices in the graph
      numEdges;            //   "     "  edges   "   "    "

  cout << "Enter number of vertices and number of edges in graph: ";
  cin >> numVertices >> numEdges;
  Graph<char> g;
  g.read(cin, numVertices, numEdges);

  cout << "Graph is ";
  if (g.isConnected())
    cout << "connected.\n";
  else
  {
    cout << "not connected.\n"
            "Would you like to see which vertices are not\n"
            "reachable from vertex 1 (" 
         << g.data(1) << ") -- (Y or N)? ";
    char response;
    cin >> response;
    if (response == 'y' || response == 'Y')
    {
      cout << "They are the following: \n";
      vector<bool> unreachable(numVertices + 1, true);
      g.depthFirstSearch(1, unreachable);
      for (int i = 1; i < unreachable.size(); i++)
        if (unreachable[i])
          cout << "Vertex " << i << " (" << g.data(i) << ")\n";
    }
    cout << endl;
  }
}