deba@348: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@348: * deba@348: * This file is a part of LEMON, a generic C++ optimization library. deba@348: * deba@348: * Copyright (C) 2003-2008 deba@348: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@348: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@348: * deba@348: * Permission to use, modify and distribute this software is granted deba@348: * provided that this copyright notice appears in all copies. For deba@348: * precise terms see the accompanying LICENSE file. deba@348: * deba@348: * This software is provided "AS IS" with no warranty of any kind, deba@348: * express or implied, and with no claim as to its suitability for any deba@348: * purpose. deba@348: * deba@348: */ deba@348: deba@348: #ifndef LEMON_NAUTY_READER_H deba@348: #define LEMON_NAUTY_READER_H deba@348: deba@348: #include deba@348: #include deba@348: #include deba@348: deba@348: /// \ingroup io_group deba@348: /// deba@348: /// @defgroup nauty_group NAUTY format deba@348: /// deba@348: /// \brief Read \e Nauty format deba@348: /// deba@348: /// Tool to read graphs from \e Nauty format data deba@348: deba@348: /// \ingroup nauty_group deba@348: /// \file deba@348: /// \brief Nauty file reader. deba@348: namespace lemon { deba@348: deba@348: /// \ingroup nauty_group deba@348: /// deba@348: /// \brief Nauty file reader deba@348: /// deba@348: /// The \e geng program is in the \e gtools suite of the nauty deba@348: /// package. This tool can generate all non-isomorphic undirected deba@348: /// graphs with given node number from several classes (for example, deba@348: /// general, connected, biconnected, triangle-free, 4-cycle-free, deba@348: /// bipartite and graphs with given edge number and degree deba@348: /// constraints). This function reads a \e nauty \e graph6 \e format deba@348: /// line from the given stream and builds it in the given graph. deba@348: /// deba@348: /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/ deba@348: /// deba@348: /// For example, the number of all non-isomorphic connected graphs deba@348: /// can be computed with following code. deba@348: ///\code deba@348: /// int num = 0; deba@348: /// SmartGraph graph; deba@350: /// while (readNauty(graph, std::cin)) { deba@350: /// PlanarityChecking pc(graph); deba@348: /// if (pc.run()) ++num; deba@348: /// } deba@348: /// std::cout << "Number of planar graphs: " << num << std::endl; deba@348: ///\endcode deba@348: /// deba@348: /// The nauty files are quite huge, therefore instead of the direct deba@348: /// file generation the pipelining is recommended. deba@348: ///\code deba@348: /// ./geng -c 10 | ./num_of_pg deba@348: ///\endcode deba@348: template deba@350: std::istream& readNauty(Graph& graph, std::istream& is) { deba@348: graph.clear(); deba@348: deba@348: std::string line; deba@348: if (getline(is, line)) { deba@348: int index = 0; deba@348: deba@348: int n; deba@348: deba@348: if (line[index] == '>') { deba@348: index += 10; deba@348: } deba@348: deba@348: char c = line[index++]; c -= 63; deba@348: if (c != 63) { deba@348: n = int(c); deba@348: } else { deba@348: c = line[index++]; c -= 63; deba@348: n = (int(c) << 12); deba@348: c = line[index++]; c -= 63; deba@348: n |= (int(c) << 6); deba@348: c = line[index++]; c -= 63; deba@348: n |= int(c); deba@348: } deba@348: deba@348: std::vector nodes; deba@348: for (int i = 0; i < n; ++i) { deba@348: nodes.push_back(graph.addNode()); deba@348: } deba@348: deba@348: int bit = -1; deba@348: for (int j = 0; j < n; ++j) { deba@348: for (int i = 0; i < j; ++i) { deba@348: if (bit == -1) { deba@348: c = line[index++]; c -= 63; deba@348: bit = 5; deba@348: } deba@348: bool b = (c & (1 << (bit--))) != 0; deba@348: deba@348: if (b) { deba@348: graph.addEdge(nodes[i], nodes[j]); deba@348: } deba@348: } deba@348: } deba@348: } deba@348: return is; deba@348: } deba@348: } deba@348: deba@348: #endif