Generic Graph Library Part 2 : Algorithms

(This is a follow on to this question).

Having given an implementation for some of the graph structures, here is a portion of the algorithms that are defined to work over them:


graph_degree.hpp

```
/*! \file graph_degree.hpp
* \brief Algorithms relating to node degree.
*
* Defines core algorithms to investigate indegree and
* outdegrees concerning a given graph. This includes finding minimum,
* maximum, average, and the distribution over a whole graph. It also has
* algorithms specifically for finding disonnected nodes (defined as nodes
* with 0 indegree, that is, inaccessible nodes), and sink nodes (defined as
* nodes with 0 outdegree, that is, nodes one cannot leave).
*
* \addtogroup graph_algorithm
* @{
*/

#ifndef GRAPH_DEGREE_SGL_HPP_
#define GRAPH_DEGREE_SGL_HPP_

#include
#include
#include
#include
#include

#include "boost/optional.hpp"

namespace simplegl
{
namespace graph
{

namespace
{

//Since max and min outdegree differ only by the comparator they use,
//and indegree and outdegree differ only by functon call,
//this is the core functionality abstracted out.
template
boost::optional
>
find_degree(const Graph& g, Compare comparator, Selector degree_type)
{
using node_type = typename Graph::node_type;
using optional_t =
boost::optional
>;

if(g.empty()) {
return optional_t();
}

auto t = g.begin()->first;
auto current = degree_type(t);
auto degree = current;

auto begin = g.begin();
std::advance(begin, 1);

for(auto it = begin; it != g.end(); ++it) {
current = degree_type(it->first);
if(comparator(current, degree)) {
degree = current;
t = it->first;
}
}

return optional_t(std::make_pair(t, degree));
}

template
using optional_t =
boost::optional
>;

template
optional_t find_outdegree(const Graph& g, Compare comparator)
{
using node_type = typename Graph::node_type;
auto select_type

There are several places where you could improve the readability of your code:

-
First of all, you also use iterator-based for loops while you could use range-based for loop instead. Consider this function:

template 
double average_indegree(const Graph& g)
{
    double start = 0;
    typename Graph::size_type total_nodes = 0;

    for(auto it = g.begin(); it != g.end(); ++it) {
        start += g.indegree(it->first);
        ++total_nodes;
    }

    return start/total_nodes;
}

With a range-based for loop, it becomes:

template 
double average_indegree(const Graph& g)
{
    double start = 0;
    typename Graph::size_type total_nodes = 0;

    for(auto& elem: g) {
        start += g.indegree(elem.first);
        ++total_nodes;
    }

    return start/total_nodes;
}

-
You can simplify some return statements thanks to list initialization by not typing the return type a second time. You can rewrite find_degree this way:

template 
boost::optional
>
find_degree(const Graph& g, Compare comparator, Selector degree_type)
{
    using node_type = typename Graph::node_type;

    if(g.empty()) { 
        return {};
    }

    auto t = g.begin()->first;
    auto current = degree_type(t);
    auto degree = current;

    auto begin = g.begin();
    std::advance(begin, 1);

    for(auto it = begin; it != g.end(); ++it) {
        current = degree_type(it->first);
        if(comparator(current, degree)) {
            degree = current;
            t = it->first;
        }
    }

    return { std::make_pair(t, degree) };
}

-
Instead of writing = 0 to zero-initialize an "unknown" type, you can use the new syntax for zero initialization (4th syntax in the given link):

template 
double average_indegree(const Graph& g)
{
    double start = 0.0;
    typename Graph::size_type total_nodes{};

    for(auto& elem: g) {
        start += g.indegree(elem.first);
        ++total_nodes;
    }

    return start/total_nodes;
}

You can also give more power to the user:

-
In average_indegree, you fixed the return type to double. You cuold have your function take a ReturnType template parameter defaulted to double instead:

template 
ReturnType average_indegree(const Graph& g)
{
    ReturnType start{};
    typename Graph::size_type total_nodes{};

    for(auto& elem: g) {
        start += g.indegree(elem.first);
        ++total_nodes;
    }

    return start/total_nodes;
}

Note that if you choose an int type smaller than Graph::size_type, the result type may be too small to contain the actual result. You could change the return type to typename std::common_type::type to ensure that a big enough return type will be picked.

I still have some remarks about the names of your functions:

• I am not very fond of the function begin to take the first element of a collection. begin is already widely used in the standard library to take an iterator to the first element. While the function in itself may be fine, I would change its name to first or something akin. That would also prevent potential name clashes with std::begin if somebody likes to use some bad old using namespace in their code.

StackExchange Code Review Q#55421, answer score: 4