COIN-OR::LEMON - Graph Library

source: lemon/lemon/nauty_reader.h @ 363:91e68d590e61

Last change on this file since 363:91e68d590e61 was 363:91e68d590e61, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Move the doc of the nauty group to groups.dox (#55)

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