Finding shortest paths in directed graphs

Question

I have very little experience in programming with C++ and the following small "program" is the 2nd one I have ever written in that language. I am most interested in comments regarding naming conventions and the way the code is modularized. Also, can you tell whether the code sticks to idiomatic use of the language?

Here what I have so far:

directed_graph_node.h:

#ifndef DIRECTED_GRAPH_NODE_H
#define DIRECTED_GRAPH_NODE_H

#include <string>
#include <unordered_set>
#include <vector>

/*******************************************************************************
* This class implements a node in directed graphs. The adjacency list          *
* invariant is that if there is a directed edge from u to v, u.m_out has a     *
* pointer to v, and v.m_in has a pointer to u.                                 *
*******************************************************************************/
class DirectedGraphNode {
public:
    DirectedGraphNode(const std::string name);
    void add_child(DirectedGraphNode& child);
    bool has_child(DirectedGraphNode& query);
    void remove_child(DirectedGraphNode& child);

    // Child iterators.
    std::unordered_set<DirectedGraphNode*>::const_iterator begin();
    std::unordered_set<DirectedGraphNode*>::const_iterator end();

    bool operator==(const DirectedGraphNode& other) const;

    friend std::ostream& operator<<(std::ostream& os, 
                                    const DirectedGraphNode& node);

    // Forward declaration.
    class ParentIteratorProxy;

    ParentIteratorProxy parents();

    class ParentIteratorProxy {
    public:
        ParentIteratorProxy(const DirectedGraphNode* owner);
        std::unordered_set<DirectedGraphNode*>::const_iterator begin();
        std::unordered_set<DirectedGraphNode*>::const_iterator end();

    private:
        const DirectedGraphNode* mp_owner;
    };

private:
    std::string m_name;
    std::unordered_set<DirectedGraphNode*> m_in;
    std::unordered_set<DirectedGraphNode*> m_out;
};

#endif  // DIRECTED_GRAPH_NODE_H

directed_graph_node.cpp:

#include <iostream>
#include <stdexcept>
#include <unordered_set>

#include "directed_graph_node.h"

/*******************************************************************************
* Constructs a new DirectedGraphNode with the given name.                      *
*******************************************************************************/
DirectedGraphNode::DirectedGraphNode(const std::string name) {
    m_name = name;
}

/*******************************************************************************
* Creates a directed edge from this node to node 'child'.                      *
*******************************************************************************/ 
void DirectedGraphNode::add_child(DirectedGraphNode& child) {
    m_out.insert(&child);
    child.m_in.insert(this);
}

/*******************************************************************************
* Queries whether there is an arc (this, query).                               *
*******************************************************************************/
bool DirectedGraphNode::has_child(DirectedGraphNode& query) {
    if (m_out.find(&query) == m_out.end()) {
        if (query.m_in.find(this) != query.m_in.end()) {
            // The adjacency list invariant is broken. See the header.
            throw std::runtime_error("Adjacency list invariant broken. 1/2.");
        }

        return false;
    } else if (query.m_in.find(this) == query.m_in.end()) {
        throw std::runtime_error("Adjacency list invariant broken. 2/2.");
    }

    return true;
}

/*******************************************************************************
* Removes the edge (this, child).                                              *
*******************************************************************************/
void DirectedGraphNode::remove_child(DirectedGraphNode& child) {
    m_out.erase(&child);
    child.m_in.erase(this);
}

/*******************************************************************************
* Compares by name this node to 'other'.                                       *
*******************************************************************************/
bool DirectedGraphNode::operator ==(const DirectedGraphNode& other) const {
    return this->m_name.compare(other.m_name) == 0;
}

/*******************************************************************************
* Returns a const iterator to a child node of this node.                       *
*******************************************************************************/
std::unordered_set<DirectedGraphNode*>::const_iterator 
DirectedGraphNode::begin() {
    return m_out.begin();
}

/*******************************************************************************
* Returns a const iterator to the end of child list.                           *
*******************************************************************************/
std::unordered_set<DirectedGraphNode*>::const_iterator
DirectedGraphNode::end() {
    return m_out.end();
}

/*******************************************************************************
* Returns a proxy iterator over a node's parent nodes.                         *
*******************************************************************************/
DirectedGraphNode::ParentIteratorProxy
                 ::ParentIteratorProxy(const DirectedGraphNode* p_owner) : 
                 mp_owner(p_owner) {}

/*******************************************************************************
* Returns the first parent node in the parent list of the owner node.          *
*******************************************************************************/
std::unordered_set<DirectedGraphNode*>::const_iterator
DirectedGraphNode::ParentIteratorProxy::begin() {
    return mp_owner->m_in.begin();
}

/*******************************************************************************
* Returns an iterator pointing to the end of owner node's parent list.         *
*******************************************************************************/
std::unordered_set<DirectedGraphNode*>::const_iterator
DirectedGraphNode::ParentIteratorProxy::end() {
    return mp_owner->m_in.end();
}

/*******************************************************************************
* Returns an iterator over owner node's parent list.                           *
*******************************************************************************/
DirectedGraphNode::ParentIteratorProxy DirectedGraphNode::parents() {
    return ParentIteratorProxy(this);
}

/*******************************************************************************
* Neatly prints a node.                                                        *
*******************************************************************************/
std::ostream& operator<<(std::ostream& os, const DirectedGraphNode& node) {
    return os << "[DirectedGraphNode " << node.m_name << "]";
}

path_finder.h:

#ifndef PATHFINDER_H
#define PATHFINDER_H

#include <algorithm>
#include <unordered_map>
#include <vector>

#include "directed_graph_node.h"

using std::unordered_map;
using std::vector;

class PathFinder {
public:
    virtual std::vector<DirectedGraphNode*>* 
        search(DirectedGraphNode& source,
               DirectedGraphNode& target) = 0;

    vector<DirectedGraphNode*>* 
        construct_path(DirectedGraphNode* touch,
                       unordered_map<DirectedGraphNode*,
                                     DirectedGraphNode*>* p_parents_f,
                       unordered_map<DirectedGraphNode*,
                                     DirectedGraphNode*>* p_parents_b) {
        vector<DirectedGraphNode*>* p_path = new vector<DirectedGraphNode*>;
        DirectedGraphNode* u = const_cast<DirectedGraphNode*>(touch);

        while (u) {
            p_path->push_back(u);
            u = (*p_parents_f)[u];
        }

        std::reverse(p_path->begin(), p_path->end());

        if (p_parents_b) {
            u = (*p_parents_b)[touch];
            while (u) {
                p_path->push_back(u);
                u = (*p_parents_b)[u];
            }
        }

        return p_path;
    }
};

#endif // PATHFINDER_H

bfs_path_finder.h:

#ifndef BFS_PATH_FINDER_H
#define BFS_PATH_FINDER_H

#include <deque>
#include <iostream>
#include <vector>
#include <unordered_map>

#include "directed_graph_node.h"
#include "path_finder.h"

/*******************************************************************************
* Implements a path finder using breadth-first search in unweighted digraphs.  *
*******************************************************************************/
class BFSPathFinder : public PathFinder {
public:
    std::vector<DirectedGraphNode*>* search(DirectedGraphNode& source,
                                            DirectedGraphNode& target) {
        m_queue.clear();
        m_parent_map.clear();

        // Initialize the state.
        m_queue.push_back(&source);
        m_parent_map[&source] = nullptr;

        while (!m_queue.empty()) {
            DirectedGraphNode* p_current = m_queue.front();

            if (*p_current == target) {
                // Reached the target.
                return construct_path(p_current, &m_parent_map, nullptr);
            }

            m_queue.pop_front();

            for (auto p_child : *p_current) {
                if (m_parent_map.find(p_child) == m_parent_map.end()) {
                    m_parent_map.insert({p_child, p_current});
                    m_queue.push_back(p_child);
                }
            }
        }

        return nullptr;
    }

private:
    std::deque<DirectedGraphNode*> m_queue;
    std::unordered_map<DirectedGraphNode*, 
                       DirectedGraphNode*> m_parent_map;
};

#endif // BFS_PATH_FINDER_H

bibfs_path_finder.h:

#ifndef BIBFS_PATH_FINDER_H
#define BIBFS_PATH_FINDER_H

#include <deque>
#include <iostream>
#include <vector>
#include <unordered_map>

#include "directed_graph_node.h"
#include "path_finder.h"

/*******************************************************************************
* Implements a path finder using bidirectional breadth-first search for        *
* unweighted digraphs.                                                         *
*******************************************************************************/
class BidirectionalBFSPathFinder : public PathFinder {
public:
    std::vector<DirectedGraphNode*>* search(DirectedGraphNode& source,
                                            DirectedGraphNode& target) {
        m_queue1.clear();
        m_queue2.clear();
        m_parent_map1.clear();
        m_parent_map2.clear();
        m_distance_map1.clear();
        m_distance_map2.clear();

        // Initialize the state.
        m_queue1.push_back(&source);
        m_queue2.push_back(&target);
        m_parent_map1[&source] = nullptr;
        m_parent_map2[&target] = nullptr;
        m_distance_map1[&source] = 0;
        m_distance_map2[&target] = 0;

        // A node where the two search frontiers "meet".
        DirectedGraphNode* p_touch = nullptr;
        // The best known cost of a shortest path.
        size_t best_cost = std::numeric_limits<std::size_t>::max();

        while (m_queue1.size() > 0 && m_queue2.size() > 0) {
            if (p_touch != nullptr
                    && m_distance_map1[m_queue1.front()] 
                     + m_distance_map2[m_queue2.front()] >= best_cost) {
                // Termination condition met.
                return construct_path(p_touch,
                                      &m_parent_map1,
                                      &m_parent_map2);
            }

            // A trivial load balancing.
            if (m_queue1.size() < m_queue2.size()) {
                // Once here, expand the forward search frontier.
                DirectedGraphNode* p_current = m_queue1.front();

                if (m_parent_map2.find(p_current) != m_parent_map2.end()) {
                    // Here, update to the shortest path is possible.
                    const size_t tmp = m_distance_map1[p_current] +
                                       m_distance_map2[p_current];

                    if (best_cost > tmp) {
                        // Update the current best touch node.
                        best_cost = tmp;
                        p_touch = p_current;
                    }
                }

                m_queue1.pop_front();

                // Expand the forward search frontier.
                for (auto p_child : *p_current) {
                    if (m_parent_map1.find(p_child) == m_parent_map1.end()) {
                        m_parent_map1.insert({p_child, p_current});
                        m_distance_map1.insert({
                            p_child, 
                            m_distance_map1[p_current] + 1
                        });
                        m_queue1.push_back(p_child);
                    }
                }
            } else {
                // Once here, expand the backward search frontier.
                DirectedGraphNode* p_current = m_queue2.front();

                if (m_parent_map1.find(p_current) != m_parent_map1.end()) {
                    // Here, update to the shortest path is possible.
                    const size_t tmp = m_distance_map1[p_current] +
                                       m_distance_map2[p_current];

                    if (best_cost > tmp) {
                        // Update the current best touch node.
                        best_cost = tmp;
                        p_touch = p_current;
                    }
                }

                m_queue2.pop_front();

                // Expand the backward search.
                for (auto p_parent : p_current->parents()) {
                    if (m_parent_map2.find(p_parent) == m_parent_map2.end()) {
                        m_parent_map2.insert({p_parent, p_current});
                        m_distance_map2.insert({
                            p_parent,
                            m_distance_map2[p_current] + 1
                        });
                        m_queue2.push_back(p_parent);
                    }
                }
            }
        }

        return nullptr;
    }

private:
    std::deque<DirectedGraphNode*> m_queue1;
    std::deque<DirectedGraphNode*> m_queue2;
    std::unordered_map<DirectedGraphNode*, 
                       DirectedGraphNode*> m_parent_map1;
    std::unordered_map<DirectedGraphNode*,
                       DirectedGraphNode*> m_parent_map2;
    std::unordered_map<DirectedGraphNode*,
                       size_t> m_distance_map1;
    std::unordered_map<DirectedGraphNode*,
                       size_t> m_distance_map2;
};

#endif  // BIBFS_PATH_FINDER_H

glampert · Accepted Answer · 2014-11-19 14:37:11Z

There is quite a bit of code here, so consequently my review is not going to be the definitive. The things that most caught my attention:

In all classes:

You are using very long names everywhere like in

std::unordered_set<DirectedGraphNode*>::const_iterator

It is very easy to mistype such names and get a torrent of template erros from the compiler that can be a pain to read and figure out. Replace all those with using aliases. E.g.:

using DirectedGraphNodeSet     = std::unordered_set<DirectedGraphNode*>;
using DirectedGraphNodeSetIter = DirectedGraphNodeSet::const_iterator;

directed_graph_node.cpp:

Make sure to always initialize data in the constructor by calling the constructors of the sub-objects:

DirectedGraphNode::DirectedGraphNode(std::string name)
    : m_name(std::move(name)) {
}

Also, in this case name should not be const. If it is const, you cannot move it, resulting in an extra unnecessary copy of the string.

Speaking of move, your classes don't provide move operator and constructor. Not sure if those would apply, but if you are not familiar with the concept yet (C++11), take a look at the previous link and also on The rule of three/five/zero.

throw std::runtime_error("Adjacency list invariant broken. 1/2.");

That error message is not very helpful. Better to name which invariant was broken instead of numbering it.

bool DirectedGraphNode::operator ==(const DirectedGraphNode& other) const {
    return this->m_name.compare(other.m_name) == 0;
}

Using the == operator would be more straightforward in this case:

bool DirectedGraphNode::operator ==(const DirectedGraphNode& other) const {
    return this->m_name == other.m_name;
}

path_finder.h:

One thing that bothers me in here is this vector<DirectedGraphNode*>*. You return that pointer, which is allocated with new, but it is not clear for the caller who owns it. There is potential for a memory leak there. I think a unique_ptr would be in order.

This is also not cool:

using std::unordered_map;
using std::vector;

In the global namespace, they will leak to any other file that includes path_finder.h. Replace those with a using alias inside the class.

Otherwise, the code looks nice. You have used modern C++ throughout. I hope you also get more reviews on the algorithms an architecture.

nwp · Answer 2 · 2014-11-20 00:34:18Z

I assume you can use C++11.

Your parameter passing is a bit off. There are a lot of options, these are the most common ones:
- const &T, meaning the function should use the objects as it is or make a copy.
- &&T or unique_ptr<T> (or less commonly just the value), meaning the function is given an object and can do whatever it wants with it, including taking ownership, modifying and throwing it away.
DirectedGraphNode(const std::string name) takes name by const value, which creates a copy of the parameter passed which then cannot be modified. In the implementation you then make another copy. The canonical way is to pass const std::string &name. This is not just crazy C++ efficiency addiction, it is about self documenting code. The meanings above are well understood whereas your version has people wondering how to use that strange looking code correctly.

Now, if you do want to get into crazy C++ efficiency addiction you can provide an additional overload DirectedGraphNode(std::string &&name) : m_name(std::move(name)){}. This provides the option to hand over an existing string without copying it. Not that this will give you much efficiency, but sometimes this matters. You may be thinking about passing string &name, because that eliminates the copy too, just like you did in add_child, has_child and remove_child. The problem with string &name is that it is shared with other code and changing name may have funny side effects. With string &&name you get your personal string that will not be used outside this function anymore because it is about to be destroyed, meaning you do not need to worry about other code.

You can compare strings using ==. Instead of

bool DirectedGraphNode::operator ==(const DirectedGraphNode& other) const {
    return this->m_name.compare(other.m_name) == 0;
}

you can write

bool DirectedGraphNode::operator ==(const DirectedGraphNode& other) const {
    return m_name == other.m_name;
}

I was not aware std::string has a member function compare. You may have been thinking about C's "never compare strings using ==". That is good advice for char *, but not necessary for std::string.

Avoid using naked new. Manually managing memory is difficult, boring and error prone. C++ gives you the tools to handle that whole class of problems automatically and efficiently and the cases where you need to intervene are rare.
```
vector<DirectedGraphNode*>* construct_path(...) {
    vector<DirectedGraphNode*>* p_path = new vector<DirectedGraphNode*>;
    ...
    return p_path;
}
```
If you just call construct_path(...); you already have a memory leak. It is difficult to know that you have to call delete on that pointer. Fortunately the solution is really easy:
```
vector<DirectedGraphNode*> construct_path(...) {
    vector<DirectedGraphNode*> p_path;
    ...
    return p_path;
}
```
No more pointers, no memory leaks, more performance and less code. If you must have pointers because you need polymorphic objects use a unique_ptr. It does what it says, it conceptually is the only pointer that points to that object, so if you have it you are the owner and if you throw it away the object disappears too. Obviously you cannot copy a unique_ptr, that would make it not unique anymore, this can be a problem. If you need to share values you can use shared_ptr, the last shared_ptr cleans up automatically. But those are already workarounds for special problems, stick to values as long as possible.
I did not check in detail, but you can most likely change vector<DirectedGraphNode*> to vector<DirectedGraphNode> and greatly simplify the code. Same for the other containers.
Prefer references over pointers. References unlike pointers always point to valid objects (unless you screwed up badly) and are easier to handle since you do not need to check for nullptr and can use regular syntax.
```
T construct_path(unordered_map<DirectedGraphNode*, DirectedGraphNode* > *p_parents_f){
    u = (*p_parents_f)[u];
}
```
becomes more readable and easier to reason about:
```
T construct_path(unordered_map<DirectedGraphNode*, DirectedGraphNode* > &p_parents_f){
    u = p_parents_f[u];
}
```
Obviously sometimes objects are optional and you need pointers to be able to express that, but don't make things unnecessarily complicated.
The destructor of PathFinder is not virtual. If you inherit from it, let a base pointer point to a derived object and then delete the base pointer, the destructor of the derived class will not run making PathFinder not suitable as a base class. This will do it:
```
class PathFinder{
    virtual ~PathFinder() = default;
};
```
Use name aliases for flexibility. At some point you may notice that an unordered_set is not a very good data structure to keep your DirectedGraphNodes in. A (sorted) vector<DirectedGraphNode> will most likely be much faster and use much less memory. If you wanted to switch you would have to change a lot of code. Instead you can used a name alias and auto to skip naming the type.
```
class DirectedGraphNode {
public:
    using Container = std::unordered_set<DirectedGraphNode>;
    Container m_in;
    Container m_out;
    typename Container::const_iterator begin();
};

...

auto start = myDirectedGraphNode.begin();
```
Your IDE will probably tell you what type start is on mouseover, but ideally you don't actually care. It is some iterator type for some container, the rest is an unimportant implementation detail.
The line DirectedGraphNode* u = const_cast<DirectedGraphNode*>(touch); is weird since touch is already a DirectedGraphNode*, making the cast useless. auto u = touch; would do the same thing.
Some names could be improved. touch and u don't really tell me anything. I would expect construct_path to take a const Container &graph, a const DirectedGraphNode &start and a const DirectedGraphNode &end. Your code probably does basically that, but it is hard to see.

A few hints can make the difference between enjoying solving tricky problems in C++ and cursing a flood of segfaults, so feel free to show some improved code later and forgive the late reply.

Thank you for your reply! I will edit the code to reflect the suggested improvements shortly, yet I have to comment that, for instance, in construct_path I have used an "algorithmic idiom", i.e., I do not really need to ask for entire graph or the start node; a parent map and the last node of the path is everything we need to construct a shortest path. — coderodde, Nov 22 '14 at 12:08
@coderodde Be careful with editing the code. See What you may and may not do after receiving answers first. — nwp, Nov 22 '14 at 14:51

Quill · Answer 3 · 2015-08-10 08:33:47Z

Your code is quite good, but since you're a beginner like me, I have some advice that helps a lot in 2D-3D games.

Try to use smart pointers, especially when you're dealing with tree-like data structures, like graph-node or some time it scene-node. If you want to make the memory management by yourself in tree data structure, make sure you have memory leak detection. Believe me, no matter how careful you are, some will behave unexpectedly throughout your code, risk will rise with tree data structure in particular.
Try to make only needed member functions in classes, unless you make a library.
Always make the code as simple as possible.

asked	2 years ago
viewed	544 times
active	1 year ago

current community

your communities

more stack exchange communities

Finding shortest paths in directed graphs

3 Answers 3

In all classes:

directed_graph_node.cpp:

path_finder.h:

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ algorithm pathfinding breadth-first-search framework or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Finding shortest paths in directed graphs

3 Answers 3

In all classes:

directed_graph_node.cpp:

path_finder.h:

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ algorithm pathfinding breadth-first-search framework or ask your own question.

Related

Hot Network Questions