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