/* Copyright (c) 1997-2004
   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_MAX_CLIQUES_H
#define _POLYMAKE_GRAPH_MAX_CLIQUES_H "$Project: polymake $$Id: max_cliques.h 4714 2004-06-22 16:23:15Z gawrilow $"

#include <Graph.h>
#include <PowerSet.h>

namespace polymake {
namespace graph {

   template <typename Graph>
   void max_cliques_recursive(const Set<int>& V, const Graph& G,
			      const Set<int>& C, PowerSet<int>& max_C)
   {
      if (V.empty())        // max clique found
	 max_C += C;
    
      else                  // continue search
	 for (Entire< Set<int> >::const_iterator v=entire(V); !v.at_end(); ++v) {
	    const Set<int> new_V = V*G.neighbors(*v);
	    max_cliques_recursive(new_V, G, C+*v, max_C);

	    // pruning the search tree
	    if (new_V.size()+1 == V.size())
	       break;
	 }
   }

   /// Compute all inclusion maximal cliques of an undirected graph.
   template <typename Graph>
   PowerSet<int> max_cliques(const Graph& G)
   {
      PowerSet<int> max_C;
      Set<int> C;

      max_cliques_recursive(sequence(0,G.nodes()), G, C, max_C);

      return max_C;
   }
} }

#endif // _POLYMAKE_GRAPH_MAX_CLIQUES_H

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