1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/nauty_reader.h Tue Nov 20 15:06:03 2007 +0000
1.3 @@ -0,0 +1,120 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_NAUTY_READER_H
1.23 +#define LEMON_NAUTY_READER_H
1.24 +
1.25 +#include <vector>
1.26 +#include <iostream>
1.27 +#include <string>
1.28 +
1.29 +
1.30 +/// \ingroup io_group
1.31 +///
1.32 +/// @defgroup nauty_group NAUTY format
1.33 +///
1.34 +/// \brief Read \e Nauty format
1.35 +///
1.36 +/// Tool to read graphs from \e Nauty format data
1.37 +
1.38 +/// \ingroup nauty_group
1.39 +/// \file
1.40 +/// \brief Nauty file reader.
1.41 +namespace lemon {
1.42 +
1.43 + /// \ingroup nauty_group
1.44 + ///
1.45 + /// \brief Nauty file reader
1.46 + ///
1.47 + /// The \e geng program is in the \e gtools suite of the nauty
1.48 + /// package. This tool can generate all non-isomorphic undirected
1.49 + /// graphs with given node number from several classes (for example,
1.50 + /// general, connected, biconnected, triangle-free, 4-cycle-free,
1.51 + /// bipartite and graphs with given edge number and degree
1.52 + /// constraints). This function reads a \e nauty \e graph6 \e format
1.53 + /// line from the given stream and builds it in the given graph.
1.54 + ///
1.55 + /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
1.56 + ///
1.57 + /// For example, the number of all non-isomorphic connected graphs
1.58 + /// can be computed with next code:
1.59 + ///\code
1.60 + /// int num = 0;
1.61 + /// SmartUGraph ugraph;
1.62 + /// while(readNauty(std::cin, ugraph)) {
1.63 + /// PlanarityChecking<SmartUGraph> pc(ugraph);
1.64 + /// if (pc.run()) ++num;
1.65 + /// }
1.66 + /// std::cout << "Number of planar graphs: " << num << std::endl;
1.67 + ///\endcode
1.68 + ///
1.69 + /// The nauty files are quite huge, therefore instead of the direct
1.70 + /// file generation the pipelining is recommended. The execution of
1.71 + /// this program:
1.72 + ///\code
1.73 + /// ./geng -c 10 | ./num_of_pg
1.74 + ///\endcode
1.75 + template <typename UGraph>
1.76 + std::istream& readNauty(std::istream& is, UGraph& ugraph) {
1.77 + ugraph.clear();
1.78 +
1.79 + std::string line;
1.80 + if (getline(is, line)) {
1.81 + int index = 0;
1.82 +
1.83 + int n;
1.84 +
1.85 + if (line[index] == '>') {
1.86 + index += 10;
1.87 + }
1.88 +
1.89 + char c = line[index++]; c -= 63;
1.90 + if (c != 63) {
1.91 + n = int(c);
1.92 + } else {
1.93 + c = line[index++]; c -= 63;
1.94 + n = (int(c) << 12);
1.95 + c = line[index++]; c -= 63;
1.96 + n |= (int(c) << 6);
1.97 + c = line[index++]; c -= 63;
1.98 + n |= int(c);
1.99 + }
1.100 +
1.101 + std::vector<typename UGraph::Node> nodes;
1.102 + for (int i = 0; i < n; ++i) {
1.103 + nodes.push_back(ugraph.addNode());
1.104 + }
1.105 +
1.106 + int bit = -1;
1.107 + for (int j = 0; j < n; ++j) {
1.108 + for (int i = 0; i < j; ++i) {
1.109 + if (bit == -1) {
1.110 + c = line[index++]; c -= 63;
1.111 + bit = 5;
1.112 + }
1.113 + bool b = (c & (1 << (bit--))) != 0;
1.114 +
1.115 + ugraph.addEdge(nodes[i], nodes[j]);
1.116 + }
1.117 + }
1.118 + }
1.119 + return is;
1.120 + }
1.121 +}
1.122 +
1.123 +#endif