lemon/nauty_reader.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 30 Nov 2008 00:48:07 +0100
changeset 392 db3251947eba
parent 358 636fa2f39f10
child 440 88ed40ad0d4f
permissions -rw-r--r--
Rename flowInit() to init() in Preflow (#176)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     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 /// \ingroup nauty_group
    27 /// \file
    28 /// \brief Nauty file reader.
    29 
    30 namespace lemon {
    31 
    32   /// \ingroup nauty_group
    33   ///
    34   /// \brief Nauty file reader
    35   ///
    36   /// The \e geng program is in the \e gtools suite of the nauty
    37   /// package. This tool can generate all non-isomorphic undirected
    38   /// graphs of several classes with given node number (e.g.
    39   /// general, connected, biconnected, triangle-free, 4-cycle-free,
    40   /// bipartite and graphs with given edge number and degree
    41   /// constraints). This function reads a \e nauty \e graph6 \e format
    42   /// line from the given stream and builds it in the given graph.
    43   ///
    44   /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
    45   ///
    46   /// For example, the number of all non-isomorphic planar graphs
    47   /// can be computed with the following code.
    48   ///\code
    49   /// int num = 0;
    50   /// SmartGraph graph;
    51   /// while (readNautyGraph(graph, std::cin)) {
    52   ///   PlanarityChecking<SmartGraph> pc(graph);
    53   ///   if (pc.run()) ++num;
    54   /// }
    55   /// std::cout << "Number of planar graphs: " << num << std::endl;
    56   ///\endcode
    57   ///
    58   /// The nauty files are quite huge, therefore instead of the direct
    59   /// file generation pipelining is recommended. For example,
    60   ///\code
    61   /// ./geng -c 10 | ./num_of_planar_graphs
    62   ///\endcode
    63   template <typename Graph>
    64   std::istream& readNautyGraph(Graph& graph, std::istream& is = std::cin) {
    65     graph.clear();
    66 
    67     std::string line;
    68     if (getline(is, line)) {
    69       int index = 0;
    70 
    71       int n;
    72 
    73       if (line[index] == '>') {
    74         index += 10;
    75       }
    76 
    77       char c = line[index++]; c -= 63;
    78       if (c != 63) {
    79         n = int(c);
    80       } else {
    81         c = line[index++]; c -= 63;
    82         n = (int(c) << 12);
    83         c = line[index++]; c -= 63;
    84         n |= (int(c) << 6);
    85         c = line[index++]; c -= 63;
    86         n |= int(c);
    87       }
    88 
    89       std::vector<typename Graph::Node> nodes;
    90       for (int i = 0; i < n; ++i) {
    91         nodes.push_back(graph.addNode());
    92       }
    93 
    94       int bit = -1;
    95       for (int j = 0; j < n; ++j) {
    96         for (int i = 0; i < j; ++i) {
    97           if (bit == -1) {
    98             c = line[index++]; c -= 63;
    99             bit = 5;
   100           }
   101           bool b = (c & (1 << (bit--))) != 0;
   102 
   103           if (b) {
   104             graph.addEdge(nodes[i], nodes[j]);
   105           }
   106         }
   107       }
   108     }
   109     return is;
   110   }
   111 }
   112 
   113 #endif