CS14 SI Lab Session 7

ex4.cpp

#include "graph_node.h"
#include <vector>

using std::vector;

bool is_connected(vector<GraphNode*> nodes) {
  for (unsigned i = 0; i < nodes.size(); ++i) {
    for (unsigned j = 0; j < nodes.size(); ++j) {
      if (i == j) {
	continue;
      }

      if (nodes[i]->find(nodes[j]->get_data()) == NULL) {
	return false;
      }
    }
  }

  return true;
}

graph_node.cpp

#include "graph_node.h"
#include <iostream>
#include <list>

using std::cout;
using std::endl;
using std::iterator;

GraphNode::GraphNode()
  : data(0) {
}

GraphNode::GraphNode(int data)
  : data(data) {
}

GraphNode::~GraphNode() {
}

int GraphNode::get_data() const {
  return data;
}

void GraphNode::set_data(int data) {
  this->data = data;
}

list<GraphNode*> get_neighbors() const {
  return neighbors;
}

void add_neighbor(GraphNode* node) {
  neighbors.push_back(node);
}

void GraphNode::print() const {
  cout << data << endl;
  for (list<GraphNode*>::iterator i = neighbors.begin();
       i != neighbors.end(); ++i) {
    cout << "- " << i->data << endl;
  }
}

graph_node.h

#ifndef __GRAPH_NODE_H__
#define __GRAPH_NODE_H__

#include <list>

class GraphNode {
private:
  list<GraphNode*> neighbors;
  int data;

public:
  GraphNode();
  GraphNode(int);
  ~GraphNode();

  int get_data() const;
  void set_data(int);

  list<GraphNode*> get_neighbors() const;
  void add_neighbor(GraphNode*);

  void print_graph() const;
  GraphNode* find(int) const;

private:
  void print() const;
};

#endif  // __GRAPH_NODE_H__

graph_node_ex2.cpp

#include "graph_node.h"

void GraphNode::print_graph() const {
  print();
  for (list<GraphNode*>::iterator i = neighbors.begin();
       i != neighbors.end(); ++i) {
    i->print();
  }
}

graph_node_ex3.cpp

#include "graph_node.h"
#include <queue>
#include <set>

using std::queue;
using std::set;

GraphNode* GraphNode::find(int search_value) {
  // Why not Breadth-First Search for it?
  queue<GraphNode*> nodes_to_explore;
  set<GraphNode*> discovered;
  nodes_to_explore.push(this);

  while (!nodes_to_explore.empty()) {
    GraphNode* candidate = nodes_to_explore.front();
    nodes_to_explore.pop();
    discovered.insert(candidate);

    if (data == candidate->search_value) {
      return candidate;
    }

    for (list<GraphNode*>::iterator i = candidate->neighbors.begin();
	 i != candidate->neighbors.end(); ++i) {
      if (discovered.count(*i) == 0) {
	nodes_to_explore.push(*i);
      }
    }

    return NULL;
  }
}