r374:51597950d0fe
Wed, 05 Nov 2008 09:11:44
[Not Reviewed]
0 comments (0 inline)
0
2
0
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_NAUTY_READER_H |
| 20 | 20 |
#define LEMON_NAUTY_READER_H |
| 21 | 21 |
|
| 22 | 22 |
#include <vector> |
| 23 | 23 |
#include <iostream> |
| 24 | 24 |
#include <string> |
| 25 | 25 |
|
| 26 | 26 |
/// \ingroup nauty_group |
| 27 | 27 |
/// \file |
| 28 | 28 |
/// \brief Nauty file reader. |
| 29 | 29 |
|
| 30 | 30 |
namespace lemon {
|
| 31 | 31 |
|
| 32 | 32 |
/// \ingroup nauty_group |
| 33 | 33 |
/// |
| 34 | 34 |
/// \brief Nauty file reader |
| 35 | 35 |
/// |
| 36 | 36 |
/// The \e geng program is in the \e gtools suite of the nauty |
| 37 | 37 |
/// package. This tool can generate all non-isomorphic undirected |
| 38 | 38 |
/// graphs of several classes with given node number (e.g. |
| 39 | 39 |
/// general, connected, biconnected, triangle-free, 4-cycle-free, |
| 40 | 40 |
/// bipartite and graphs with given edge number and degree |
| 41 |
/// constraints). This function reads a \e nauty \e |
|
| 41 |
/// constraints). This function reads a \e nauty \e graph6 \e format |
|
| 42 | 42 |
/// line from the given stream and builds it in the given graph. |
| 43 | 43 |
/// |
| 44 | 44 |
/// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/ |
| 45 | 45 |
/// |
| 46 | 46 |
/// For example, the number of all non-isomorphic planar graphs |
| 47 | 47 |
/// can be computed with the following code. |
| 48 | 48 |
///\code |
| 49 | 49 |
/// int num = 0; |
| 50 | 50 |
/// SmartGraph graph; |
| 51 |
/// while ( |
|
| 51 |
/// while (readNautyGraph(graph, std::cin)) {
|
|
| 52 | 52 |
/// PlanarityChecking<SmartGraph> pc(graph); |
| 53 | 53 |
/// if (pc.run()) ++num; |
| 54 | 54 |
/// } |
| 55 | 55 |
/// std::cout << "Number of planar graphs: " << num << std::endl; |
| 56 | 56 |
///\endcode |
| 57 | 57 |
/// |
| 58 | 58 |
/// The nauty files are quite huge, therefore instead of the direct |
| 59 | 59 |
/// file generation pipelining is recommended. For example, |
| 60 | 60 |
///\code |
| 61 | 61 |
/// ./geng -c 10 | ./num_of_planar_graphs |
| 62 | 62 |
///\endcode |
| 63 | 63 |
template <typename Graph> |
| 64 |
std::istream& |
|
| 64 |
std::istream& readNautyGraph(Graph& graph, std::istream& is = std::cin) {
|
|
| 65 | 65 |
graph.clear(); |
| 66 | 66 |
|
| 67 | 67 |
std::string line; |
| 68 | 68 |
if (getline(is, line)) {
|
| 69 | 69 |
int index = 0; |
| 70 | 70 |
|
| 71 | 71 |
int n; |
| 72 | 72 |
|
| 73 | 73 |
if (line[index] == '>') {
|
| 74 | 74 |
index += 10; |
| 75 | 75 |
} |
| 76 | 76 |
|
| 77 | 77 |
char c = line[index++]; c -= 63; |
| 78 | 78 |
if (c != 63) {
|
| 79 | 79 |
n = int(c); |
| 80 | 80 |
} else {
|
| 81 | 81 |
c = line[index++]; c -= 63; |
| 82 | 82 |
n = (int(c) << 12); |
| 83 | 83 |
c = line[index++]; c -= 63; |
| 84 | 84 |
n |= (int(c) << 6); |
| 85 | 85 |
c = line[index++]; c -= 63; |
| 86 | 86 |
n |= int(c); |
| 87 | 87 |
} |
| 88 | 88 |
|
| 89 | 89 |
std::vector<typename Graph::Node> nodes; |
| 90 | 90 |
for (int i = 0; i < n; ++i) {
|
| 91 | 91 |
nodes.push_back(graph.addNode()); |
| 92 | 92 |
} |
| 93 | 93 |
|
| 94 | 94 |
int bit = -1; |
| 95 | 95 |
for (int j = 0; j < n; ++j) {
|
| 96 | 96 |
for (int i = 0; i < j; ++i) {
|
| 97 | 97 |
if (bit == -1) {
|
| 98 | 98 |
c = line[index++]; c -= 63; |
| 99 | 99 |
bit = 5; |
| 100 | 100 |
} |
| 101 | 101 |
bool b = (c & (1 << (bit--))) != 0; |
| 102 | 102 |
|
| 103 | 103 |
if (b) {
|
| 104 | 104 |
graph.addEdge(nodes[i], nodes[j]); |
| 105 | 105 |
} |
| 106 | 106 |
} |
| 107 | 107 |
} |
| 108 | 108 |
} |
| 109 | 109 |
return is; |
| 110 | 110 |
} |
| 111 | 111 |
} |
| 112 | 112 |
|
| 113 | 113 |
#endif |
| 1 | 1 |
#!/bin/bash |
| 2 | 2 |
|
| 3 | 3 |
set -e |
| 4 | 4 |
|
| 5 | 5 |
if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then |
| 6 | 6 |
echo "Usage:" |
| 7 | 7 |
echo " $0 source-file(s)" |
| 8 | 8 |
exit |
| 9 | 9 |
fi |
| 10 | 10 |
|
| 11 | 11 |
for i in $@ |
| 12 | 12 |
do |
| 13 | 13 |
echo Update $i... |
| 14 | 14 |
TMP=`mktemp` |
| 15 | 15 |
sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\ |
| 16 | 16 |
-e "s/\<undirected graphs\>/_gr_aph_label_s/g"\ |
| 17 | 17 |
-e "s/\<undirected edge\>/_ed_ge_label_/g"\ |
| 18 | 18 |
-e "s/\<undirected edges\>/_ed_ge_label_s/g"\ |
| 19 | 19 |
-e "s/\<directed graph\>/_digr_aph_label_/g"\ |
| 20 | 20 |
-e "s/\<directed graphs\>/_digr_aph_label_s/g"\ |
| 21 | 21 |
-e "s/\<directed edge\>/_ar_c_label_/g"\ |
| 22 | 22 |
-e "s/\<directed edges\>/_ar_c_label_s/g"\ |
| 23 | 23 |
-e "s/UGraph/_Gr_aph_label_/g"\ |
| 24 | 24 |
-e "s/u[Gg]raph/_gr_aph_label_/g"\ |
| 25 | 25 |
-e "s/\<Graph\>/_Digr_aph_label_/g"\ |
| 26 | 26 |
-e "s/\<graph\>/_digr_aph_label_/g"\ |
| 27 | 27 |
-e "s/\<Graphs\>/_Digr_aph_label_s/g"\ |
| 28 | 28 |
-e "s/\<graphs\>/_digr_aph_label_s/g"\ |
| 29 | 29 |
-e "s/_Graph/__Gr_aph_label_/g"\ |
| 30 | 30 |
-e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\ |
| 31 | 31 |
-e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\ |
| 32 | 32 |
-e "s/Graph/_Digr_aph_label_/g"\ |
| 33 | 33 |
-e "s/graph/_digr_aph_label_/g"\ |
| 34 | 34 |
-e "s/UEdge/_Ed_ge_label_/g"\ |
| 35 | 35 |
-e "s/u[Ee]dge/_ed_ge_label_/g"\ |
| 36 | 36 |
-e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\ |
| 37 | 37 |
-e "s/\<Edge\>/_Ar_c_label_/g"\ |
| 38 | 38 |
-e "s/\<edge\>/_ar_c_label_/g"\ |
| 39 | 39 |
-e "s/\<Edges\>/_Ar_c_label_s/g"\ |
| 40 | 40 |
-e "s/\<edges\>/_ar_c_label_s/g"\ |
| 41 | 41 |
-e "s/_Edge/__Ed_ge_label_/g"\ |
| 42 | 42 |
-e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\ |
| 43 | 43 |
-e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\ |
| 44 | 44 |
-e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\ |
| 45 | 45 |
-e "s/Edge/_Ar_c_label_/g"\ |
| 46 | 46 |
-e "s/edge/_ar_c_label_/g"\ |
| 47 | 47 |
-e "s/A[Nn]ode/_Re_d_label_/g"\ |
| 48 | 48 |
-e "s/B[Nn]ode/_Blu_e_label_/g"\ |
| 49 | 49 |
-e "s/A-[Nn]ode/_Re_d_label_/g"\ |
| 50 | 50 |
-e "s/B-[Nn]ode/_Blu_e_label_/g"\ |
| 51 | 51 |
-e "s/a[Nn]ode/_re_d_label_/g"\ |
| 52 | 52 |
-e "s/b[Nn]ode/_blu_e_label_/g"\ |
| 53 | 53 |
-e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\ |
| 54 | 54 |
-e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\ |
| 55 | 55 |
-e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\ |
| 56 | 56 |
-e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\ |
| 57 | 57 |
-e "s/_Digr_aph_label_/Digraph/g"\ |
| 58 | 58 |
-e "s/_digr_aph_label_/digraph/g"\ |
| 59 | 59 |
-e "s/_Gr_aph_label_/Graph/g"\ |
| 60 | 60 |
-e "s/_gr_aph_label_/graph/g"\ |
| 61 | 61 |
-e "s/_Ar_c_label_/Arc/g"\ |
| 62 | 62 |
-e "s/_ar_c_label_/arc/g"\ |
| 63 | 63 |
-e "s/_Ed_ge_label_/Edge/g"\ |
| 64 | 64 |
-e "s/_ed_ge_label_/edge/g"\ |
| 65 | 65 |
-e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\ |
| 66 | 66 |
-e "s/_Re_d_label_/Red/g"\ |
| 67 | 67 |
-e "s/_Blu_e_label_/Blue/g"\ |
| 68 | 68 |
-e "s/_re_d_label_/red/g"\ |
| 69 | 69 |
-e "s/_blu_e_label_/blue/g"\ |
| 70 | 70 |
-e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\ |
| 71 | 71 |
-e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\ |
| 72 | 72 |
-e "s/DigraphToEps/GraphToEps/g"\ |
| 73 | 73 |
-e "s/digraphToEps/graphToEps/g"\ |
| 74 | 74 |
-e "s/\<DefPredMap\>/SetPredMap/g"\ |
| 75 | 75 |
-e "s/\<DefDistMap\>/SetDistMap/g"\ |
| 76 | 76 |
-e "s/\<DefReachedMap\>/SetReachedMap/g"\ |
| 77 | 77 |
-e "s/\<DefProcessedMap\>/SetProcessedMap/g"\ |
| 78 | 78 |
-e "s/\<DefHeap\>/SetHeap/g"\ |
| 79 | 79 |
-e "s/\<DefStandardHeap\>/SetStandradHeap/g"\ |
| 80 | 80 |
-e "s/\<DefOperationTraits\>/SetOperationTraits/g"\ |
| 81 | 81 |
-e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\ |
| 82 | 82 |
-e "s/\<copyGraph\>/graphCopy/g"\ |
| 83 | 83 |
-e "s/\<copyDigraph\>/digraphCopy/g"\ |
| 84 | 84 |
-e "s/\<IntegerMap\>/RangeMap/g"\ |
| 85 | 85 |
-e "s/\<integerMap\>/rangeMap/g"\ |
| 86 | 86 |
-e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\ |
| 87 | 87 |
-e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\ |
| 88 | 88 |
-e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\ |
| 89 | 89 |
-e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\ |
| 90 | 90 |
-e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\ |
| 91 | 91 |
-e "s/\<storeBoolMap\>/loggerBoolMap/g"\ |
| 92 | 92 |
-e "s/\<BoundingBox\>/Box/g"\ |
| 93 |
-e "s/\<readNauty\>/readNautyGraph/g"\ |
|
| 93 | 94 |
<$i > $TMP |
| 94 | 95 |
mv $TMP $i |
| 95 | 96 |
done |
0 comments (0 inline)