CS14 SI Lab Session 9 Solutions

distance_heap.h

#ifndef __DISTANCE_HEAP_H__
#define __DISTANCE_HEAP_H__

#include "heap.h"
#include "node.h"
#include <utility>

using std::pair;

struct DistancePair {
  Node* n;
  double distance;

  bool operator<(const DistancePair& rhs) const {
    return distance < rhs.distance;
  }

  bool operator>(const DistancePair& rhs) const {
    return distance > rhs.distance;
  }

  DistancePair()
    : n(NULL) {
  }

  DistancePair(double distance, Node* n = NULL)
    : n(n), distance(distance) {
  }
};

class DistanceHeap: public Heap<DistancePair> {
 public:
  void push(Node* n, double distance) {
    DistancePair dp(distance, n);
    Heap<DistancePair>::push(dp);
  }

  void updateValue(Node* n, double value) {
    for (vector<DistancePair>::iterator i = heap.begin() + 1;
	 i != heap.end(); ++i) {
      if (i->n->label == n->label) {
	i->distance = value;
	percolate_up(std::distance(heap.begin(), i));
	return;
      }
    }
  }
};

#endif  // __DISTANCE_HEAP_H__

edge.h

#ifndef __EDGE_H__
#define __EDGE_H__

#include "node.h"

struct Edge {
  Node* from;
  Node* to;
  double weight;

  Edge(double weight = 1.0): from(NULL), to(NULL), weight(weight) {}
  Edge(Node* from, Node* to): from(from), to(to) {}
  Edge(Node* from, Node* to, double weight = 1.0): 
    from(from), to(to), weight(weight) {}

  bool operator<(const Edge& e) {
    return weight < e.weight;
  }

  bool operator>(const Edge& e) {
    return weight > e.weight;
  }
};

#endif // __EDGE_H__

errors

In file included from distance_heap.h:4:0,
                 from graph.h:12,
                 from main.cpp:2:
heap.h: In instantiation of ‘Heap<T>::Heap() [with T = DistancePair]’:
distance_heap.h:23:7:   required from here
heap.h:23:28: error: no matching function for call to ‘DistancePair::DistancePair()’
heap.h:23:28: note: candidates are:
In file included from graph.h:12:0,
                 from main.cpp:2:
distance_heap.h:18:3: note: DistancePair::DistancePair(double, Node*)
distance_heap.h:18:3: note:   candidate expects 2 arguments, 0 provided
distance_heap.h:10:8: note: DistancePair::DistancePair(const DistancePair&)
distance_heap.h:10:8: note:   candidate expects 1 argument, 0 provided
In file included from distance_heap.h:4:0,
                 from graph.h:12,
                 from main.cpp:2:
heap.h: In instantiation of ‘T Heap<T>::pop() [with T = DistancePair]’:
graph.h:143:23:   required from here
heap.h:36:5: error: ‘class std::vector<DistancePair, std::allocator<DistancePair> >’ has no member named ‘pop’
heap.h:45:2: error: return-statement with no value, in function returning ‘DistancePair’ [-fpermissive]

graph.h

#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdlib>
#include "node.h"
#include "edge.h"
#include "distance_heap.h"

using namespace std;

typedef pair<Node*, Node*> NodePair;

// This is called a comparison class and it can be passed as a template
// argument to most STL types so that it can compare they Key values.
class CompareNodePairs {
public:
  bool operator()(const NodePair& p1, const NodePair& p2) const {
    string concat_p1 = p1.first->label + p1.second->label;
    string concat_p2 = p2.first->label + p2.second->label;
    return concat_p1 < concat_p2;
  }
};

class Graph {
private:
  map<string, Node*> vertices;
  map<NodePair, Edge, CompareNodePairs> edges;

public:
  Graph() {}
  Graph(const string& input_file) {
    construct_from_file(input_file);
  }
  ~Graph() {
    for (map<string, Node*>::iterator i = vertices.begin();
	 i != vertices.end(); ++i) {
      delete i->second;
      i->second = NULL;
    }
  }

  void print() const {
    for (map<string, Node*>::const_iterator i = vertices.begin();
	 i != vertices.end(); ++i) {
      Node* v = i->second;
      cout << "Node " << v->label << " has " << v->neighbors.size() <<
	" neighbors" << endl;

      for (list<Node*>::iterator j = v->neighbors.begin();
	   j != v->neighbors.end(); ++j) {
	Edge e = findEdge(v->label, (*j)->label);
	cout << "\twith Node " << (*j)->label << " and edge weight "
	     << e.weight << endl;
      }
    }
  }

  Node* findNode(const string& label) const {
    if (vertices.count(label) == 0) {
      return NULL;
    }

    return vertices.find(label)->second;
  }

  Edge findEdge(const string& from_label, const string& to_label) const {
    Node* from = findNode(from_label);
    Node* to = findNode(to_label);

    // One of the node's doesn't exist.
    if (!(from && to)) {
      cout << "Can't find edge between two nodes if one of them doesn't exist"
	   << endl;
      exit(1);
    }

    NodePair np = make_pair(from, to);

    // Edge doesn't exist.
    if (edges.count(np) == 0) {
      cout << "Could not find edge between the two nodes" << endl;
      exit(1);
    }

    return edges.find(np)->second;
  }

  void addVertex(const string& label) {
    if (vertices.count(label) > 0) {
      // Node already exists
      return;
    }

    Node* vertex = new Node(label);
    vertices[label] = vertex;
  }

  void addEdge(const string& from_label, const string& to_label,
	       double weight) {
    Node* from = findNode(from_label);
    Node* to = findNode(to_label);

    if (!(from && to)) {
      cout << "Cannot make edge between two nodes if one doesn't exist."
	   << endl;
      exit(1);
    }

    from->neighbors.push_back(to);
    Edge e(from, to, weight);
    NodePair np = make_pair(from, to);
    edges[np] = e;
  }

  double dijkstras(const string& from_label, const string& to_label) {
    Node* from = findNode(from_label);
    Node* to = findNode(to_label);
    if (!(from && to)) {
      cout << "Cannot find shortest path between two nodes if "
	"one doesn't exist." << endl;
      exit(1);
    }

    map<string, double> distances;
    DistanceHeap q;

    // Add all elements to the queue.
    for (map<string, Node*>::iterator i = vertices.begin();
	 i != vertices.end(); ++i) {
      distances[i->first] = INFINITY;
      q.push(i->second, INFINITY);
    }

    distances[from_label] = 0;
    q.updateValue(from, 0);

    while (!q.empty()) {
      Node* v = q.pop().n;
      if (distances[v->label] == INFINITY) {
	break;
      }

      for (list<Node*>::iterator u = v->neighbors.begin();
	   u != v->neighbors.end(); ++u) {	
	double weight = findEdge(v->label, (*u)->label).weight;
	double altDistance = distances[v->label] + weight;
	if (altDistance < distances[(*u)->label]) {
	  distances[(*u)->label] = altDistance;
	  q.updateValue((*u), altDistance);
	  (*u)->previous = v;
	}
      }
    }

    return distances[to_label];
  }

  double kruskals() {
    double cost = 0.0;
    
    Heap<Edge> edge_heap;
    set<Node*> discovered;

    for (map<NodePair, Edge>::iterator i = edges.begin();
	 i != edges.end(); ++i) {
      edge_heap.push(i->second);
    }

    while (!edge_heap.empty()) {
      Edge e = edge_heap.pop();

      // If both the start and end point have already been discovered,
      // it will cause a cycle.
      if (discovered.count(e.from) && discovered.count(e.to)) {
	continue;
      }

      cost += e.weight;
      discovered.insert(e.from);
      discovered.insert(e.to);
    }

    return cost;
  }

private:
  void construct_from_file(const string& filename) {
    fstream f(filename.c_str());
    int vertex_count = 0, edge_count = 0;

    f >> vertex_count >> edge_count;

    string vertex_label;
    for (int i = 0; i < vertex_count; ++i) {
      f >> vertex_label;
      addVertex(vertex_label);
    }

    string vertex1, vertex2;
    double edge_weight;

    for (int i = 0; i < edge_count; ++i) {
      f >> vertex1 >> vertex2 >> edge_weight;
      addEdge(vertex1, vertex2, edge_weight);
    }
  }
};

#endif  // __GRAPH_H__

heap.h

#ifndef __HEAP_H__
#define __HEAP_H__

#include <vector>
using namespace std;

template<typename T>
class Heap {
protected:
  vector<T> heap;
  void percolate_up(unsigned pos) {
    for (; pos > 1; pos /= 2) {
      if (heap[pos] < heap[pos/2]) {
	swap(heap[pos], heap[pos/2]);
      } else {
	return;
      }
    }
  }

public:
  // We let the first element in the vector be taken
  Heap(): heap(vector<T>(1)) {}
  ~Heap() {}

  void push(const T& value) {
    heap.push_back(value);

    percolate_up(heap.size() - 1);
  }

  T pop() {
    T val = heap[1];

    heap[1] = heap[heap.size() - 1];
    heap.pop_back();

    for (unsigned i = 1; i < heap.size() / 2;) {
      unsigned min_child = (heap[2*i] < heap[2*i + 1]) ? 2*i : 2*i + 1;

      if (heap[i] > heap[min_child]) {
	swap(heap[i], heap[min_child]);
	i = min_child;
      } else {
	break;
      }
    }

    return val;
  }

  bool empty() {
    return heap.size() <= 1;
  }
};

#endif  //  __HEAP_H__

main.cpp

#include <iostream>
#include "graph.h"
#include <cassert>
#include <iostream>

using namespace std;

int main() {
  Graph g;

  g.addVertex("A");
  g.addVertex("B");
  g.addVertex("C");
  g.addVertex("D");
  g.addVertex("E");
  g.addVertex("F");

  g.addEdge("A", "B", 7);
  g.addEdge("A", "C", 9);
  g.addEdge("A", "D", 14);
  g.addEdge("B", "C", 10);
  g.addEdge("B", "F", 15);
  g.addEdge("C", "D", 2);
  g.addEdge("C", "F", 11);
  g.addEdge("D", "E", 9);
  g.addEdge("E", "F", 6);

  assert(g.dijkstras("A", "E") == 20);
  g.print();

  Graph k;
  k.addVertex("A");
  k.addVertex("B");
  k.addVertex("C");
  
  k.addEdge("A", "B", 5);
  k.addEdge("A", "C", 9);
  k.addEdge("B", "C", 5);

  cout << endl;

  assert(k.kruskals() == 10);
  k.print();

  return 0;
}

node.h

#ifndef __NODE_H__
#define __NODE_H__

#include <string>
#include <list>
using namespace std;

struct Node {
  string label;
  list<Node*> neighbors;
  Node* previous;

  Node(): previous(NULL){}
  Node(const string& label): label(label), previous(NULL) {}
};

#endif  // __NODE_H__