CS14 SI Lab Session 8 Solutions

main.cpp

#include "undirected_graph.h"
#include <string>
#include <cassert>

using std::string;

int main() {
  UndirectedGraph<int> g;
  g.addVertex(1);
  g.addVertex(2);
  g.addVertex(3);
  g.addVertex(4);
  g.addVertex(5);
  g.addVertex(6);
  g.addVertex(7);

  g.addEdge(1, 2, 7);
  g.addEdge(1, 3, 9);
  g.addEdge(1, 6, 14);
  g.addEdge(2, 4, 15);
  g.addEdge(2, 3, 10);
  g.addEdge(3, 4, 11);
  g.addEdge(3, 6, 2);
  g.addEdge(4, 5, 6);
  g.addEdge(5, 6, 9);

  int start = 1, end = 5;
  assert(g.shortest_path(start, end) == 20);
  g.print_shortest_path(start, end);

  assert(g.num_connected_components() == 2);

  return 0;
}

undirected_graph.h

#ifndef __UNDIRECTED_GRAPH_H__
#define __UNDIRECTED_GRAPH_H__

#include <map>
#include <vector>

using std::map;
using std::vector;

template<typename NodeID>
class UndirectedGraph {
private:
  struct GraphNode {
    NodeID id;
    GraphNode* previous;

    GraphNode(const NodeID& id);
  };

  map<NodeID, GraphNode*> vertices;

  // An adjacency matrix, indexed by NodeID
  map<NodeID, map<NodeID, int> > edges;

public:
  ~UndirectedGraph();

  void addVertex(const NodeID& id);
  void addEdge(const NodeID& to, const NodeID& from, int cost);

  int shortest_path(const NodeID& start, const NodeID& dest);
  void print_shortest_path(const NodeID& start, const NodeID& dest);
  int num_connected_components() const;
};

#include "undirected_graph.incl"

#endif  // __UNDIRECTED_GRAPH_H__

undirected_graph.incl

#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::queue;
using std::set;

template<typename NodeID>
UndirectedGraph<NodeID>::GraphNode::GraphNode(const NodeID& id)
  : id(id), previous(NULL) {
}

template<typename NodeID>
UndirectedGraph<NodeID>::~UndirectedGraph() {
  // Need the typename here since we won't know what NodeID is until compile time.
  for (typename map<NodeID, GraphNode*>::iterator i = vertices.begin();
       i != vertices.end(); ++i) {
    delete i->second;
    i->second = NULL;
  }
}

template<typename NodeID>
void UndirectedGraph<NodeID>::addVertex(const NodeID& id) {
  // Only insert Vertex if it doesn't exist.
  if (vertices.count(id) != 0) {
    return;
  }

  // Insert Vertex into vertices map.
  GraphNode* v = new GraphNode(id);
  vertices[id] = v;

  // Also need to add new place in edges.
  edges[id] = map<NodeID, int>();
}

template<typename NodeID>
void UndirectedGraph<NodeID>::addEdge(const NodeID& to, const NodeID& from,
				      int cost) {
  // Can't create an edge between two non-existent vertices.
  if (!(vertices.count(to) && vertices.count(from))) {
    return;
  }

  edges[to][from] = cost;
  edges[from][to] = cost;
}

// Exercise 2
// Dijkstra's of course.
template<typename NodeID>
int UndirectedGraph<NodeID>::shortest_path(const NodeID& start,
					   const NodeID& dest) {
  // Can't find the shortest path between two non-existent vertices.
  if (!(vertices.count(start) && vertices.count(dest))) {
    exit(1);
  }

  map<NodeID, int> distances;
  set<NodeID> not_processed;
  for (typename map<NodeID, GraphNode*>::iterator i = vertices.begin();
       i != vertices.end(); ++i) {
    distances[i->first] = INT_MAX;
    not_processed.insert(i->first);
  }

  distances[start] = 0;

  for (typename set<NodeID>::iterator v = not_processed.begin();
       v != not_processed.end();) {
    
    // Need to find the next node to process
    NodeID to_be_processed = *not_processed.begin();
    int shortest_distance = distances[to_be_processed];
    for (typename set<NodeID>::iterator candidate = not_processed.begin();
	 candidate != not_processed.end(); ++candidate) {
      int candidate_distance = distances[*candidate];
      if (candidate_distance < shortest_distance) {
	shortest_distance = candidate_distance;
	to_be_processed = *candidate;
      }
    }

    // Remove the node from the not_processed set and moves up the iterator.
    if (v == not_processed.find(to_be_processed)) {
      not_processed.erase(v++);
    } else {
      not_processed.erase(to_be_processed);
    }

    // Don't need to process infinity distance smallest vertices.
    if (shortest_distance == INT_MAX) {
      break;
    }

    map<NodeID, int> neighbors = edges[to_be_processed];
    for (typename map<NodeID, int>::iterator neighbor = neighbors.begin();
	 neighbor != neighbors.end(); ++neighbor) {
      if (shortest_distance + neighbor->second < distances[neighbor->first]) {
	distances[neighbor->first] = shortest_distance + neighbor->second;
	vertices[neighbor->first]->previous = vertices[to_be_processed];
      }
    }
  }

  return distances[dest];
}

template<typename NodeID>
void UndirectedGraph<NodeID>::print_shortest_path(const NodeID& start,
						const NodeID& dest) {
  shortest_path(start, dest);
  vector<NodeID> path;
  for(GraphNode* i = vertices[dest]; i; i = i->previous) {
    path.push_back(i->id);
  }

  for (typename vector<NodeID>::iterator i = path.end() - 1; i != path.begin(); --i) {
    cout << *i << " -> ";
  }

  cout << dest << endl;
}

template<typename NodeID>
int UndirectedGraph<NodeID>::num_connected_components() const {
  // Use breath-first search from unseen nodes to find the number of
  // components.
  set<NodeID> seen;
  queue<NodeID> bfs_queue;

  int component_count = 0;
  for (typename map<NodeID, GraphNode*>::const_iterator i = vertices.begin();
       i != vertices.end(); ++i) {
    if (seen.count(i->first) != 0) {
      continue;
    }

    ++component_count;
    bfs_queue.push(i->first);
    while (!bfs_queue.empty()) {
      NodeID current = bfs_queue.front();
      bfs_queue.pop();
      seen.insert(current);
      map<NodeID, int> neighbors = edges.find(current)->second;
      for (typename map<NodeID, int>::iterator n = neighbors.begin();
	   n != neighbors.end(); ++n) {
	if (seen.count(n->first) == 0) {
	  bfs_queue.push(n->first);
	}
      }
    }
  }

  return component_count;
}