COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/nauty_reader.h @ 2543:a0443c411220

Last change on this file since 2543:a0443c411220 was 2516:6a30e13a1c79, checked in by Balazs Dezso, 16 years ago

Nauty graph6 reader

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