1.1 --- a/lemon/Makefile.am	Sat Nov 17 21:41:01 2007 +0000
     1.2 +++ b/lemon/Makefile.am	Tue Nov 20 15:06:03 2007 +0000
     1.3 @@ -100,6 +100,7 @@
     1.4  	lemon/mip_glpk.h \
     1.5  	lemon/mip_cplex.h \
     1.6  	lemon/nagamochi_ibaraki.h \
     1.7 +	lemon/nauty_reader.h \
     1.8  	lemon/network_simplex.h \
     1.9  	lemon/path.h \
    1.10  	lemon/path_utils.h \

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/nauty_reader.h	Tue Nov 20 15:06:03 2007 +0000
     2.3 @@ -0,0 +1,120 @@
     2.4 +/* -*- C++ -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library
     2.7 + *
     2.8 + * Copyright (C) 2003-2007
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef LEMON_NAUTY_READER_H
    2.23 +#define LEMON_NAUTY_READER_H
    2.24 +
    2.25 +#include <vector>
    2.26 +#include <iostream>
    2.27 +#include <string>
    2.28 +
    2.29 +
    2.30 +/// \ingroup io_group
    2.31 +///
    2.32 +/// @defgroup nauty_group NAUTY format
    2.33 +///
    2.34 +/// \brief Read \e Nauty format
    2.35 +///
    2.36 +/// Tool to read graphs from \e Nauty format data
    2.37 +
    2.38 +/// \ingroup nauty_group
    2.39 +/// \file
    2.40 +/// \brief Nauty file reader.
    2.41 +namespace lemon {
    2.42 +
    2.43 +  /// \ingroup nauty_group
    2.44 +  ///
    2.45 +  /// \brief Nauty file reader
    2.46 +  ///
    2.47 +  /// The \e geng program is in the \e gtools suite of the nauty
    2.48 +  /// package. This tool can generate all non-isomorphic undirected
    2.49 +  /// graphs with given node number from several classes (for example,
    2.50 +  /// general, connected, biconnected, triangle-free, 4-cycle-free,
    2.51 +  /// bipartite and graphs with given edge number and degree
    2.52 +  /// constraints). This function reads a \e nauty \e graph6 \e format
    2.53 +  /// line from the given stream and builds it in the given graph.
    2.54 +  ///
    2.55 +  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
    2.56 +  ///
    2.57 +  /// For example, the number of all non-isomorphic connected graphs
    2.58 +  /// can be computed with next code:
    2.59 +  ///\code
    2.60 +  /// int num = 0;
    2.61 +  /// SmartUGraph ugraph;
    2.62 +  /// while(readNauty(std::cin, ugraph)) {
    2.63 +  ///   PlanarityChecking<SmartUGraph> pc(ugraph);
    2.64 +  ///   if (pc.run()) ++num;
    2.65 +  /// }
    2.66 +  /// std::cout << "Number of planar graphs: " << num << std::endl;
    2.67 +  ///\endcode
    2.68 +  ///
    2.69 +  /// The nauty files are quite huge, therefore instead of the direct
    2.70 +  /// file generation the pipelining is recommended. The execution of
    2.71 +  /// this program:
    2.72 +  ///\code 
    2.73 +  /// ./geng -c 10 | ./num_of_pg 
    2.74 +  ///\endcode
    2.75 +  template <typename UGraph>
    2.76 +  std::istream& readNauty(std::istream& is, UGraph& ugraph) {
    2.77 +    ugraph.clear();
    2.78 +
    2.79 +    std::string line;
    2.80 +    if (getline(is, line)) {
    2.81 +      int index = 0;
    2.82 +    
    2.83 +      int n;
    2.84 +
    2.85 +      if (line[index] == '>') {
    2.86 +	index += 10; 
    2.87 +      }
    2.88 +
    2.89 +      char c = line[index++]; c -= 63;
    2.90 +      if (c != 63) {
    2.91 +	n = int(c);
    2.92 +      } else {
    2.93 +	c = line[index++]; c -= 63;
    2.94 +	n = (int(c) << 12);
    2.95 +	c = line[index++]; c -= 63;
    2.96 +	n |= (int(c) << 6);
    2.97 +	c = line[index++]; c -= 63;
    2.98 +	n |= int(c);      
    2.99 +      }
   2.100 +
   2.101 +      std::vector<typename UGraph::Node> nodes;
   2.102 +      for (int i = 0; i < n; ++i) {
   2.103 +	nodes.push_back(ugraph.addNode());
   2.104 +      }
   2.105 +
   2.106 +      int bit = -1;
   2.107 +      for (int j = 0; j < n; ++j) {
   2.108 +	for (int i = 0; i < j; ++i) {
   2.109 +	  if (bit == -1) {
   2.110 +	    c = line[index++]; c -= 63;
   2.111 +	    bit = 5;
   2.112 +	  }
   2.113 +	  bool b = (c & (1 << (bit--))) != 0;
   2.114 +
   2.115 +	  ugraph.addEdge(nodes[i], nodes[j]);
   2.116 +	}
   2.117 +      }
   2.118 +    }
   2.119 +    return is;
   2.120 +  }
   2.121 +}
   2.122 +
   2.123 +#endif