I am restudying graph theories and I want to write a Graph
class that would allow me to implement those methods. Is there a better way of implementing a general Graph
class?
Main function:
int main() {
using namespace GraphUtils;
Graph<char> graph;
Node<char> a('a');
Node<char> b('b');
Node<char> c('c');
Node<char> d('d');
Node<char> e('e');
Node<char> f('f');
graph.AddNode(a).AddNode(b).AddNode(c).AddNode(d).AddNode(e).AddNode(f);
a.AddChild(f).AddChild(d);
b.AddChild(c).AddChild(a);
c.AddChild(d);
e.AddChild(f);
f.AddChild(b);
graph.Print();
if( !PathExist(graph, a, b)) {
cout << "ERR: a -> b exists" << endl;
}
if( !PathExist(graph, a, c)) {
cout << "ERR: a -> c exists" << endl;
}
if( PathExist(graph, a, e)) {
cout << "ERR: a -> c doesn't exist" << endl;
}
if( PathExist(graph, c, e)) {
cout << "ERR: c -> e doesn't exist" << endl;
}
if( !PathExist(graph, e, c)) {
cout << "ERR: e -> c exists" << endl;
}
}
Class implementation, which is heavily pointer-oriented:
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using std::map;
using std::vector;
using std::cout;
using std::endl;
using std::queue;
namespace GraphUtils {
template <typename T>
struct Node {
T data;
vector<Node*> children;
Node() {}
Node(T input): data(input) {}
Node& AddChild(Node& input) {
children.push_back(&input);
return *this;
}
};
template <typename T>
bool operator<(Node<T>& lhs, Node<T>& rhs) {
return (lhs.data < rhs.data);
}
template <typename T>
bool operator==(Node<T>& lhs, Node<T>& rhs) {
return !(lhs.data < rhs.data || lhs.data > rhs.data);
}
template<typename T>
struct Graph {
vector<const Node<T>* > nodes;
Graph& AddNode(const Node<T>& input) {
nodes.push_back(&input);
return *this;
}
void Print() {
for(typename vector<const Node<T>* >::const_iterator iter = nodes.begin();
iter != nodes.end();
iter++)
{
cout << (*iter)->data << ":";
for(typename vector<Node<T>* >::const_iterator child = (*iter)->children.begin();
child != (*iter)->children.end();
child++)
{
cout << (*child)->data << ", ";
}
cout << endl;
}
}
};
// using BFS to determine if path exists
template<typename T>
bool PathExist(Graph<T>& graph, Node<T>& a, Node<T>& b) {
map<const Node<T>* , bool> t_visited;
queue<Node<T>* > t_queue;
for(typename vector<const Node<T>* >::const_iterator iter = graph.nodes.begin();
iter != graph.nodes.end(); iter++)
{
t_visited[*iter] = false;
}
t_queue.push(&a);
Node<T>* t_node;
while(!t_queue.empty()) {
// get the top object
t_node = t_queue.front();
t_queue.pop();
// set visited
t_visited[t_node] = true;
// node doesn't have the == operator
if(*t_node == b) return true;
// for each ot it's children
for(typename vector<Node<T>* >::iterator iter = t_node->children.begin();
iter != t_node->children.end(); iter++)
{
// if item has not been visited
if(!t_visited[(*iter)]) {
t_queue.push((*iter));
}
}
}
return false;
}
};