#include <iostream>
#include <queue>
#include <unordered_map>

#include <origin/graph/directed_graph.hpp>
#include <origin/graph/undirected_graph.hpp>
#include <origin/graph/algorithm/breadth_first_search.hpp>

using namespace std;

int main() {
  using namespace origin;

  {
    typedef directed_graph<char, int> Graph;
    typedef Graph::vertex_descriptor Vertex;

    Graph g;
    size_t const N = 5;
    Vertex verts[N];
    for(size_t i = 0; i < N; ++i)
      verts[i] = g.add_vertex('a' + i);
    for(size_t i = 1; i < N; ++i)
      g.add_edge(verts[0], verts[i], i);

    assert(breadth_first_find(g, verts[0], 'c') == verts[2]);
    assert(breadth_first_find(g, verts[0], '1') == Vertex());

    breadth_first_tree(
      g, verts[0],
      [](Graph const& g, Vertex s, Vertex t) { cout << g[s] << "--" << g[t] << "\n"; });
  }

  {
    typedef undirected_graph<char, int> Graph;
    typedef Graph::vertex_descriptor Vertex;

    Graph g;
    size_t const N = 5;
    Vertex verts[N];
    for(size_t i = 0; i < N; ++i)
      verts[i] = g.add_vertex('a' + i);
    for(size_t i = 1; i < N; ++i)
      g.add_edge(verts[0], verts[i], i);

    assert(breadth_first_find(g, verts[0], 'c') == verts[2]);
  }
}