lemon/nauty_reader.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 12 Dec 2008 21:44:37 +0100
changeset 430 09e416d35896
parent 358 636fa2f39f10
child 440 88ed40ad0d4f
permissions -rw-r--r--
Bug fix in variant.h (#196)
deba@348
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@348
     2
 *
deba@348
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@348
     4
 *
deba@348
     5
 * Copyright (C) 2003-2008
deba@348
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@348
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@348
     8
 *
deba@348
     9
 * Permission to use, modify and distribute this software is granted
deba@348
    10
 * provided that this copyright notice appears in all copies. For
deba@348
    11
 * precise terms see the accompanying LICENSE file.
deba@348
    12
 *
deba@348
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@348
    14
 * express or implied, and with no claim as to its suitability for any
deba@348
    15
 * purpose.
deba@348
    16
 *
deba@348
    17
 */
deba@348
    18
deba@348
    19
#ifndef LEMON_NAUTY_READER_H
deba@348
    20
#define LEMON_NAUTY_READER_H
deba@348
    21
deba@348
    22
#include <vector>
deba@348
    23
#include <iostream>
deba@348
    24
#include <string>
deba@348
    25
deba@348
    26
/// \ingroup nauty_group
deba@348
    27
/// \file
deba@348
    28
/// \brief Nauty file reader.
kpeter@351
    29
deba@348
    30
namespace lemon {
deba@348
    31
deba@348
    32
  /// \ingroup nauty_group
deba@348
    33
  ///
deba@348
    34
  /// \brief Nauty file reader
deba@348
    35
  ///
deba@348
    36
  /// The \e geng program is in the \e gtools suite of the nauty
deba@348
    37
  /// package. This tool can generate all non-isomorphic undirected
kpeter@352
    38
  /// graphs of several classes with given node number (e.g.
deba@348
    39
  /// general, connected, biconnected, triangle-free, 4-cycle-free,
deba@348
    40
  /// bipartite and graphs with given edge number and degree
kpeter@358
    41
  /// constraints). This function reads a \e nauty \e graph6 \e format
deba@348
    42
  /// line from the given stream and builds it in the given graph.
deba@348
    43
  ///
deba@348
    44
  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
deba@348
    45
  ///
kpeter@352
    46
  /// For example, the number of all non-isomorphic planar graphs
kpeter@352
    47
  /// can be computed with the following code.
deba@348
    48
  ///\code
deba@348
    49
  /// int num = 0;
deba@348
    50
  /// SmartGraph graph;
kpeter@359
    51
  /// while (readNautyGraph(graph, std::cin)) {
deba@350
    52
  ///   PlanarityChecking<SmartGraph> pc(graph);
deba@348
    53
  ///   if (pc.run()) ++num;
deba@348
    54
  /// }
deba@348
    55
  /// std::cout << "Number of planar graphs: " << num << std::endl;
deba@348
    56
  ///\endcode
deba@348
    57
  ///
deba@348
    58
  /// The nauty files are quite huge, therefore instead of the direct
kpeter@352
    59
  /// file generation pipelining is recommended. For example,
deba@348
    60
  ///\code
kpeter@352
    61
  /// ./geng -c 10 | ./num_of_planar_graphs
deba@348
    62
  ///\endcode
deba@348
    63
  template <typename Graph>
kpeter@359
    64
  std::istream& readNautyGraph(Graph& graph, std::istream& is = std::cin) {
deba@348
    65
    graph.clear();
deba@348
    66
deba@348
    67
    std::string line;
deba@348
    68
    if (getline(is, line)) {
deba@348
    69
      int index = 0;
deba@348
    70
deba@348
    71
      int n;
deba@348
    72
deba@348
    73
      if (line[index] == '>') {
deba@348
    74
        index += 10;
deba@348
    75
      }
deba@348
    76
deba@348
    77
      char c = line[index++]; c -= 63;
deba@348
    78
      if (c != 63) {
deba@348
    79
        n = int(c);
deba@348
    80
      } else {
deba@348
    81
        c = line[index++]; c -= 63;
deba@348
    82
        n = (int(c) << 12);
deba@348
    83
        c = line[index++]; c -= 63;
deba@348
    84
        n |= (int(c) << 6);
deba@348
    85
        c = line[index++]; c -= 63;
deba@348
    86
        n |= int(c);
deba@348
    87
      }
deba@348
    88
deba@348
    89
      std::vector<typename Graph::Node> nodes;
deba@348
    90
      for (int i = 0; i < n; ++i) {
deba@348
    91
        nodes.push_back(graph.addNode());
deba@348
    92
      }
deba@348
    93
deba@348
    94
      int bit = -1;
deba@348
    95
      for (int j = 0; j < n; ++j) {
deba@348
    96
        for (int i = 0; i < j; ++i) {
deba@348
    97
          if (bit == -1) {
deba@348
    98
            c = line[index++]; c -= 63;
deba@348
    99
            bit = 5;
deba@348
   100
          }
deba@348
   101
          bool b = (c & (1 << (bit--))) != 0;
deba@348
   102
deba@348
   103
          if (b) {
deba@348
   104
            graph.addEdge(nodes[i], nodes[j]);
deba@348
   105
          }
deba@348
   106
        }
deba@348
   107
      }
deba@348
   108
    }
deba@348
   109
    return is;
deba@348
   110
  }
deba@348
   111
}
deba@348
   112
deba@348
   113
#endif