Compute shortest path in undirected graph

Question

In a recent coding interview I was asked to write a program which takes as input two text lines:

• The first one represents a graph, formatted as a sequence of undirected edges like [A,B,10] [B,C,4]
• The second one represents two nodes, between which the shortes path is to be found, and the maximum acceptable distance, formatted like A->C,20.

the output is a representation of this shortest path, like A->C.

/*************************
 * BEGIN default includes
 *************************/
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
/*************************
 * END default includes
 *************************/

#include <unordered_set>

#define DEBUG_QUIET 0
#define DEBUG_INFO 1
#define DEBUG_VERBOSE 2

#define DEBUG DEBUG_QUIET // Edit to change debug output level

#if DEBUG >= DEBUG_VERBOSE
#define PRINT_VERBOSE(x) x
#else 
#define PRINT_VERBOSE(x)
#endif
#if DEBUG >= DEBUG_INFO
#define PRINT_INFO(x) x
#else 
#define PRINT_INFO(x)
#endif

using namespace std;

class E1 : exception {};
class E2 : exception {};
class E3 : exception {};

class Graph {
    
    public:
        /**
        * @brief Constructs a graph from a string.
        * @param    s   The first line of input
        */
        Graph(const string s) {
            string::const_iterator it = s.begin();
            bool done = false;
            while (!done) {
                expect(it,'[');
                char n1 = *(it++);
                expect(it,',');
                char n2 = *(it++);
                expect(it,',');
                unsigned weight = extractNumber(it, s.end());
                expect(it,']');
                if (it==s.end()) done = true;
                if (!done) expect(it,' ');
                PRINT_VERBOSE(cout << "New edge: ["<< n1 << "," << n2 << "," << weight << "] " << endl; )
                
                m_graphMap.insert(make_pair(n1,NeighborSet_t()));
                NeighborSet_t* ns1 = &m_graphMap.find(n1)->second;
                if (ns1->find(Node_t(n2))!=ns1->end()) { throw E2(); }
                ns1->insert(Node_t(n2,weight));

                m_graphMap.insert(make_pair(n2,NeighborSet_t()));
                NeighborSet_t* ns2 = &m_graphMap.find(n2)->second;
                if (ns2->find(Node_t(n1))!=ns2->end()) { throw E2(); }
                ns2->insert(Node_t(n1,weight));
            }
            PRINT_VERBOSE(cout << "Parsing graph string complete" << endl);
        }
        /**
        * @brief Computes the Shortest Path from two points.
        * @param    s   The second line of input
        * @return       A representation of the Shortest Path according to the specification
        */
        string sp(const string s) const {
            char start_node, end_node;
            unsigned maxdist;
            parseSPTstring(s, start_node, end_node, maxdist);
            PRINT_INFO(cout << "Searching for path from " << start_node << " to " << end_node << " (maxdist: " << maxdist << ")" << endl);
            if (m_graphMap.find(start_node) == m_graphMap.end() || m_graphMap.find(end_node) == m_graphMap.end() )
                throw E2(); // Not in graph!
            GraphMap_t spt;
            MinHeap_t minHeap; // Stores a set of nodes, ordered by distance
            minHeap.insert(Node_t(start_node,0)); // Will insert again, but next insert will be ignored
            PRINT_INFO( cout << "Initializing minHeap" << endl; )
            Visited_t visited;
            initMinHeap(start_node, visited, minHeap);
            PRINT_INFO( cout << "Computing SPT" << endl; )
            buildSPT(minHeap, spt);
            PRINT_VERBOSE( visited = Visited_t(); printGraph(start_node,visited,spt); )
            PRINT_VERBOSE( cout << "Generating SPT string" << endl; )
            visited = Visited_t(); // Reset
            return generateSPString(start_node,end_node,visited,spt,maxdist);
        }
        
    private:
        /**********
         * Types
         **********/
        typedef unordered_set<char> Visited_t;
        class Node_t {
            public:
                const char name;
                const unsigned distance;
                bool operator== (const Node_t& other) const { return this-> name == other.name; }
                bool operator< (const Node_t& other) const { 
                    if (*this==other) 
                        return false; // Same node, reflexively false
                    else 
                    { 
                        if (this->distance == other.distance)
                            return this->name < other.name; // Don't care, sort by name 
                        else
                            return this->distance < other.distance;
                    } 
                }
                Node_t(char n, unsigned d = UINT_MAX) : name(n), distance(d) {};
        };
        typedef set<Node_t> NeighborSet_t; // Can't use unordered_set because it needs to be hashable
        typedef set<Node_t> MinHeap_t;
        typedef unordered_map<char, NeighborSet_t> GraphMap_t;
        
        /*********************************************
         * Helper functions for parsing / debugging
         *********************************************/
         
        /**
        * @brief Throws an exception if it finds unexpected characters.
        * @param    it  An iterator over the input string
        * @param    c   The expected character
        */
        static void expect(string::const_iterator& it,char c){
            PRINT_VERBOSE( cout << "Expecting '" << c << "', found '" << *it << "' "; )
            if (!(c==*it)) throw E1(); // Invalid formatting of the input string
            it++;
            return;
        }
        /**
        * @brief Useful to extract numbers of arbitraty digits.
        * @param    start   Beginning of digits
        * @param    end     End of the string
        * @return           The index of the last digit of this number
        */
        static unsigned extractNumber(string::const_iterator& start, const string::const_iterator& end) {
            string::const_iterator weight_end = find_if(start, end, not1(ptr_fun<int, int>(isdigit)));
            unsigned weight;
            try { 
                weight = stoi(string(start,weight_end));
            } catch (invalid_argument) {
                throw E1(); // Garbage in the input string
            }
            start = weight_end;
            return weight;
        }
        /**
        * @brief Parse path specification.
        * @param    s           The second line of input
        * @param    start_node  Will be overwritten with the start node name
        * @param    end_node    Will be overwritten with the end node name
        */
        static void parseSPTstring(const string s, char& start_node, char& end_node, unsigned& maxdist) {
            string::const_iterator it = s.begin();
            start_node = *(it++);
            expect(it, '-');
            expect(it, '>');
            end_node = *(it++);
            expect(it, ',');
            maxdist = extractNumber(it, s.end());
            if (!(s.end()==it)) throw E1(); // Trailing characters
        }
        /**
        * @brief DFS recursive function to print a graph. For debugging.
        * @param    node        The current root node
        * @param    visited     Unordered set of visited node names
        * @param    g           The graph
        */
        static void printGraph(char node, Visited_t& visited, const GraphMap_t& g) {
            if (visited.find(node)!=visited.end()){ 
                PRINT_VERBOSE( cout << "Not visiting " << node << " again. "; )
                return;
            }
            PRINT_VERBOSE( cout << "Visit " << node << ". ");
            visited.insert(node);
            const NeighborSet_t neighborSet = g.at(node);
            for ( Node_t n : neighborSet) {
                cout << "[" << node << "," << n.name << "," << n.distance << "] ";
                printGraph(n.name, visited, g);
            }
            PRINT_VERBOSE( cout << "Step out " << node << ". " << endl);
        }
        /**
        * @brief Function to print the minHeap. For debugging.
        * @param    minHeap The minHeap
        */
        static void printMinHeap(const MinHeap_t& minHeap) {
            for (MinHeap_t::iterator it = minHeap.begin(); it!=minHeap.end(); it++) {
                cout << (*it).name << ":" << (*it).distance << "; ";
            }; 
        }
        /**
        * @brief Recursive function to generate a string representing the SP according to the specification.
        * @param    start_node  Char name of the start of the path node
        * @param    end_node    Char name of the end of the path node
        * @param    visited     Unordered set of visited node names. SPT is an ADG, but may still print the same node multiple times
        * @param    spt         Acyclic, directed graph representing the Shortest Path Tree
        * @param    maxdist     Maximum allowed distance from the start node
        * @return               The string representation of the SP
        */
        static string generateSPString(const char start_node, const char end_node, Visited_t& visited, GraphMap_t& spt, const unsigned maxdist){
            if (visited.find(start_node)!=visited.end()){ 
                PRINT_VERBOSE( cout << "Not visiting " << start_node << " again. "; )
                return "";
            }
            PRINT_VERBOSE( cout << "Visit " << start_node << ". "; )
            visited.insert(start_node);
            stringstream ss;
            if (start_node==end_node) {
                    ss << end_node;
                    return ss.str();
            }
            const NeighborSet_t neighborSet = spt.at(start_node);
            if (neighborSet.empty()) return "";
            for ( Node_t n : neighborSet) {
                if (n.name==end_node) {
                    if (n.distance>maxdist)
                        throw E3();
                }
                ss << generateSPString(n.name, end_node, visited, spt, maxdist);
            }
            PRINT_VERBOSE( cout << "Step outside " << start_node << ". "; )
            stringstream ss2;
            if (!ss.str().empty())
                ss2 << start_node << "->" << ss.str();
            else
                ss2 << ss.str();
            PRINT_VERBOSE( cout << "Returning '" << ss2.str() << "'. "; )
            return ss2.str();
        }
        
        /*************************
         * Dijkstra Implementation
         *************************/
         
        /**
        * @brief Recursive DFS to populate the minHeap.
        * @param    node        Current root note
        * @param    visited     Unordered set of already visited node names, to avoid loops since the graph is undirected
        * @param    minHeap     The minHeap to be generated
        */
        void initMinHeap(const char node, Visited_t& visited, MinHeap_t& minHeap) const{
            if (visited.find(node)!=visited.end()){ 
                PRINT_VERBOSE(cout << "Not visiting " << node << " again. ");
                return;
            }
            PRINT_VERBOSE( cout << "Visit " << node << ". ");
            visited.insert(node);
            PRINT_VERBOSE( cout << "Add " << node << " to minHeap. ");
            minHeap.insert(Node_t(node,UINT_MAX));
            NeighborSet_t neighborSet = m_graphMap.at(node);
            for ( Node_t n : neighborSet) {
                initMinHeap(n.name, visited, minHeap);
            }
            PRINT_VERBOSE(cout << "Step out " << node << ". " << endl);
        }
        /**
        * @brief Computes the SPT from the minHeap.
        * @param    minHeap     The minHeap
        * @param    spt         The SPT
        */
        void buildSPT(MinHeap_t& minHeap, GraphMap_t& spt) const{
            while (!minHeap.empty()) {
                Node_t minNode = *(minHeap.begin());
                PRINT_VERBOSE( cout << "Closest neighbor is " << minNode.name << ", dist: " << minNode.distance << ", deleting from minHeap. "; cout << endl; )
                minHeap.erase(minHeap.find(minNode));
                PRINT_VERBOSE(  cout << "MinHeap: "; printMinHeap(minHeap); )
                spt.insert(make_pair(minNode.name,NeighborSet_t()));
                for (Node_t n : m_graphMap.at(minNode.name)) {
                    PRINT_VERBOSE( cout << "Find node " << n.name << "... "; )
                    MinHeap_t::iterator i = minHeap.find(Node_t(n.name));
                    if (i==minHeap.end()) {
                        PRINT_VERBOSE( cout << "not in minHeap, skipping. "; )
                        continue;
                    }
                    unsigned newDist = minNode.distance+n.distance;
                    if (newDist>(*i).distance){
                        PRINT_VERBOSE( cout << "New distance (" << newDist << ") is greater than the current one (" << (*i).distance << "). Continue."; )
                        continue;
                    }
                    PRINT_VERBOSE(cout << "Delete node " << (*i).name << ", distance " << (*i).distance << ". "; )
                    minHeap.erase(i);
                    PRINT_VERBOSE( cout << "MinHeap after erase: "; printMinHeap(minHeap); cout; )
                    PRINT_VERBOSE( cout << "Insert node " << n.name << ", distance " << newDist << ". "; )
                    minHeap.insert(Node_t(n.name,newDist));
                    PRINT_VERBOSE( cout << "MinHeap after insert: "; printMinHeap(minHeap); )
                    spt[minNode.name].insert(Node_t(i->name,newDist)); // Store the distance in the dual graph
                }
                PRINT_VERBOSE( cout << endl; )
            }
            PRINT_VERBOSE(cout << "SPT done." << endl; )
        }
        
        /* 
         * Members
         */
        GraphMap_t m_graphMap = GraphMap_t();
};

int main() {
    string edgeString;
    getline(cin,edgeString);
    string pathString;
    getline(cin,pathString);
    PRINT_INFO( cout << edgeString << endl << pathString << endl; )
    try {
        const Graph g = Graph(edgeString);
        string spt = g.sp(pathString);
        if (spt.empty()) {
            cout << "E3";
            return 0;
        }
        cout << spt << endl;
    } catch (E1) { 
        cout << "E1" << endl;
        return 0;
    } catch (E2) {
        cout << "E2" << endl;
        return 0;
    } catch (E3) {
        cout << "E3" << endl;
        return 0;
    }
    return 0;
}

My code was an implementation of the Dijkstra algorithm with min heap, which I thought was the most efficient algorithm for this problem, and I was passing all tests; nevertheless, I failed the interview.

How does my code look?

Answer 1

Intro code:

There's a lot of "instant fail"s here:

• Include only the headers you need!

• Debugging macros are probably not acceptable for something like this. We can step through in a debugger if we need to manually check what's happening in the code. If we want to "prove" that the code is working correctly, we should use unit tests.

  The macros make the code a lot harder to read and maintain.

• using namespace std; This leads to namespace collisions. Don't do it.

• class E1 : exception {}; Not a helpful name. Try InvalidInputException or something similar.

---

Graph class constructor:

• Graph(const string s) That's an unnecessary string copy. We should pass a const std::string&.

• The parsing code shouldn't be part of the Graph class. If we want to add a different text format later, we shouldn't have to change the Graph class.

  The Graph could be a simple struct containing only data. The parsing could be done by a set of free (non-member) functions.

• expect(it,'['); If it is at the end() of the string, dereferencing it will cause undefined behavior.

•           m_graphMap.insert(make_pair(n1,NeighborSet_t()));
            NeighborSet_t* ns1 = &m_graphMap.find(n1)->second;
            if (ns1->find(Node_t(n2))!=ns1->end()) { throw E2(); }
            ns1->insert(Node_t(n2,weight));
  

  insert returns an iterator to the inserted element (or the one that prevented insertion), so we shouldn't need to find it again straight afterwards.

  Consider using operator[] instead. With a few minor changes the above might be condensed to: m_graphMap[n1][n2].distance = weight;

• Is there actually a reason to store the neighbours as a set, instead of a std::vector<std::pair<char, unsigned int>>?

---

Dijkstra implementation:

• sp() should be called findShortestPath() or something equally meaningful.

• string sp(const string s) const. Again, an unnecessary string copy.

• Again, the parsing of the user input should be done separately, and not in the graph class, or in the findShortestPath function.

• Note that the findShortestPath function should also be separate from the Graph class. (It's good that you're not storing any data from the path finding inside the Graph class as members, but we could separate the function (and typedefs) entirely).

• void initMinHeap(const char node, Visited_t& visited, MinHeap_t& minHeap) It looks like this recursively adds every node in the graph onto the min heap. We don't need to do that!

  Since we have a fixed destination node, we shouldn't process the entire graph. We want to pick the closest node off the queue and check if it's the one we're looking for. If not, we add its neighbours to the queue and then check the next closest node.

•       NeighborSet_t neighborSet = m_graphMap.at(node);
  

  This copies an entire std::set unnecessarily.

•           Node_t minNode = *(minHeap.begin());
            minHeap.erase(minHeap.find(minNode));
  

  We already know where the element we want to remove is, so we shouldn't have to call find.

---

Answer 2

In addition to user673679 and Toby Speight's answers, here are a few more issues:

Use a consistent code style

Sometimes I see spaces around commas, sometimes not, the body of if statements is sometimes on the same line, sometimes on separate lines. It makes the code messy to look at. The least you can do is run it through some automated code formatting; either your editor can do it, or you can use an external tool like Artistic Style or ClangFormat.

In particular, make sure every statement is on a separate line, add spaces around operators and after commas, and don't be afraid to separate segments of code with empty lines.

Improve the Doxygen documentation

It's great that you documented the code using Doxygen! There are a few slight improvements you could make though:

If you pass something by non-const reference or non-const pointer, be sure to add [in], [out] or [in,out] annotations to the parameters in the Doxygen comments.

Also ensure you add a Doxygen header for each class itself, not just for its member variabels and functions. Describe what the class is meant to represent.

Use emplace() where appropriate

If you use emplace() instead of insert(), you don't have to call make_pair() or explicitly construct a type:

m_graphMap.emplace(n1, NeighborSet_t());
...
ns1->emplace(n2,weight);

Avoid useless braces, parentheses, etc.

There are a few uses of unnecessary syntax that makes the code just harder to read. For example:

• *(it++) -> *it++
• !(c==*it) -> c != *it
• (*i).distance -> i->distance

Your use of this-> is unnecessary, but in the case of the binary operator overloads, it's actually a nice way to keep expressions symmetric and clearly indicate which side's member variable you are using.

Missed opportunities for using range-for loops

In printMinHeap, you could write:

for (auto &item: minHeap)
    std::cout << item.name << ": " << item.distance << "; ";

Make Node_t hashable

You wrote you couldn't use a std::unordered_set for NeighborSet_t because "it needs to be hashable". So why not make it hashable? You already had to overload operator< to make it comparable so it could be used in a std::set. There's two ways to approach this:

1. Pass a hash function as a parameter to std::unordered_set.
2. Overload std::hash to be able to produce a hash for Node_t.

Use of stringstreams

A std::stringstream is helpful if you are adding a lot of data to it, but if you convert to and from std::strings a lot, any performance benefit is lost. This is exactly what you do in generateSPString(). Better would be to pass if you pass it an std::stringstream by reference, and have it add to that, but that requires you being able to write everything sequentially, but currently you also want to prepend things to the string. In that case, maybe just use std::string for everything.

Better printing functions

You have functions like printGraph() that are hardcoded to print to std::cout. Better would be to pass a std::ostream reference to the functions, so they can print to that:

static void printGraph(std::ostream &out, ...) {
    ...
    out << "[" << ...;
    ...
}

You can also create an overload for operator<< (see this tutorial) so you can write this:

Graph g(...);
std::cout << g;

Use '\n' instead of std::endl

Prefer using '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed. That is usually not necessary, and comes with a performance overhead.

Answer 3

Do you really use all these?:

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

Such a large list of includes can often be a sign of too many different responsibilities for a single translation unit. Or of a developer too lazy to actually consider what's required.

---

using namespace std;

Throwing away all the benefits of namespaces and piling the whole of std into the global namespace is an instant review fail in many (most?) development teams.

---

#define DEBUG DEBUG_QUIET // Edit to change debug output level

#if DEBUG >= DEBUG_VERBOSE
#define PRINT_VERBOSE(x) x
#else 
#define PRINT_VERBOSE(x)
#endif
#if DEBUG >= DEBUG_INFO
#define PRINT_INFO(x) x
#else 
#define PRINT_INFO(x)
#endif

I have to recompile just to change the debugging level??

And you're introducing macros that can't be used like functions - avoid that unless there's no alternative.

---

class E1 : exception {};
class E2 : exception {};
class E3 : exception {};

Those are the least informative class names I've seen for some time. And why the private inheritance?

---

At this point I'd seen enough, and didn't bother reading the rest.