Skip to content
Snippets Groups Projects
Select Git revision
  • a27797e1f2edcceb0ab3ae57c400978b9bcc51ff
  • master default protected
2 results

group-connectivity.h

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;