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: * alpar@440: * Copyright (C) 2003-2009 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 nauty_group deba@348: /// \file deba@348: /// \brief Nauty file reader. kpeter@351: 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 kpeter@352: /// graphs of several classes with given node number (e.g. deba@348: /// general, connected, biconnected, triangle-free, 4-cycle-free, deba@348: /// bipartite and graphs with given edge number and degree kpeter@358: /// 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: /// kpeter@352: /// For example, the number of all non-isomorphic planar graphs kpeter@352: /// can be computed with the following code. deba@348: ///\code deba@348: /// int num = 0; deba@348: /// SmartGraph graph; kpeter@359: /// while (readNautyGraph(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 kpeter@352: /// file generation pipelining is recommended. For example, deba@348: ///\code kpeter@352: /// ./geng -c 10 | ./num_of_planar_graphs deba@348: ///\endcode deba@348: template kpeter@359: std::istream& readNautyGraph(Graph& graph, std::istream& is = std::cin) { 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