lemon/nauty_reader.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 04 Nov 2008 10:21:22 +0000
changeset 356 99f1bdf8f7db
parent 348 96f7cc46c91c
child 351 91e68d590e61
permissions -rw-r--r--
Merge
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 io_group
deba@348
    27
///
deba@348
    28
/// @defgroup nauty_group NAUTY format
deba@348
    29
///
deba@348
    30
/// \brief Read \e Nauty format
deba@348
    31
///
deba@348
    32
/// Tool to read graphs from \e Nauty format data
deba@348
    33
deba@348
    34
/// \ingroup nauty_group
deba@348
    35
/// \file
deba@348
    36
/// \brief Nauty file reader.
deba@348
    37
namespace lemon {
deba@348
    38
deba@348
    39
  /// \ingroup nauty_group
deba@348
    40
  ///
deba@348
    41
  /// \brief Nauty file reader
deba@348
    42
  ///
deba@348
    43
  /// The \e geng program is in the \e gtools suite of the nauty
deba@348
    44
  /// package. This tool can generate all non-isomorphic undirected
deba@348
    45
  /// graphs with given node number from several classes (for example,
deba@348
    46
  /// general, connected, biconnected, triangle-free, 4-cycle-free,
deba@348
    47
  /// bipartite and graphs with given edge number and degree
deba@348
    48
  /// constraints). This function reads a \e nauty \e graph6 \e format
deba@348
    49
  /// line from the given stream and builds it in the given graph.
deba@348
    50
  ///
deba@348
    51
  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
deba@348
    52
  ///
deba@348
    53
  /// For example, the number of all non-isomorphic connected graphs
deba@348
    54
  /// can be computed with following code.
deba@348
    55
  ///\code
deba@348
    56
  /// int num = 0;
deba@348
    57
  /// SmartGraph graph;
deba@350
    58
  /// while (readNauty(graph, std::cin)) {
deba@350
    59
  ///   PlanarityChecking<SmartGraph> pc(graph);
deba@348
    60
  ///   if (pc.run()) ++num;
deba@348
    61
  /// }
deba@348
    62
  /// std::cout << "Number of planar graphs: " << num << std::endl;
deba@348
    63
  ///\endcode
deba@348
    64
  ///
deba@348
    65
  /// The nauty files are quite huge, therefore instead of the direct
deba@348
    66
  /// file generation the pipelining is recommended.
deba@348
    67
  ///\code
deba@348
    68
  /// ./geng -c 10 | ./num_of_pg
deba@348
    69
  ///\endcode
deba@348
    70
  template <typename Graph>
deba@350
    71
  std::istream& readNauty(Graph& graph, std::istream& is) {
deba@348
    72
    graph.clear();
deba@348
    73
deba@348
    74
    std::string line;
deba@348
    75
    if (getline(is, line)) {
deba@348
    76
      int index = 0;
deba@348
    77
deba@348
    78
      int n;
deba@348
    79
deba@348
    80
      if (line[index] == '>') {
deba@348
    81
        index += 10;
deba@348
    82
      }
deba@348
    83
deba@348
    84
      char c = line[index++]; c -= 63;
deba@348
    85
      if (c != 63) {
deba@348
    86
        n = int(c);
deba@348
    87
      } else {
deba@348
    88
        c = line[index++]; c -= 63;
deba@348
    89
        n = (int(c) << 12);
deba@348
    90
        c = line[index++]; c -= 63;
deba@348
    91
        n |= (int(c) << 6);
deba@348
    92
        c = line[index++]; c -= 63;
deba@348
    93
        n |= int(c);
deba@348
    94
      }
deba@348
    95
deba@348
    96
      std::vector<typename Graph::Node> nodes;
deba@348
    97
      for (int i = 0; i < n; ++i) {
deba@348
    98
        nodes.push_back(graph.addNode());
deba@348
    99
      }
deba@348
   100
deba@348
   101
      int bit = -1;
deba@348
   102
      for (int j = 0; j < n; ++j) {
deba@348
   103
        for (int i = 0; i < j; ++i) {
deba@348
   104
          if (bit == -1) {
deba@348
   105
            c = line[index++]; c -= 63;
deba@348
   106
            bit = 5;
deba@348
   107
          }
deba@348
   108
          bool b = (c & (1 << (bit--))) != 0;
deba@348
   109
deba@348
   110
          if (b) {
deba@348
   111
            graph.addEdge(nodes[i], nodes[j]);
deba@348
   112
          }
deba@348
   113
        }
deba@348
   114
      }
deba@348
   115
    }
deba@348
   116
    return is;
deba@348
   117
  }
deba@348
   118
}
deba@348
   119
deba@348
   120
#endif