lemon/nauty_reader.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 04 Nov 2008 10:21:22 +0000
changeset 356 99f1bdf8f7db
parent 348 96f7cc46c91c
child 351 91e68d590e61
permissions -rw-r--r--
Merge
     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 io_group
    27 ///
    28 /// @defgroup nauty_group NAUTY format
    29 ///
    30 /// \brief Read \e Nauty format
    31 ///
    32 /// Tool to read graphs from \e Nauty format data
    33 
    34 /// \ingroup nauty_group
    35 /// \file
    36 /// \brief Nauty file reader.
    37 namespace lemon {
    38 
    39   /// \ingroup nauty_group
    40   ///
    41   /// \brief Nauty file reader
    42   ///
    43   /// The \e geng program is in the \e gtools suite of the nauty
    44   /// package. This tool can generate all non-isomorphic undirected
    45   /// graphs with given node number from several classes (for example,
    46   /// general, connected, biconnected, triangle-free, 4-cycle-free,
    47   /// bipartite and graphs with given edge number and degree
    48   /// constraints). This function reads a \e nauty \e graph6 \e format
    49   /// line from the given stream and builds it in the given graph.
    50   ///
    51   /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
    52   ///
    53   /// For example, the number of all non-isomorphic connected graphs
    54   /// can be computed with following code.
    55   ///\code
    56   /// int num = 0;
    57   /// SmartGraph graph;
    58   /// while (readNauty(graph, std::cin)) {
    59   ///   PlanarityChecking<SmartGraph> pc(graph);
    60   ///   if (pc.run()) ++num;
    61   /// }
    62   /// std::cout << "Number of planar graphs: " << num << std::endl;
    63   ///\endcode
    64   ///
    65   /// The nauty files are quite huge, therefore instead of the direct
    66   /// file generation the pipelining is recommended.
    67   ///\code
    68   /// ./geng -c 10 | ./num_of_pg
    69   ///\endcode
    70   template <typename Graph>
    71   std::istream& readNauty(Graph& graph, std::istream& is) {
    72     graph.clear();
    73 
    74     std::string line;
    75     if (getline(is, line)) {
    76       int index = 0;
    77 
    78       int n;
    79 
    80       if (line[index] == '>') {
    81         index += 10;
    82       }
    83 
    84       char c = line[index++]; c -= 63;
    85       if (c != 63) {
    86         n = int(c);
    87       } else {
    88         c = line[index++]; c -= 63;
    89         n = (int(c) << 12);
    90         c = line[index++]; c -= 63;
    91         n |= (int(c) << 6);
    92         c = line[index++]; c -= 63;
    93         n |= int(c);
    94       }
    95 
    96       std::vector<typename Graph::Node> nodes;
    97       for (int i = 0; i < n; ++i) {
    98         nodes.push_back(graph.addNode());
    99       }
   100 
   101       int bit = -1;
   102       for (int j = 0; j < n; ++j) {
   103         for (int i = 0; i < j; ++i) {
   104           if (bit == -1) {
   105             c = line[index++]; c -= 63;
   106             bit = 5;
   107           }
   108           bool b = (c & (1 << (bit--))) != 0;
   109 
   110           if (b) {
   111             graph.addEdge(nodes[i], nodes[j]);
   112           }
   113         }
   114       }
   115     }
   116     return is;
   117   }
   118 }
   119 
   120 #endif