CS14 Lab Session 9 Code

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) {}
};

#endif // __EDGE_H__

graph.h

#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <fstream>
#include <iostream>
#include <map>
#include <utility>
#include <cstdlib>
#include "node.h"
#include "edge.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;
  }

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 {
private:
  vector<T> heap;

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);

    for (unsigned pos = heap.size() - 1; pos > 1; pos /= 2) {
      if (heap[pos] < heap[pos/2]) {
	swap(heap[pos], heap[pos/2]);
      } else {
	return;
      }
    }
  }

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

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

    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] < min_child) {
	swap(heap[i], heap[min_child]);
	i = min_child;
      } else {
	return;
      }
    }
  }

  void updateValue(const T& value, );
};

#endif  //  __HEAP_H__

main.cpp

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

using namespace std;

int main() {
  Graph g;

  g.addVertex("A");
  g.addVertex("B");
  g.addVertex("C");
  g.addEdge("A", "B", 4.0);
  g.addEdge("A", "C", 15.5);
  g.addEdge("B", "A", 2.0);

  g.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__