/usr/include/lemon/nauty_reader.h is in liblemon-dev 1.3.1+dfsg-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | /* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file is a part of LEMON, a generic C++ optimization library.
*
* Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#ifndef LEMON_NAUTY_READER_H
#define LEMON_NAUTY_READER_H
#include <vector>
#include <iostream>
#include <string>
/// \ingroup nauty_group
/// \file
/// \brief Nauty file reader.
namespace lemon {
/// \ingroup nauty_group
///
/// \brief Nauty file reader
///
/// The \e geng program is in the \e gtools suite of the nauty
/// package. This tool can generate all non-isomorphic undirected
/// graphs of several classes with given node number (e.g.
/// general, connected, biconnected, triangle-free, 4-cycle-free,
/// bipartite and graphs with given edge number and degree
/// constraints). This function reads a \e nauty \e graph6 \e format
/// line from the given stream and builds it in the given graph.
///
/// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/
///
/// For example, the number of all non-isomorphic planar graphs
/// can be computed with the following code.
///\code
/// int num = 0;
/// SmartGraph graph;
/// while (readNautyGraph(graph, std::cin)) {
/// PlanarityChecking<SmartGraph> pc(graph);
/// if (pc.run()) ++num;
/// }
/// std::cout << "Number of planar graphs: " << num << std::endl;
///\endcode
///
/// The nauty files are quite huge, therefore instead of the direct
/// file generation pipelining is recommended. For example,
///\code
/// ./geng -c 10 | ./num_of_planar_graphs
///\endcode
template <typename Graph>
std::istream& readNautyGraph(Graph& graph, std::istream& is = std::cin) {
graph.clear();
std::string line;
if (getline(is, line)) {
int index = 0;
int n;
if (line[index] == '>') {
index += 10;
}
char c = line[index++]; c -= 63;
if (c != 63) {
n = int(c);
} else {
c = line[index++]; c -= 63;
n = (int(c) << 12);
c = line[index++]; c -= 63;
n |= (int(c) << 6);
c = line[index++]; c -= 63;
n |= int(c);
}
std::vector<typename Graph::Node> nodes;
for (int i = 0; i < n; ++i) {
nodes.push_back(graph.addNode());
}
int bit = -1;
for (int j = 0; j < n; ++j) {
for (int i = 0; i < j; ++i) {
if (bit == -1) {
c = line[index++]; c -= 63;
bit = 5;
}
bool b = (c & (1 << (bit--))) != 0;
if (b) {
graph.addEdge(nodes[i], nodes[j]);
}
}
}
}
return is;
}
}
#endif
|