Skip to content
Snippets Groups Projects
Select Git revision
  • 893f7f1c84cc10be1d14499076f52041f5cdc473
  • master default
  • zs2021
  • zs1920
4 results

euklides-modulici.py

Blame
  • group-connectivity.h 5.23 KiB
    #ifndef __GROUP_CONNECTIVITY_H__
    #define __GROUP_CONNECTIVITY_H__
    
    #include <stdlib.h>
    #include <stdint.h>
    #include <vector>
    #include "options.h"
    #include "rings.h"
    #include "fast-array.h"
    
    typedef int EdgeId;
    typedef int DirectedEdgeId;
    typedef std::pair<DirectedEdgeId, DirectedEdgeId> TwoCut;
    
    struct AbstractTester {
      bool isConnected;
    #if SAVE_MEMORY
      typedef std::vector<bool> ClassesType;
    #else
      typedef std::vector<size_t> ClassesType;
    #endif
      ClassesType classes;
    
      virtual void init(
        int edges,
        std::vector<EdgeId> spanningTree,
        std::vector<TwoCut> twoCuts,
        std::vector< std::vector<DirectedEdgeId> > elementaryCycles
      ) =0;
      virtual std::vector<size_t> getClasses() =0;
      virtual bool run() =0;
    
      virtual ~AbstractTester() {}
    };
    
    
    template < typename Ring_ >
    struct Tester : public AbstractTester {
      typedef Ring_ Ring;
      typedef typename Ring::T T;
      typedef ::Mapping<Ring> Mapping;
    
    # include "twoCuts.h"
    
      size_t numForb;
      int edges;
    
      std::vector<EdgeId> classEdges;
      std::vector< std::pair<EdgeId, Mapping> > nonClassEdges;
    # if EXPLICIT_NORMAL_EDGES
      std::vector< EdgeId > normalEdges;
    # endif
    # if USE_TWO_CUTS
      std::vector< TwoCutInt > twoCuts;
    # endif
    
      virtual void init(
        int edges_,
        std::vector<EdgeId> spanningTree,
        std::vector<TwoCut> twoCuts_,
        std::vector< std::vector<DirectedEdgeId> > elementaryCycles
      ) {
        edges = edges_;
        numForb = 1;
        while (edges_-- > 0) numForb *= (Ring::size - 1);
    
    #   if EXPLICIT_NORMAL_EDGES
        std::vector<bool> edgeList(edges, 1);
    #   endif
    
        for (const auto& elemCycle : elementaryCycles) {
          nonClassEdges.push_back(std::make_pair(elemCycle[0] - 1, Mapping(edges)));
          Mapping &map = nonClassEdges.back().second;
    
          for (auto edge : elemCycle) {
            bool neg = (edge < 0);
            edge = neg ? -edge : edge;
            edge -= 1;
            map.assign(edge, neg ? Ring::one : Ring::negate(Ring::one));
          }
        }
    
    #   if USE_TWO_CUTS
        for (auto cut : twoCuts_) {
          if (cut.first < 0) {
            cut.first *= -1;
            cut.second *= -1;
          }
    
          TwoCutInt intCut;
          intCut.a = cut.first - 1;
          intCut.flip = (cut.second < 0);
          intCut.b = (intCut.flip ? - cut.second : cut.second) - 1;
    
          twoCuts.push_back(intCut);
          edgeList[intCut.a] = false;
          edgeList[intCut.b] = false;
        }
    #   endif
    
    #   if EXPLICIT_NORMAL_EDGES
        for (auto e : spanningTree)
          if (edgeList[e - 1]) classEdges.push_back(e - 1);
    
        for (size_t i = 0; i < edges; i++)
          if (edgeList[i]) normalEdges.push_back(i);
    #   else
        for (auto e : spanningTree)
          classEdges.push_back(e - 1);
    #   endif
    
        size_t num_classes = 1;
        edges_ = classEdges.size();
        while (edges_-- > 0) num_classes *= Ring::size;
    #   if USE_TWO_CUTS
        for (const auto& cut : twoCuts) num_classes *= cut.num_classes;
    #   endif
        ClassesType C(num_classes, 0);
        C.swap(classes);
      }
    
    
    #if USE_NEXT_FORB
      bool nextForb(Mapping& forb) {
    #   if EXPLICIT_NORMAL_EDGES
        for (auto i : normalEdges) {
    #   else
        for (size_t i = 0; i < edges; i++) {
    #   endif
          T v = forb[i] + 1;
          if (v >= Ring::size) {
            forb.assign(i, 1);
          } else {
            forb.assign(i, v);
            return true;
          }
        }
    
    #   if USE_TWO_CUTS
        for (const auto& cut : twoCuts) {
          int val = cut.getValue(forb) + 1;
          if (val >= cut.max_value) {
            cut.encode(forb, 0);
          } else {
            cut.encode(forb, val);
            return true;
          }
        }
    #   endif
    
        return false;
      }
    #else // !USE_NEXT_FORB
      Mapping& unpack(size_t index, Mapping& ret) {
        size_t m = Ring::size - 1;
    
        for (size_t i = 0; i < edges; i++) {
          ret.assign(i, (index % m) + 1);
          index /= m;
        }
    
        return ret;
      }
    #endif
    
    
      Mapping& canonize(Mapping& map) {
        for (const auto &i : nonClassEdges) {
    #if OPTIMIZE_COMBINE
          if (map[i.first] != Ring::zero)
    #endif
            map.combine(map[i.first], i.second);
        }
    
        return map;
      }
    
      size_t pack(const Mapping& map) {
        size_t index = 0;
        for (auto i : classEdges) {
          index *= Ring::size;
          index += map[i];
        }
    
    #   if USE_TWO_CUTS
        for (const auto& c : twoCuts) {
          index *= c.num_classes;
          index += c.getClass(map);
        }
    #   endif
    
        return index;
      }
    
    
      virtual std::vector<size_t> getClasses() {
    #if SAVE_MEMORY
        std::vector<size_t> ret(classes.size());
        for (size_t i = 0; i < classes.size(); i++) ret[i] = classes[i];
        return ret;
    #else
        return classes;
    #endif
      }
    
    
    
      virtual bool run() {
    #   if SAVE_MEMORY
    #     define INC(a) a = true
    #   else
    #     define INC(a) a++
    #   endif
    
        Mapping forb(edges);
    
    #   if USE_NEXT_FORB
          for (size_t i = 0; i < edges; i++) forb.assign(i, 1);
    
    #     if USE_TWO_CUTS
          for (const auto& cut : twoCuts) cut.encode(forb, 0);
    #     endif
    
          do {
            Mapping copy(forb);
            INC(classes[pack(canonize(copy))]);
          } while (nextForb(forb));
    #   else
          for (size_t i = 0; i < numForb; i++)
            INC(classes[pack(canonize(unpack(i, forb)))]);
    #   endif
    
        for (const auto &c : classes) if (!c) return (isConnected = false);
    
        return (isConnected = true);
    #   undef INC
      }
    
      virtual ~Tester() {}
    };
    
    #if USE_TWO_CUTS
    template < typename R >
    const typename Tester<R>::TwoCutInt::Tables Tester<R>::TwoCutInt::S;
    #endif
    
    #endif