2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You must include the functions you want reviewed. A 100 line header isn't the biggest question you'll see on this SE. \$\endgroup\$ – ratchet freak Jan 25 '17 at 15:32
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Edward Jan 25 '17 at 15:53
  • \$\begingroup\$ 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. \$\endgroup\$ – StrayPointer Jan 25 '17 at 16:09
  • \$\begingroup\$ List is usually slow in practice, any reason you want to not just use a vector? \$\endgroup\$ – Raziman T V Jan 25 '17 at 16:48
  • \$\begingroup\$ 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. \$\endgroup\$ – StrayPointer Jan 25 '17 at 17:00
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I do not have using namespace std; in my code, I have all the include directives and using statements in a seperate .h file because many of the headers use those so I grouped them and I just include that file on need. This is the way I grouped them, github.com/theStrayPointer/Stray-Algorithms/blob/master/… I was kind of mimicking what visual studio does via stdafx.h \$\endgroup\$ – StrayPointer Jan 25 '17 at 19:31
  • \$\begingroup\$ I have considered writing code in OOP, the purpose of the code is not to be production code but to be a way for me to improve my problem solving skills and algorithm implementation skills. But if you advise writing in OOP, I will convert my code since I'm pretty comfortable working with it (at my level). \$\endgroup\$ – StrayPointer Jan 25 '17 at 19:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin York Jan 25 '17 at 20:13
  • \$\begingroup\$ @ Loki Astari understood thank you. Originally my headers weren't generic so I had .h files and .cpp files that included the header having the using declarations, but templates are in .h files, I ended up doing things that way. But now I'll add std:: to my identifies. \$\endgroup\$ – StrayPointer Jan 25 '17 at 20:27
  • \$\begingroup\$ @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. \$\endgroup\$ – πάντα ῥεῖ Jan 25 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.