directed_graph.h

Go to the documentation of this file.

#ifndef META_DIRECTED_GRAPH_H_
#define META_DIRECTED_GRAPH_H_

#include <stdexcept>
#include <vector>
#include <unordered_set>
#include <cstddef>
#include "meta.h"
#include "util/optional.h"
#include "graph/graph.h"
#include "graph/default_node.h"
#include "graph/default_edge.h"

namespace meta
{
namespace graph
{
template <class Node = default_node, class Edge = default_edge>
class directed_graph : public graph<Node, Edge>
{
  public:
    using adjacency_list = typename graph<Node, Edge>::adjacency_list;
    using vec_t = std::vector<std::pair<Node, adjacency_list>>;
    using graph<Node, Edge>::nodes_;
    using graph<Node, Edge>::num_edges_;
    using graph<Node, Edge>::size;
    using graph<Node, Edge>::add_edge;

    const adjacency_list& adjacent(node_id id) const;

    const std::vector<node_id>& incoming(node_id id) const;

    virtual node_id insert(Node node) override;

    virtual void add_edge(Edge edge, node_id source, node_id dest) override;

    #include "node_iterator.h"
    typedef node_iterator<typename vec_t::iterator> iterator;
    typedef node_iterator<typename vec_t::const_iterator> const_iterator;

    iterator begin() { return {nodes_.begin()}; }

    const_iterator begin() const { return {nodes_.cbegin()}; }

    iterator end() { return {nodes_.end()}; }

    const_iterator end() const { return {nodes_.cend()}; }

    #include "edge_iterator.h"
    typedef edge_iterator<typename vec_t::iterator> e_iterator;
    typedef edge_iterator<typename vec_t::const_iterator> const_e_iterator;

    e_iterator edges_begin() { return {this, nodes_.begin(), nodes_.end()}; }

    const_e_iterator edges_begin() const
    {
        return {this, nodes_.cbegin(), nodes_.cend()};
    }

    e_iterator edges_end() { return {this, nodes_.end(), nodes_.end()}; }

    const_e_iterator edges_end() const
    {
        return {this, nodes_.cend(), nodes_.cend()};
    }

  private:
    std::vector<std::vector<node_id>> incoming_;
};

class directed_graph_exception : public std::runtime_error
{
  public:
    using std::runtime_error::runtime_error;
};
}
}

#include "graph/directed_graph.tcc"
#endif