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

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

template <typename T, typename K> void insertEdge(graph<T, K>& g, T v1, T v2, K weight)
{
if (!g.directed)
}

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
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())
{
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.

• You must include the functions you want reviewed. A 100 line header isn't the biggest question you'll see on this SE. – ratchet freak Jan 25 '17 at 15:32
• I don't have time to do a full review, but generally, I would suggest this: 1) Write, test and thoroughly debug a concrete implementation first and then 2) adapt it to a templated design. – Edward Jan 25 '17 at 15:53
• I have tested all the implemented operations as I said, they all work as supposed, as for your second advice, I didn't understand that well, thank you either way. – StrayPointer Jan 25 '17 at 16:09
• List is usually slow in practice, any reason you want to not just use a vector? – Raziman T V Jan 25 '17 at 16:48
• I don't expect to have dense graphs so the list vs vector performance won't matter bigtime. Although, on removeEdge() operations lists should be much more efficient. – StrayPointer Jan 25 '17 at 17:00

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

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


• Putting using std::string; in the header file is nearly as bad as using namespace std; Only ever do that in source files. If your header file is included by another project you may change the definition of their code because of your pollution of the global namespace. It is much much better to just get used to using the prefix std:: on everything. It is only three letters for a reason. – Martin York Jan 25 '17 at 20:13
• @Loki "This not only means you have using namespace std;" They don't have it. actually I checked the formerly present github link that introduces an obscure header file, collating all of the used standard classes with using statements. – πάντα ῥεῖ Jan 25 '17 at 21:38