// Copyright (c) 2008-2010 Kent State University
//
// This file is distributed under the MIT License. See the accompanying file
// LICENSE.txt or http://www.opensource.org/licenses/mit-license.php for terms
// and conditions.

#include <cassert>
#include <iostream>

#include <origin/graph/adjacency_matrix.hpp>
#include <origin/graph/generator/tree.hpp>

using namespace std;
using namespace origin;

// Make sure that the graph exhibits the m-ary tree structure induced by the
// induce_k_ary_tree_graph generator.
template<typename Graph, typename Label>
void test_k_ary_tree(Graph const& g, Label label) {
  typedef typename Graph::vertex_handle Vertex;
  typedef typename Graph::edge_handle Edge;
}

// For debug purposes we include a print function for visual inspection.
template<typename Graph>
void print_k_ary_tree(Graph const& g) {
  typedef typename Graph::vertex_handle Vertex;
  typedef typename Graph::edge_handle Edge;

  for(auto i = g.vertices().begin(); i != g.vertices().end(); ++i) {
    for(auto out_edge = g.incident_edges(*i).begin();
        out_edge != g.incident_edges(*i).end(); ++out_edge) {
      std::cout << '(' << *i << ", " << *out_edge << ")\n";
    }
  }
}

int main() {
  typedef undirected_adjacency_matrix<char, int> graph_type;

  graph_type g(7);
  assert(g.order() == 7);
  assert(g.empty());

  // Induce a binary tree on g.
  auto label = [&g](size_t n) { return g.vertex(n); };
  induce_k_ary_tree_graph(g, label, 2);
  print_k_ary_tree(g);

  return 0;
}