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

// 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_CREATE_CONDENSATION_GRAPH_HPP

#define BOOST_CREATE_CONDENSATION_GRAPH_HPP

#include <boost/graph/graph_traits.hpp>

#include <boost/property_map.hpp>

namespace boost {

  template <typename Graph, typename ComponentLists, 

    typename ComponentNumberMap,

    typename CondensationGraph, typename EdgeMultiplicityMap>

  void create_condensation_graph(const Graph& g, 

                                 const ComponentLists& components,

                                 ComponentNumberMap component_number,

                                 CondensationGraph& cg,

                                 EdgeMultiplicityMap edge_mult_map)

  {

    typedef typename graph_traits<Graph>::vertex_descriptor vertex;

    typedef typename graph_traits<Graph>::vertices_size_type size_type;

    typedef typename graph_traits<CondensationGraph>::vertex_descriptor 

      cg_vertex;

    std::vector<cg_vertex> to_cg_vertex(components.size());

    for (size_type s = 0; s < components.size(); ++s)

      to_cg_vertex[s] = add_vertex(cg);

    for (size_type si = 0; si < components.size(); ++si) {

      cg_vertex s = to_cg_vertex[si];

      std::vector<cg_vertex> adj;

      for (size_type i = 0; i < components[si].size(); ++i) {

        vertex u = components[s][i];

        typename graph_traits<Graph>::adjacency_iterator v, v_end;

        for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {

          cg_vertex t = to_cg_vertex[component_number[*v]];

          if (s != t) // Avoid loops in the condensation graph

            adj.push_back(t);

        }

      }

      std::sort(adj.begin(), adj.end());

      if (! adj.empty()) {

        size_type i = 0;

        cg_vertex t = adj[i];

        typename graph_traits<CondensationGraph>::edge_descriptor e;

        bool inserted;

        tie(e, inserted) = add_edge(s, t, cg);

        put(edge_mult_map, e, 1);

        ++i;

        while (i < adj.size()) {

          if (adj[i] == t)

            put(edge_mult_map, e, get(edge_mult_map, e) + 1);

          else {

            t = adj[i];

            tie(e, inserted) = add_edge(s, t, cg);

            put(edge_mult_map, e, 1);

          }

          ++i;

        }

      }

    }

  }

  template <typename Graph, typename ComponentLists, 

    typename ComponentNumberMap, typename CondensationGraph>

  void create_condensation_graph(const Graph& g, 

                                 const ComponentLists& components,

                                 ComponentNumberMap component_number,

                                 CondensationGraph& cg)

  {

    create_condensation_graph(g, components, component_number, cg, 

                              dummy_property_map());

  }

} // namespace boost

#endif // BOOST_CREATE_CONDENSATION_GRAPH_HPP