/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_GRAPH_COMPARE_H
#define _POLYMAKE_GRAPH_COMPARE_H "$Project: polymake $$Id: graph_compare.h 7395 2006-07-20 18:08:16Z gawrilow $"

#include <GenericGraph.h>
#include <GenericIncidenceMatrix.h>
#include <Array.h>
#include <Map.h>
#include <list>

namespace polymake { namespace graph {

class NautyGraph {
   struct impl;
   impl *p_impl;

   int n_autom;
   std::list< Array<int> > autom;

   static impl *alloc_impl(int n_nodes, bool _is_directed);
   void add_edge(int from, int to);
   void partition(int at);
   int* partitions();
   int* labels();
   void finalize(bool gather_automorphisms);

   template <typename Matrix>
   void fill(const GenericIncidenceMatrix<Matrix, pm::True>& M)
   {
      for (typename Entire< Rows< Matrix > >::const_iterator r=entire(rows(M));  !r.at_end();  ++r)
	 for (typename Entire< typename Matrix::row_type >::const_iterator c=entire(*r);  !c.at_end();  ++c)
	    add_edge(r.index(), *c);
   }

public:
   NautyGraph() : p_impl(0) { }

   template <typename Graph>
   explicit NautyGraph(const GenericGraph<Graph>& G, bool gather_automorphisms=false)
      : p_impl(alloc_impl(G.nodes(), G.dir==directed))
   {
      fill(neighborhood_matrix(G));
      finalize(gather_automorphisms);
   }

   // non-symmetrical incidence matrix
   template <typename Matrix>
   explicit NautyGraph(const GenericIncidenceMatrix<Matrix, pm::False>& M, bool gather_automorphisms=false)
      : p_impl(alloc_impl(M.rows()+M.cols(), false))
   {
      int rnode=M.cols();
      partition(rnode);
      for (typename Entire< Rows< Matrix > >::const_iterator r=entire(rows(M));  !r.at_end();  ++r, ++rnode)
	 for (typename Entire< typename Matrix::row_type >::const_iterator c=entire(*r);  !c.at_end();  ++c) {
	    add_edge(rnode, *c);
	    add_edge(*c, rnode);
	 }
      finalize(gather_automorphisms);
   }

   // symmetrical incidence matrix
   template <typename Matrix>
   explicit NautyGraph(const GenericIncidenceMatrix<Matrix, pm::True>& M, bool gather_automorphisms=false)
      : p_impl(alloc_impl(M.rows(), true))
   {
      // there can be ones on the diagonal, which correspond loops in the graph;
      // nauty requires the graph to be declared as directed in this case
      fill(M);
      finalize(gather_automorphisms);
   }

   ~NautyGraph();

   bool operator== (const NautyGraph& g2) const;
   bool operator!= (const NautyGraph& g2) const { return !operator==(g2); }

private:
   static void incr_count(std::pair<int,int>& p)
   {
      ++p.first; ++p.second;
   }
   static int first_index(std::pair<int,int>& p)
   {
      return p.second++;
   }
   static int second_index(std::pair<int,int>& p)
   {
      return (p.second++)-p.first;
   }

public:
   template <typename Graph1, typename Colors1, typename Graph2, typename Colors2>
   static bool prepare_colored(NautyGraph& NG1, const GenericGraph<Graph1>& G1, const Colors1& colors1,
			       NautyGraph& NG2, const GenericGraph<Graph2>& G2, const Colors2& colors2);

   Array<int> find_permutation(const NautyGraph& g2) const;
   std::pair< Array<int>, Array<int> > find_permutations(const NautyGraph& g2, int n_cols) const;

   int n_automorphisms() const { return n_autom; }
   const std::list< Array<int> >& automorphisms() const { return autom; }
};

template <typename Graph1, typename Graph2> inline
bool isomorphic(const GenericGraph<Graph1>& G1, const GenericGraph<Graph2>& G2)
{
   if ((G1.dir==directed) != (G2.dir==directed) || G1.nodes() != G2.nodes())
      return false;
   NautyGraph NG1(G1), NG2(G2);
   return NG1==NG2;
}

template <typename Graph1, typename Colors1, typename Graph2, typename Colors2> inline
bool isomorphic(const GenericGraph<Graph1>& G1, const Colors1& colors1,
		const GenericGraph<Graph2>& G2, const Colors2& colors2)
{
   if ((G1.dir==directed) != (G2.dir==directed) || G1.nodes() != G2.nodes())
      return false;
   NautyGraph NG1, NG2;
   return NautyGraph::prepare_colored(NG1, G1, colors1, NG2, G2, colors2) && NG1==NG2;
}

template <typename Graph1, typename Graph2> inline
Array<int> find_node_permutation(const GenericGraph<Graph1>& G1, const GenericGraph<Graph2>& G2)
{
   if ((G1.dir==directed) != (G2.dir==directed))
      throw pm::no_match("graphs of different kind");
   if (G1.nodes() != G2.nodes())
      throw pm::no_match("graphs of different size");
   NautyGraph NG1(G1), NG2(G2);
   return NG1.find_permutation(NG2);
}

template <typename Graph1, typename Colors1, typename Graph2, typename Colors2> inline
Array<int> find_node_permutation(const GenericGraph<Graph1>& G1, const Colors1& colors1,
				 const GenericGraph<Graph2>& G2, const Colors2& colors2)
{
   if ((G1.dir==directed) != (G2.dir==directed))
      throw pm::no_match("graphs of different kind");
   if (G1.nodes() != G2.nodes())
      throw pm::no_match("graphs of different size");
   NautyGraph NG1, NG2;
   if (NautyGraph::prepare_colored(NG1, G1, colors1, NG2, G2, colors2))
      return NG1.find_permutation(NG2);
   else
      throw pm::no_match("different colors");
}

template <typename Graph> inline
Array< Array<int> > automorphisms(const GenericGraph<Graph>& G)
{
   NautyGraph NG(G, true);
   return Array< Array<int> >(NG.n_automorphisms(), NG.automorphisms().begin());
}

template <typename Matrix1, typename Matrix2, typename sym> inline
bool isomorphic(const GenericIncidenceMatrix<Matrix1,sym>& M1, const GenericIncidenceMatrix<Matrix2,sym>& M2)
{
   if (M1.rows() != M2.rows() || M1.cols() != M2.cols())
      return false;
   NautyGraph NG1(M1), NG2(M2);
   return NG1==NG2;
}

template <typename Matrix1, typename Matrix2> inline
Array<int> find_row_permutation(const GenericIncidenceMatrix<Matrix1,pm::True>& M1, const GenericIncidenceMatrix<Matrix2,pm::True>& M2)
{
   if (M1.rows() != M2.rows())
      throw pm::no_match("matrices of different dimensions");
   NautyGraph NG1(M1), NG2(M2);
   return NG1.find_permutation(NG2);
}

template <typename Matrix1, typename Matrix2> inline
std::pair< Array<int>, Array<int> >
find_row_col_permutation(const GenericIncidenceMatrix<Matrix1,pm::False>& M1, const GenericIncidenceMatrix<Matrix2,pm::False>& M2)
{
   if (M1.rows() != M2.rows() || M1.cols() != M2.cols())
      throw pm::no_match("matrices of different dimensions");
   NautyGraph NG1(M1), NG2(M2);
   return NG1.find_permutations(NG2, M1.cols());
}

template <typename Matrix> inline
Array< Array<int> > automorphisms(const GenericIncidenceMatrix<Matrix,pm::True>& M)
{
   NautyGraph NG(M, true);
   return Array< Array<int> >(NG.n_automorphisms(), NG.automorphisms().begin());
}

template <typename Matrix> inline
Array< Array<int> > row_automorphisms(const GenericIncidenceMatrix<Matrix,pm::False>& M)
{
   NautyGraph NG(M, true);
   Array< Array<int> > result(NG.n_automorphisms());
   std::list< Array<int> >::const_iterator p=NG.automorphisms().begin();
   const int n_rows=M.rows(), n_cols=M.cols();
   sequence rows(n_cols, n_rows);

   for (Entire< Array< Array<int> > >::iterator r=entire(result); !r.at_end(); ++r, ++p)
      r->append(n_rows, translate(select(*p,rows), -n_cols).begin());
   return result;
}

template <typename Matrix> inline
Array< Array<int> > col_automorphisms(const GenericIncidenceMatrix<Matrix,pm::False>& M)
{
   NautyGraph NG(M, true);
   Array< Array<int> > result(NG.n_automorphisms());
   std::list< Array<int> >::const_iterator p=NG.automorphisms().begin();
   const int n_cols=M.cols();
   sequence cols(0, n_cols);

   for (Entire< Array< Array<int> > >::iterator r=entire(result); !r.at_end(); ++r, ++p)
      r->append(n_cols, select(*p,cols).begin());
   return result;
}

template <typename Graph1, typename Colors1, typename Graph2, typename Colors2>
bool NautyGraph::prepare_colored(NautyGraph& NG1, const GenericGraph<Graph1>& G1, const Colors1& colors1,
				 NautyGraph& NG2, const GenericGraph<Graph2>& G2, const Colors2& colors2)
{
   const int n=G1.nodes();
   NG1.p_impl=alloc_impl(n, G1.dir==directed);
   NG2.p_impl=alloc_impl(n, G2.dir==directed);

   typedef Map<typename pm::identical<typename Colors1::value_type, typename Colors2::value_type>::type,
      std::pair<int, int> > color_map_type;
   color_map_type color_map;

   for (typename Entire<Colors1>::const_iterator c=entire(colors1); !c.at_end(); ++c)
      incr_count(color_map[*c]);

   for (typename Entire<Colors2>::const_iterator c=entire(colors2); !c.at_end(); ++c)
      if (--color_map[*c].second < 0)
	 return false;

   int *p1=NG1.partitions(), *l1=NG1.labels(), *l2=NG2.labels();
   int start=0;

   for (typename color_map_type::iterator cm=color_map.begin(); !cm.at_end(); ++cm) {
      const int n_of_this_color=cm->second.first;
      cm->second.second=start;
      std::fill(p1, p1+n_of_this_color-1, 1);  p1+=n_of_this_color; p1[-1]=0;
      start+=n_of_this_color;
   }
   p1=NG1.partitions();
   std::copy(p1, p1+n, NG2.partitions());

   for (typename pm::ensure_features<Colors1, pm::cons<pm::end_sensitive, pm::indexed> >::const_iterator
	   c=ensure(colors1, (pm::cons<pm::end_sensitive, pm::indexed>*)0).begin(); !c.at_end(); ++c)
      l1[first_index(color_map[*c])]=c.index();

   for (typename pm::ensure_features<Colors2, pm::cons<pm::end_sensitive, pm::indexed> >::const_iterator
	   c=ensure(colors2, (pm::cons<pm::end_sensitive, pm::indexed>*)0).begin(); !c.at_end(); ++c)
      l2[second_index(color_map[*c])]=c.index();

   NG1.fill(neighborhood_matrix(G1));  NG1.finalize(false);
   NG2.fill(neighborhood_matrix(G2));  NG2.finalize(false);
   return true;
}

} }

#endif // _POLYMAKE_GRAPH_COMPARE_H

// Local Variables:
// mode:C++
// c-basic-offset:3
// End: