|
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. |
|
37 namespace 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(std::cin, graph)) { |
|
59 /// PlanarityChecking<SmartUGraph> 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(std::istream& is, Graph& graph) { |
|
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 |