RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * 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;

  ///   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>

    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

        -e "s/_Graph/__Gr_aph_label_/g"\

        -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\

        -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\

        -e "s/Graph/_Digr_aph_label_/g"\

        -e "s/graph/_digr_aph_label_/g"\

        -e "s/UEdge/_Ed_ge_label_/g"\

        -e "s/u[Ee]dge/_ed_ge_label_/g"\

        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\

        -e "s/\<Edge\>/_Ar_c_label_/g"\

        -e "s/\<edge\>/_ar_c_label_/g"\

        -e "s/\<Edges\>/_Ar_c_label_s/g"\

        -e "s/\<edges\>/_ar_c_label_s/g"\

        -e "s/_Edge/__Ed_ge_label_/g"\

        -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\

        -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\

        -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\

        -e "s/Edge/_Ar_c_label_/g"\

        -e "s/edge/_ar_c_label_/g"\

        -e "s/A[Nn]ode/_Re_d_label_/g"\

        -e "s/B[Nn]ode/_Blu_e_label_/g"\

        -e "s/A-[Nn]ode/_Re_d_label_/g"\

        -e "s/B-[Nn]ode/_Blu_e_label_/g"\

        -e "s/a[Nn]ode/_re_d_label_/g"\

        -e "s/b[Nn]ode/_blu_e_label_/g"\

        -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\

        -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\

        -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\

        -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\

        -e "s/_Digr_aph_label_/Digraph/g"\

        -e "s/_digr_aph_label_/digraph/g"\

        -e "s/_Gr_aph_label_/Graph/g"\

        -e "s/_gr_aph_label_/graph/g"\

        -e "s/_Ar_c_label_/Arc/g"\

        -e "s/_ar_c_label_/arc/g"\

        -e "s/_Ed_ge_label_/Edge/g"\

        -e "s/_ed_ge_label_/edge/g"\

        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\

        -e "s/_Re_d_label_/Red/g"\

        -e "s/_Blu_e_label_/Blue/g"\

        -e "s/_re_d_label_/red/g"\

        -e "s/_blu_e_label_/blue/g"\

        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\

        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\

        -e "s/DigraphToEps/GraphToEps/g"\

        -e "s/digraphToEps/graphToEps/g"\

        -e "s/\<DefPredMap\>/SetPredMap/g"\

        -e "s/\<DefDistMap\>/SetDistMap/g"\

        -e "s/\<DefReachedMap\>/SetReachedMap/g"\

        -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\

        -e "s/\<DefHeap\>/SetHeap/g"\

        -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\

        -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\

        -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\

        -e "s/\<copyGraph\>/graphCopy/g"\

        -e "s/\<copyDigraph\>/digraphCopy/g"\

        -e "s/\<IntegerMap\>/RangeMap/g"\

        -e "s/\<integerMap\>/rangeMap/g"\

        -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\

        -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\

        -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\

        -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\

        -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\

        -e "s/\<storeBoolMap\>/loggerBoolMap/g"\

        -e "s/\<BoundingBox\>/Box/g"\

    <$i > $TMP

    mv $TMP $i

done