deba@2516: /* -*- C++ -*-
deba@2516:  *
deba@2516:  * This file is a part of LEMON, a generic C++ optimization library
deba@2516:  *
alpar@2553:  * Copyright (C) 2003-2008
deba@2516:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2516:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2516:  *
deba@2516:  * Permission to use, modify and distribute this software is granted
deba@2516:  * provided that this copyright notice appears in all copies. For
deba@2516:  * precise terms see the accompanying LICENSE file.
deba@2516:  *
deba@2516:  * This software is provided "AS IS" with no warranty of any kind,
deba@2516:  * express or implied, and with no claim as to its suitability for any
deba@2516:  * purpose.
deba@2516:  *
deba@2516:  */
deba@2516: 
deba@2516: #ifndef LEMON_NAUTY_READER_H
deba@2516: #define LEMON_NAUTY_READER_H
deba@2516: 
deba@2516: #include <vector>
deba@2516: #include <iostream>
deba@2516: #include <string>
deba@2516: 
deba@2516: 
deba@2516: /// \ingroup io_group
deba@2516: ///
deba@2516: /// @defgroup nauty_group NAUTY format
deba@2516: ///
deba@2516: /// \brief Read \e Nauty format
deba@2516: ///
deba@2516: /// Tool to read graphs from \e Nauty format data
deba@2516: 
deba@2516: /// \ingroup nauty_group
deba@2516: /// \file
deba@2516: /// \brief Nauty file reader.
deba@2516: namespace lemon {
deba@2516: 
deba@2516:   /// \ingroup nauty_group
deba@2516:   ///
deba@2516:   /// \brief Nauty file reader
deba@2516:   ///
deba@2516:   /// The \e geng program is in the \e gtools suite of the nauty
deba@2516:   /// package. This tool can generate all non-isomorphic undirected
deba@2516:   /// graphs with given node number from several classes (for example,
deba@2516:   /// general, connected, biconnected, triangle-free, 4-cycle-free,
deba@2516:   /// bipartite and graphs with given edge number and degree
deba@2516:   /// constraints). This function reads a \e nauty \e graph6 \e format
deba@2516:   /// line from the given stream and builds it in the given graph.
deba@2516:   ///
deba@2516:   /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
deba@2516:   ///
deba@2516:   /// For example, the number of all non-isomorphic connected graphs
deba@2516:   /// can be computed with next code:
deba@2516:   ///\code
deba@2516:   /// int num = 0;
deba@2516:   /// SmartUGraph ugraph;
deba@2516:   /// while(readNauty(std::cin, ugraph)) {
deba@2516:   ///   PlanarityChecking<SmartUGraph> pc(ugraph);
deba@2516:   ///   if (pc.run()) ++num;
deba@2516:   /// }
deba@2516:   /// std::cout << "Number of planar graphs: " << num << std::endl;
deba@2516:   ///\endcode
deba@2516:   ///
deba@2516:   /// The nauty files are quite huge, therefore instead of the direct
deba@2516:   /// file generation the pipelining is recommended. The execution of
deba@2516:   /// this program:
deba@2516:   ///\code 
deba@2516:   /// ./geng -c 10 | ./num_of_pg 
deba@2516:   ///\endcode
deba@2516:   template <typename UGraph>
deba@2516:   std::istream& readNauty(std::istream& is, UGraph& ugraph) {
deba@2516:     ugraph.clear();
deba@2516: 
deba@2516:     std::string line;
deba@2516:     if (getline(is, line)) {
deba@2516:       int index = 0;
deba@2516:     
deba@2516:       int n;
deba@2516: 
deba@2516:       if (line[index] == '>') {
deba@2516: 	index += 10; 
deba@2516:       }
deba@2516: 
deba@2516:       char c = line[index++]; c -= 63;
deba@2516:       if (c != 63) {
deba@2516: 	n = int(c);
deba@2516:       } else {
deba@2516: 	c = line[index++]; c -= 63;
deba@2516: 	n = (int(c) << 12);
deba@2516: 	c = line[index++]; c -= 63;
deba@2516: 	n |= (int(c) << 6);
deba@2516: 	c = line[index++]; c -= 63;
deba@2516: 	n |= int(c);      
deba@2516:       }
deba@2516: 
deba@2516:       std::vector<typename UGraph::Node> nodes;
deba@2516:       for (int i = 0; i < n; ++i) {
deba@2516: 	nodes.push_back(ugraph.addNode());
deba@2516:       }
deba@2516: 
deba@2516:       int bit = -1;
deba@2516:       for (int j = 0; j < n; ++j) {
deba@2516: 	for (int i = 0; i < j; ++i) {
deba@2516: 	  if (bit == -1) {
deba@2516: 	    c = line[index++]; c -= 63;
deba@2516: 	    bit = 5;
deba@2516: 	  }
deba@2516: 	  bool b = (c & (1 << (bit--))) != 0;
deba@2516: 
deba@2610: 	  if (b) {
deba@2610: 	    ugraph.addEdge(nodes[i], nodes[j]);
deba@2610: 	  }
deba@2516: 	}
deba@2516:       }
deba@2516:     }
deba@2516:     return is;
deba@2516:   }
deba@2516: }
deba@2516: 
deba@2516: #endif