|
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. |
|
38 namespace 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 |