Finding shortest paths in directed graphs

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 
#include 
#include 

/*******************************************************************************
* 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::const_iterator begin();
    std::unordered_set::const_iterator end();

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

    friend std::ostream& operator::const_iterator begin();
        std::unordered_set::const_iterator end();

    private:
        const DirectedGraphNode* mp_owner;
    };

private:
    std::string m_name;
    std::unordered_set m_in;
    std::unordered_set m_out;
};

#endif  // DIRECTED_GRAPH_NODE_H

directed_graph_node.cpp:

```
#include
#include
#include

#include "directed_graph_node.h"

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

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::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;
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*. 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.

StackExchange Code Review Q#70172, answer score: 4