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

euklides-odcitaci.py

Blame
  • group-connectivity.h 3.58 KiB
    #ifndef __GROUP_CONNECTIVITY_H__
    #define __GROUP_CONNECTIVITY_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;
    
      size_t numForb;
      int edges;
    
      std::vector<EdgeId> classEdges;
      std::vector< std::pair<EdgeId, Mapping> > nonClassEdges;
    
      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);
    
        size_t num_classes = 1;
        edges_ = spanningTree.size();
        while (edges_-- > 0) num_classes *= Ring::size;
        ClassesType C(num_classes, 0);
        C.swap(classes);
    
        for (auto e : spanningTree)
          classEdges.push_back(e - 1);
    
        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_NEXT_FORB
      bool nextForb(Mapping& forb) {
        for (size_t i = 0; i < edges; i++) {
          T v = forb[i] + 1;
          if (v >= Ring::size) {
            forb.assign(i, 1);
          } else {
            forb.assign(i, v);
            return true;
          }
        }
    
        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& cannonize(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];
        }
    
        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);
    
          do {
            Mapping copy(forb);
            INC(classes[pack(cannonize(copy))]);
          } while (nextForb(forb));
    #   else
          for (size_t i = 0; i < numForb; i++)
            INC(classes[pack(cannonize(unpack(i, forb)))]);
    #   endif
    
        for (const auto &c : classes) if (!c) return (isConnected = false);
    
        return (isConnected = true);
    #   undef INC
      }
    
      virtual ~Tester() {}
    };
    
    #endif