1.1 --- a/lemon/Makefile.am	Wed Oct 29 06:22:21 2008 +0000
     1.2 +++ b/lemon/Makefile.am	Wed Oct 29 14:06:08 2008 +0000
     1.3 @@ -37,6 +37,7 @@
     1.4  	lemon/maps.h \
     1.5  	lemon/math.h \
     1.6  	lemon/max_matching.h \
     1.7 +	lemon/nauty_reader.h \
     1.8  	lemon/path.h \
     1.9          lemon/random.h \
    1.10  	lemon/smart_graph.h \

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/nauty_reader.h	Wed Oct 29 14:06:08 2008 +0000
     2.3 @@ -0,0 +1,120 @@
     2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library.
     2.7 + *
     2.8 + * Copyright (C) 2003-2008
     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 +/// \ingroup io_group
    2.30 +///
    2.31 +/// @defgroup nauty_group NAUTY format
    2.32 +///
    2.33 +/// \brief Read \e Nauty format
    2.34 +///
    2.35 +/// Tool to read graphs from \e Nauty format data
    2.36 +
    2.37 +/// \ingroup nauty_group
    2.38 +/// \file
    2.39 +/// \brief Nauty file reader.
    2.40 +namespace lemon {
    2.41 +
    2.42 +  /// \ingroup nauty_group
    2.43 +  ///
    2.44 +  /// \brief Nauty file reader
    2.45 +  ///
    2.46 +  /// The \e geng program is in the \e gtools suite of the nauty
    2.47 +  /// package. This tool can generate all non-isomorphic undirected
    2.48 +  /// graphs with given node number from several classes (for example,
    2.49 +  /// general, connected, biconnected, triangle-free, 4-cycle-free,
    2.50 +  /// bipartite and graphs with given edge number and degree
    2.51 +  /// constraints). This function reads a \e nauty \e graph6 \e format
    2.52 +  /// line from the given stream and builds it in the given graph.
    2.53 +  ///
    2.54 +  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
    2.55 +  ///
    2.56 +  /// For example, the number of all non-isomorphic connected graphs
    2.57 +  /// can be computed with following code.
    2.58 +  ///\code
    2.59 +  /// int num = 0;
    2.60 +  /// SmartGraph graph;
    2.61 +  /// while(readNauty(std::cin, graph)) {
    2.62 +  ///   PlanarityChecking<SmartUGraph> pc(graph);
    2.63 +  ///   if (pc.run()) ++num;
    2.64 +  /// }
    2.65 +  /// std::cout << "Number of planar graphs: " << num << std::endl;
    2.66 +  ///\endcode
    2.67 +  ///
    2.68 +  /// The nauty files are quite huge, therefore instead of the direct
    2.69 +  /// file generation the pipelining is recommended.
    2.70 +  ///\code
    2.71 +  /// ./geng -c 10 | ./num_of_pg
    2.72 +  ///\endcode
    2.73 +  template <typename Graph>
    2.74 +  std::istream& readNauty(std::istream& is, Graph& graph) {
    2.75 +    graph.clear();
    2.76 +
    2.77 +    std::string line;
    2.78 +    if (getline(is, line)) {
    2.79 +      int index = 0;
    2.80 +
    2.81 +      int n;
    2.82 +
    2.83 +      if (line[index] == '>') {
    2.84 +        index += 10;
    2.85 +      }
    2.86 +
    2.87 +      char c = line[index++]; c -= 63;
    2.88 +      if (c != 63) {
    2.89 +        n = int(c);
    2.90 +      } else {
    2.91 +        c = line[index++]; c -= 63;
    2.92 +        n = (int(c) << 12);
    2.93 +        c = line[index++]; c -= 63;
    2.94 +        n |= (int(c) << 6);
    2.95 +        c = line[index++]; c -= 63;
    2.96 +        n |= int(c);
    2.97 +      }
    2.98 +
    2.99 +      std::vector<typename Graph::Node> nodes;
   2.100 +      for (int i = 0; i < n; ++i) {
   2.101 +        nodes.push_back(graph.addNode());
   2.102 +      }
   2.103 +
   2.104 +      int bit = -1;
   2.105 +      for (int j = 0; j < n; ++j) {
   2.106 +        for (int i = 0; i < j; ++i) {
   2.107 +          if (bit == -1) {
   2.108 +            c = line[index++]; c -= 63;
   2.109 +            bit = 5;
   2.110 +          }
   2.111 +          bool b = (c & (1 << (bit--))) != 0;
   2.112 +
   2.113 +          if (b) {
   2.114 +            graph.addEdge(nodes[i], nodes[j]);
   2.115 +          }
   2.116 +        }
   2.117 +      }
   2.118 +    }
   2.119 +    return is;
   2.120 +  }
   2.121 +}
   2.122 +
   2.123 +#endif