COIN-OR::LEMON - Graph Library

source: lemon/lemon/nauty_reader.h @ 362:c6c6e1d863c4

Last change on this file since 362:c6c6e1d863c4 was 362:c6c6e1d863c4, checked in by Balazs Dezso <deba@…>, 16 years ago

Swap parameters in readNauty()

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