Graph implementation to be used for finding Cycles, Paths, closest path between two nodes, etc

Question

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





};

Answer 1

That depends on what is good in some sense. It's a pretty standard adjacency list implementation, and it's nothing wrong with that. Whether it's good depends on what query you gonna ask the data structure. If doing path search or minimal spanning tree for sparse graph that is good. If you want to do some clustering, then maybe an adjacency matrix is better.

On the API level, I like that chaining add methods. It's nice and easy to use. Storing pointer to aliases avoided the problem of memory leakage, but it makes the programmer feel a bit silly to declare a variable for each node, with only one character in it. What if the number of nodes dynamically grows, which is one of the strength of using an adjacency list? Why can't I do like graph.AddNode('a')? And add child by graph.get('a').AddChild('b') or something.

Also if the node local variables goes out of scope, the graph must die or in danger of facing segmentation fault, or even some security issues. Not very flexible.

Answer 2

Public Implementation: Bad

No. You are basically allowing intrusion into the implementation details to implement anything.

struct Graph {
    vector<const Node<T>* > nodes;

Basically you are going to cause headaches for your self down the road because you have expose the implementation details of how the graphs stores its data. People now have to use this to write their functions.

Lock down your member vaiables and provide access to the class via methods to add nodes and edges.

Visitor Pattern

You should also look up the visitor pattern. This allows people to write graph traversal algorithms without knowing details about the graph.

Stop using using

using std::map;
using std::vector;
using std::cout;
using std::endl;
using std::queue;

You are going to break somebody else code by putting this in the header file. I don't like you using this in a source file (unless you scope it very closely). But putting this in a header file is a define no-no. If I include your header file in my source file you can potentially cause breaking changes in my code that are nearly undetectable. As a result you will find most project will refuse to use your code because of the potential danger to their code base.

If you don't mind messing your own code up (obviously your don't) put it inside your own namespace so at least it does not affect my code.

Parameters

Use them correctly.

Graph& AddNode(const Node<T>& input) {
    nodes.push_back(&input);
    return *this;
}

So you can pass a node by reference. Which means that internally you will make a copy. Which makes this redundant:

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

You now have two copies of each node.

Would be easier to write like this:

graph.AddNode(Node<char>('a')).AddNode(Node<char>('b')).AddNode(Node<char>('c')).AddNode(Node<char>('d')).AddNode(Node<char>('e')).AddNode(Node<char>('f'));

But that seems a bit verbose. So you could have written a helper function that does type deduction for you.

template<typename T>
Node<T> mkNode(T const& v) {return Node<T>(v);}

  graph.AddNode(mkNode('a')).AddNode(mkNode('b')).AddNode(mkNode('c')).AddNode(mkNode('d')).AddNode(mkNode('e')).AddNode(mkNode('f'));

Or even better just write an AddNode() that takes a T and internall creates a Node of the correct type.

graph.AddNode('a').AddNode('b').AddNode('c').AddNode('d').AddNode('e').AddNode('f');