Representing an adjacency list (graph) using a hash table of lists

Question

While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews.

I tried to implement the graph as follows:

template <typename T, typename K> struct graph {
    unordered_map< T, list< pair<T, K> > > adjList;
    bool directed = 1; 
};

This allowed me to store a list of pairs (where first is the destination vertex, and second is the weight) for every vertex, and the adjacency list can be indexed by the vertex content.

So far, I was able to implement the basic operations successfully:

• insertEdge()
• removeEdge()
• searchEdge()
• printGraph() (prints all edges)

These operations behave correctly for both directed and undirected graphs.

template <typename T, typename K> struct graph {
    unordered_map< T, list< pair<T, K> > > adjList;
    bool directed = 1;
};

template <typename T, typename K> void reinit(graph<T, K>& g, bool directed) 
{
    g.directed = directed;
    g.adjList.clear();
}


template <typename T, typename K> void insertEdge(graph<T, K>& g, T v1, T v2, K weight)
{
    g.adjList[v1].push_front(std::make_pair(v2, weight));
    if (!g.directed)
        g.adjList[v2].push_front(std::make_pair(v1, weight));
}


template <typename T, typename K> void printGraph(graph<T, K>& g)
{
    cout << "Graph is " << (g.directed ? "directed" : "undirected") << endl;
    for (const auto& v : g.adjList) //for every vertex
        for (const auto& e : v.second)
            cout << v.first << "---" << e.second << "---" << e.first << endl;
}


template <typename T, typename K> K searchEdge(graph<T, K>& g, T v1, T v2)
{   //test if edge(v1,v2) is graph
    auto l = g.adjList.find(v1);
    if (l != g.adjList.end())
        for (auto e : l->second)
            if (e.first == v2)
                return e.second;

    return numeric_limits<K>::min();
}


template <typename T, typename K> void removeEdge(graph<T, K>& g, T v1, T v2)
{
    if (GRAPH::searchEdge(g, v1, v2) != numeric_limits<K>::min())
    {
        auto l = g.adjList.find(v1);
        for (auto e = l->second.begin(); e != l->second.end(); e++)
            if (e->first == v2)
            {
                l->second.erase(e);
                return;
            }
    }
}

For the most part, I found trouble implementing breadth-first search and depth-first search algorithms. If the current structure is not that great, please suggest any changes/reformulations. If it's passable, please suggest how I can approach those mentioned algorithms.

Answer 1

General Comments

Write your code for readability.

You don't normally see templates written like this:

template <typename T, typename K> void printGraph(graph<T, K>& g)

It pushes the information you want all the way to the right. Normally, I would expect to see the template code on the first line, followed by the object it templates (looking like a normal bit of code):

template <typename T, typename K>
void printGraph(graph<T, K>& g)

The space between > when closing a template has not been needed in over 5 years. Let it be consigned to the big bit bucket in the sky.

 list<pair<T, K> > >

I notice your lack of using std:: when declaring your types.

 unordered_map< T, list

This not only means you have using namespace std; in your code, but that you have it in a header file (or you have a lot of using XXXX; but causes the same issues). The use of using namespace std; in normal code is considered bad practice. But the use of it in a header file is so bad that people will ban your code from projects. You are basically infecting any code that includes your header. This can lead to subtle, impossible-to-find errors. Don't do it.

I would also prefer if you would use an initial capital letter for type information. The most important part of C++ is the type system. Being able to identify types easily is essential. Thus, most people use an initial capital letter to identify user-defined types, while an initial lower-case letter identifies an object.

Build your types from smaller types. This will make it easier to maintain your code as it localizes changes. For example, rather than using std::pair<T, K> as your edge definition, prefer to use a named type Edge. That way, if you change the definition of the type, you only have to change it in a single location and not trawl through your code looking for all uses. Also, using a name like that provides context and meaning, which in turn makes your code easier to read.

template <typename T, typename K>
struct Graph
{
    using Edge        = std::pair<T, K>;
    using EdgeList    = std::list<Edge>;
    using AdjencyList = std::unordered_map<T, EdgeList>;

    AdjencyList adjList;
    bool        directed = true; // use real bool(s) not int.
};

Design Comments

You are completely ignoring encapsulation. Your functions may work, but because your data is completely exposed, there is no protection from a bad coder coming along and breaking your constraints. Your methods are supposed to be the only way to manipulate the state (so it can be controlled).

Because of this, your code would fail any competent code review and not be allowed into the code base.