//=======================================================================

// Copyright 2002 Indiana University.

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

//

// Distributed under the Boost Software License, Version 1.0. (See

// accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//=======================================================================

#ifndef BOOST_GRAPH_TEST_HPP

#define BOOST_GRAPH_TEST_HPP

#include <vector>

#include <boost/test/minimal.hpp>

#include <boost/graph/filtered_graph.hpp>

#include <boost/graph/iteration_macros.hpp>

#include <boost/graph/isomorphism.hpp>

#include <boost/graph/copy.hpp>

#include <boost/graph/graph_utility.hpp> // for connects

// UNDER CONSTRUCTION 

namespace boost {

  template <typename Graph>

  struct graph_test

  {

    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

    typedef typename graph_traits<Graph>::vertices_size_type v_size_t;

    typedef typename graph_traits<Graph>::degree_size_type deg_size_t;

    typedef typename graph_traits<Graph>::edges_size_type e_size_t;

    typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;

    typedef typename property_map<Graph, vertex_index_t>::type index_map_t;

    typedef iterator_property_map<typename std::vector<vertex_t>::iterator,

      index_map_t,vertex_t,vertex_t&> IsoMap;

    struct ignore_vertex {

      ignore_vertex() { }

      ignore_vertex(vertex_t v) : v(v) { }

      bool operator()(vertex_t x) const { return x != v; }

      vertex_t v;

    };

    struct ignore_edge {

      ignore_edge() { }

      ignore_edge(edge_t e) : e(e) { }

      bool operator()(edge_t x) const { return x != e; }

      edge_t e;

    };

    struct ignore_edges {

      ignore_edges(vertex_t s, vertex_t t, const Graph& g) 

        : s(s), t(t), g(g) { }

      bool operator()(edge_t x) const { 

        return !(source(x, g) == s && target(x, g) == t);

      }

      vertex_t s; vertex_t t; const Graph& g;

    };

    //=========================================================================

    // Traversal Operations

    void test_incidence_graph

       (const std::vector<vertex_t>& vertex_set,

        const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,

        const Graph& g)

    {

      typedef typename std::vector<vertex_t>::const_iterator vertex_iter;

      typedef typename std::vector< std::pair<vertex_t, vertex_t> >

        ::const_iterator edge_iter;

      typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;

      for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {

        vertex_t u = *ui;

        std::vector<vertex_t> adj;

        for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)

          if (e->first == u)

            adj.push_back(e->second);

        std::pair<out_edge_iter, out_edge_iter> p = out_edges(u, g);

        BOOST_CHECK(out_degree(u, g) == adj.size());

        BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))

                   == out_degree(u, g));

        for (; p.first != p.second; ++p.first) {

          edge_t e = *p.first;

          BOOST_CHECK(source(e, g) == u);

          BOOST_CHECK(contains(adj, target(e, g)) == true);

        }

      }

    }

    void test_bidirectional_graph

      (const std::vector<vertex_t>& vertex_set,

       const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,

       const Graph& g)

    {

      typedef typename std::vector<vertex_t>::const_iterator vertex_iter;

      typedef typename std::vector< std::pair<vertex_t, vertex_t> >

        ::const_iterator edge_iter;

      typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iter;

      for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) {

        vertex_t v = *vi;

        std::vector<vertex_t> inv_adj;

        for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)

          if (e->second == v)

            inv_adj.push_back(e->first);

        std::pair<in_edge_iter, in_edge_iter> p = in_edges(v, g);

        BOOST_CHECK(in_degree(v, g) == inv_adj.size());

        BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))

                   == in_degree(v, g));

        for (; p.first != p.second; ++p.first) {

          edge_t e = *p.first;

          BOOST_CHECK(target(e, g) == v);

          BOOST_CHECK(contains(inv_adj, source(e, g)) == true);

        }

      }

    }

    void test_adjacency_graph

      (const std::vector<vertex_t>& vertex_set,

       const std::vector< std::pair<vertex_t,vertex_t> >& edge_set,

       const Graph& g)

    {

      typedef typename std::vector<vertex_t>::const_iterator vertex_iter;

      typedef typename std::vector<std::pair<vertex_t,vertex_t> >

        ::const_iterator edge_iter;

      typedef typename graph_traits<Graph>::adjacency_iterator adj_iter;

      for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {

        vertex_t u = *ui;

        std::vector<vertex_t> adj;

        for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)

          if (e->first == u)

            adj.push_back(e->second);

        std::pair<adj_iter, adj_iter> p = adjacent_vertices(u, g);

        BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) == adj.size());

        for (; p.first != p.second; ++p.first) {

          vertex_t v = *p.first;

          BOOST_CHECK(contains(adj, v) == true);

        }

      }

    }      

    void test_vertex_list_graph

      (const std::vector<vertex_t>& vertex_set, const Graph& g)

    {

      typedef typename graph_traits<Graph>::vertex_iterator v_iter;

      std::pair<v_iter, v_iter> p = vertices(g);

      BOOST_CHECK(num_vertices(g) == vertex_set.size());

      v_size_t n = std::distance(p.first, p.second);

      BOOST_CHECK(n == num_vertices(g));

      for (; p.first != p.second; ++p.first) {

        vertex_t v = *p.first;

        BOOST_CHECK(contains(vertex_set, v) == true);

      }

    }

    void test_edge_list_graph

      (const std::vector<vertex_t>& vertex_set, 

       const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 

       const Graph& g)

    {

      typedef typename graph_traits<Graph>::edge_iterator e_iter;

      std::pair<e_iter, e_iter> p = edges(g);

      BOOST_CHECK(num_edges(g) == edge_set.size());

      e_size_t m = std::distance(p.first, p.second);

      BOOST_CHECK(m == num_edges(g));

      for (; p.first != p.second; ++p.first) {

        edge_t e = *p.first;

        BOOST_CHECK(any_if(edge_set, connects(source(e, g), target(e, g), g)));

        BOOST_CHECK(contains(vertex_set, source(e, g)) == true);

        BOOST_CHECK(contains(vertex_set, target(e, g)) == true);

      }

    }

    void test_adjacency_matrix

      (const std::vector<vertex_t>& vertex_set, 

       const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 

       const Graph& g)

    {

      std::pair<edge_t, bool> p;

      for (typename std::vector<std::pair<vertex_t, vertex_t> >

             ::const_iterator i = edge_set.begin();

           i != edge_set.end(); ++i) {

        p = edge(i->first, i->second, g);

        BOOST_CHECK(p.second == true);

        BOOST_CHECK(source(p.first, g) == i->first);

        BOOST_CHECK(target(p.first, g) == i->second);

      }

      typename std::vector<vertex_t>::const_iterator j, k;

      for (j = vertex_set.begin(); j != vertex_set.end(); ++j)

        for (k = vertex_set.begin(); k != vertex_set.end(); ++k) {

          p = edge(*j, *k, g);

          if (p.second == true)

            BOOST_CHECK(any_if(edge_set, 

              connects(source(p.first, g), target(p.first, g), g)) == true);

        }

    }

    //=========================================================================

    // Mutating Operations

    void test_add_vertex(Graph& g)

    {

      Graph cpy;

      std::vector<vertex_t> iso_vec(num_vertices(g));

      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));

      copy_graph(g, cpy, orig_to_copy(iso_map));

      assert((verify_isomorphism(g, cpy, iso_map)));

      vertex_t v = add_vertex(g);

      BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1);

      BOOST_CHECK(out_degree(v, g) == 0);

      // Make sure the rest of the graph stayed the same

      BOOST_CHECK((verify_isomorphism

                  (make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy,

                   iso_map)));

    }

    void test_add_edge(vertex_t u, vertex_t v, Graph& g)

    {

      Graph cpy;

      std::vector<vertex_t> iso_vec(num_vertices(g));

      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));

      copy_graph(g, cpy, orig_to_copy(iso_map));

      bool parallel_edge_exists = contains(adjacent_vertices(u, g), v);

      std::pair<edge_t, bool> p = add_edge(u, v, g);

      edge_t e = p.first;

      bool added = p.second;

      if (is_undirected(g) && u == v) // self edge

        BOOST_CHECK(added == false);

      else if (parallel_edge_exists)

        BOOST_CHECK(allows_parallel_edges(g) && added == true

                   || !allows_parallel_edges(g) && added == false);

      else

        BOOST_CHECK(added == true);

      if (p.second == true) { // edge added

        BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1);

        BOOST_CHECK(contains(out_edges(u, g), e) == true);

        BOOST_CHECK((verify_isomorphism

                    (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map)));

      }

      else { // edge not added

        if (! (is_undirected(g) && u == v)) {

          // e should be a parallel edge

          BOOST_CHECK(source(e, g) == u);

          BOOST_CHECK(target(e, g) == v);

        }

        // The graph should not be changed.

        BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));

      }

    } // test_add_edge()

    void test_remove_edge(vertex_t u, vertex_t v, Graph& g)

    {

      Graph cpy;

      std::vector<vertex_t> iso_vec(num_vertices(g));

      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));

      copy_graph(g, cpy, orig_to_copy(iso_map));

      deg_size_t occurances = count(adjacent_vertices(u, g), v);

      remove_edge(u, v, g);

      BOOST_CHECK(num_edges(g) + occurances == num_edges(cpy));

      BOOST_CHECK((verify_isomorphism

                  (g, make_filtered_graph(cpy, ignore_edges(u,v,cpy)),

                   iso_map)));

    }

    void test_remove_edge(edge_t e, Graph& g)

    {

      Graph cpy;

      std::vector<vertex_t> iso_vec(num_vertices(g));

      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));

      copy_graph(g, cpy, orig_to_copy(iso_map));

      vertex_t u = source(e, g), v = target(e, g);

      deg_size_t occurances = count(adjacent_vertices(u, g), v);

      remove_edge(e, g);

      BOOST_CHECK(num_edges(g) + 1 == num_edges(cpy));

      BOOST_CHECK(count(adjacent_vertices(u, g), v) + 1 == occurances);

      BOOST_CHECK((verify_isomorphism

                  (g, make_filtered_graph(cpy, ignore_edge(e)),

                   iso_map)));

    }

    void test_clear_vertex(vertex_t v, Graph& g)

    {

      Graph cpy;

      std::vector<vertex_t> iso_vec(num_vertices(g));

      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));

      copy_graph(g, cpy, orig_to_copy(iso_map));

      clear_vertex(v, g);

      BOOST_CHECK(out_degree(v, g) == 0);

      BOOST_CHECK(num_vertices(g) == num_vertices(cpy));

      BOOST_CHECK((verify_isomorphism

                  (g, make_filtered_graph(cpy, keep_all(), ignore_vertex(v)),

                   iso_map)));

    }

    //=========================================================================

    // Property Map

    template <typename PropVal, typename PropertyTag>

    void test_readable_vertex_property_graph

      (const std::vector<PropVal>& vertex_prop, PropertyTag, const Graph& g)

    {

      typedef typename property_map<Graph, PropertyTag>::const_type const_Map;

      const_Map pmap = get(PropertyTag(), g);

      typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();

  for (typename boost::graph_traits<Graph>::vertex_iterator 

           bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;

       bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)

    for (typename boost::graph_traits<Graph>::vertex_descriptor v;

         bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;

         ++bgl_first_9) {

      //BGL_FORALL_VERTICES_T(v, g, Graph) {

        typename property_traits<const_Map>::value_type 

          pval1 = get(pmap, v), pval2 = get(PropertyTag(), g, v);

        BOOST_CHECK(pval1 == pval2);

        BOOST_CHECK(pval1 == *i++);

      }

    }

    template <typename PropVal, typename PropertyTag>

    void test_vertex_property_graph

      (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g)

    {

      typedef typename property_map<Graph, PropertyTag>::type PMap;

      PMap pmap = get(PropertyTag(), g);

      typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();

  for (typename boost::graph_traits<Graph>::vertex_iterator 

           bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;

       bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)

    for (typename boost::graph_traits<Graph>::vertex_descriptor v;

         bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;

         ++bgl_first_9)

      //      BGL_FORALL_VERTICES_T(v, g, Graph)

        put(pmap, v, *i++);

      test_readable_vertex_property_graph(vertex_prop, tag, g);

      BGL_FORALL_VERTICES_T(v, g, Graph)

        put(pmap, v, vertex_prop[0]);

      typename std::vector<PropVal>::const_iterator j = vertex_prop.begin();

      BGL_FORALL_VERTICES_T(v, g, Graph)

        put(PropertyTag(), g, v, *j++);

      test_readable_vertex_property_graph(vertex_prop, tag, g);      

    }

  };

} // namespace boost

#include <boost/graph/iteration_macros_undef.hpp>

#endif // BOOST_GRAPH_TEST_HPP