1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/nauty_reader.h	Wed Oct 29 14:06:08 2008 +0000
     1.3 @@ -0,0 +1,120 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_NAUTY_READER_H
    1.23 +#define LEMON_NAUTY_READER_H
    1.24 +
    1.25 +#include <vector>
    1.26 +#include <iostream>
    1.27 +#include <string>
    1.28 +
    1.29 +/// \ingroup io_group
    1.30 +///
    1.31 +/// @defgroup nauty_group NAUTY format
    1.32 +///
    1.33 +/// \brief Read \e Nauty format
    1.34 +///
    1.35 +/// Tool to read graphs from \e Nauty format data
    1.36 +
    1.37 +/// \ingroup nauty_group
    1.38 +/// \file
    1.39 +/// \brief Nauty file reader.
    1.40 +namespace lemon {
    1.41 +
    1.42 +  /// \ingroup nauty_group
    1.43 +  ///
    1.44 +  /// \brief Nauty file reader
    1.45 +  ///
    1.46 +  /// The \e geng program is in the \e gtools suite of the nauty
    1.47 +  /// package. This tool can generate all non-isomorphic undirected
    1.48 +  /// graphs with given node number from several classes (for example,
    1.49 +  /// general, connected, biconnected, triangle-free, 4-cycle-free,
    1.50 +  /// bipartite and graphs with given edge number and degree
    1.51 +  /// constraints). This function reads a \e nauty \e graph6 \e format
    1.52 +  /// line from the given stream and builds it in the given graph.
    1.53 +  ///
    1.54 +  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
    1.55 +  ///
    1.56 +  /// For example, the number of all non-isomorphic connected graphs
    1.57 +  /// can be computed with following code.
    1.58 +  ///\code
    1.59 +  /// int num = 0;
    1.60 +  /// SmartGraph graph;
    1.61 +  /// while(readNauty(std::cin, graph)) {
    1.62 +  ///   PlanarityChecking<SmartUGraph> pc(graph);
    1.63 +  ///   if (pc.run()) ++num;
    1.64 +  /// }
    1.65 +  /// std::cout << "Number of planar graphs: " << num << std::endl;
    1.66 +  ///\endcode
    1.67 +  ///
    1.68 +  /// The nauty files are quite huge, therefore instead of the direct
    1.69 +  /// file generation the pipelining is recommended.
    1.70 +  ///\code
    1.71 +  /// ./geng -c 10 | ./num_of_pg
    1.72 +  ///\endcode
    1.73 +  template <typename Graph>
    1.74 +  std::istream& readNauty(std::istream& is, Graph& graph) {
    1.75 +    graph.clear();
    1.76 +
    1.77 +    std::string line;
    1.78 +    if (getline(is, line)) {
    1.79 +      int index = 0;
    1.80 +
    1.81 +      int n;
    1.82 +
    1.83 +      if (line[index] == '>') {
    1.84 +        index += 10;
    1.85 +      }
    1.86 +
    1.87 +      char c = line[index++]; c -= 63;
    1.88 +      if (c != 63) {
    1.89 +        n = int(c);
    1.90 +      } else {
    1.91 +        c = line[index++]; c -= 63;
    1.92 +        n = (int(c) << 12);
    1.93 +        c = line[index++]; c -= 63;
    1.94 +        n |= (int(c) << 6);
    1.95 +        c = line[index++]; c -= 63;
    1.96 +        n |= int(c);
    1.97 +      }
    1.98 +
    1.99 +      std::vector<typename Graph::Node> nodes;
   1.100 +      for (int i = 0; i < n; ++i) {
   1.101 +        nodes.push_back(graph.addNode());
   1.102 +      }
   1.103 +
   1.104 +      int bit = -1;
   1.105 +      for (int j = 0; j < n; ++j) {
   1.106 +        for (int i = 0; i < j; ++i) {
   1.107 +          if (bit == -1) {
   1.108 +            c = line[index++]; c -= 63;
   1.109 +            bit = 5;
   1.110 +          }
   1.111 +          bool b = (c & (1 << (bit--))) != 0;
   1.112 +
   1.113 +          if (b) {
   1.114 +            graph.addEdge(nodes[i], nodes[j]);
   1.115 +          }
   1.116 +        }
   1.117 +      }
   1.118 +    }
   1.119 +    return is;
   1.120 +  }
   1.121 +}
   1.122 +
   1.123 +#endif