/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_NAUTY_READER_H

#define LEMON_NAUTY_READER_H

#include <vector>

#include <iostream>

#include <string>

/// \ingroup io_group

///

/// @defgroup nauty_group NAUTY format

///

/// \brief Read \e Nauty format

///

/// Tool to read graphs from \e Nauty format data

/// \ingroup nauty_group

/// \file

/// \brief Nauty file reader.

namespace lemon {

  /// \ingroup nauty_group

  ///

  /// \brief Nauty file reader

  ///

  /// The \e geng program is in the \e gtools suite of the nauty

  /// package. This tool can generate all non-isomorphic undirected

  /// graphs with given node number from several classes (for example,

  /// general, connected, biconnected, triangle-free, 4-cycle-free,

  /// bipartite and graphs with given edge number and degree

  /// constraints). This function reads a \e nauty \e graph6 \e format

  /// line from the given stream and builds it in the given graph.

  ///

  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/

  ///

  /// For example, the number of all non-isomorphic connected graphs

  /// can be computed with next code:

  ///\code

  /// int num = 0;

  /// SmartUGraph ugraph;

  /// while(readNauty(std::cin, ugraph)) {

  ///   PlanarityChecking<SmartUGraph> pc(ugraph);

  ///   if (pc.run()) ++num;

  /// }

  /// std::cout << "Number of planar graphs: " << num << std::endl;

  ///\endcode

  ///

  /// The nauty files are quite huge, therefore instead of the direct

  /// file generation the pipelining is recommended. The execution of

  /// this program:

  ///\code 

  /// ./geng -c 10 | ./num_of_pg 

  ///\endcode

  template <typename UGraph>

  std::istream& readNauty(std::istream& is, UGraph& ugraph) {

    ugraph.clear();

    std::string line;

    if (getline(is, line)) {

      int index = 0;

      int n;

      if (line[index] == '>') {

	index += 10; 

      }

      char c = line[index++]; c -= 63;

      if (c != 63) {

	n = int(c);

      } else {

	c = line[index++]; c -= 63;

	n = (int(c) << 12);

	c = line[index++]; c -= 63;

	n |= (int(c) << 6);

	c = line[index++]; c -= 63;

	n |= int(c);      

      }

      std::vector<typename UGraph::Node> nodes;

      for (int i = 0; i < n; ++i) {

	nodes.push_back(ugraph.addNode());

      }

      int bit = -1;

      for (int j = 0; j < n; ++j) {

	for (int i = 0; i < j; ++i) {

	  if (bit == -1) {

	    c = line[index++]; c -= 63;

	    bit = 5;

	  }

	  bool b = (c & (1 << (bit--))) != 0;

	  if (b) {

	    ugraph.addEdge(nodes[i], nodes[j]);

	  }

	}

      }

    }

    return is;

  }

}

#endif