graph

#include <set>
/* using std::set */
#include <map>
/* using std::map */
#include <array>
/* using std::array */
#include <memory>
/* using std::shared_ptr, std::make_shared, std::enable_shared_from_this,
 * std::weak_ptr */
#include <utility>
/* using std::move, std::pair, std::make_pair */
#include <cassert>
/* using assert */
#include <iostream>
/* using std::cout */


namespace graph {

  class vertex;

  struct vertexcmp
  {
    bool operator()(const std::shared_ptr<vertex>& first,
            const std::shared_ptr<vertex>& second) const noexcept;
    bool operator()(const std::weak_ptr<vertex>& first,
            const std::weak_ptr<vertex>& second) const noexcept
    {
      return (*this)(first.lock(), second.lock());
    }
  };

  using vertexset = std::set<std::shared_ptr<vertex>, vertexcmp>;
  using backrefset = std::set<std::weak_ptr<vertex>, vertexcmp>;

  struct vertex: std::enable_shared_from_this<vertex>
  {
    vertexset children;
    backrefset parents;
    const int id;
    vertex(int id) noexcept
      : id(id)
    {}
    vertex(const vertex&) = delete;
    vertex(vertex&&) = default;
    bool add_child(const std::shared_ptr<vertex>& child)
    {
      assert(child);
      if(! children.insert(child).second)
    return false; /* already a child */
      std::weak_ptr<vertex> self(this->shared_from_this());
      bool newparent = child->parents.insert(std::move(self)).second;
      assert(newparent);
      return true;
    }
    bool remove_child(const std::shared_ptr<vertex>& child) noexcept
    {
      assert(child);
      if(! children.erase(child))
    return false;
      std::weak_ptr<vertex> self(this->shared_from_this());
      bool wasparent = child->parents.erase(std::move(self));
      assert(wasparent);
      return true;
    }
  };

  bool vertexcmp::operator()(const std::shared_ptr<vertex>& first,
                 const std::shared_ptr<vertex>& second) const noexcept
  {
    assert(first && second);
    return first->id < second->id;
  }

  using edge = std::pair<int, int>;
  using edgeset = std::set<edge>;

  void walk_graph(const std::shared_ptr<vertex>& node, edgeset& walked) noexcept
  {
    assert(node);
    const vertexset& children = node->children;
    int id = node->id;
    for(const std::shared_ptr<vertex>& child: children) {
      assert(child);
      int childid = child->id;
      bool notvisited = walked.insert(std::make_pair(id, childid)).second;
      if(notvisited) {
    std::cout << id << " -> " << childid << "\n";
    walk_graph(child, walked);
      }
    }
  }

  using vertexmap = std::map<int, std::shared_ptr<vertex> >;

  struct graphset
  {
    vertexmap vertexes;
    std::shared_ptr<vertex>& operator[](int id)
    {
      std::shared_ptr<vertex>& node = vertexes[id];
      if(node)
    assert(node->id == id);
      else
    node = std::make_shared<vertex>(id);
      return node;
    }
    bool add_edge(int from, int to)
    {
      std::shared_ptr<vertex>& parent = (*this)[from];
      std::shared_ptr<vertex>& child = (*this)[to];
      return parent->add_child(child);
    }
  };

  template<std::size_t n>
  using edge_array = std::array<edge, n>;
}

int main()
{
  graph::graphset testgraph;
  static constexpr graph::edge_array<6> edges {
    graph::edge{0, 1},
    graph::edge{0, 4},
    graph::edge{1, 2},
    graph::edge{1, 3},
    graph::edge{1, 4},
    graph::edge{2, 3},
  };
  for(const graph::edge& e: edges)
    testgraph.add_edge(e.first, e.second);
  graph::edgeset walked;
  graph::walk_graph(testgraph[0], walked);
}