group-connectivity.h

#ifndef __GROUP_CONNECTIVITY_H__
#define __GROUP_CONNECTIVITY_H__

#include <vector>
#include "compileTimeOptions.h"
#include "rings.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 std::vector<T> Mapping;

  // combine(alpha, a, beta, b) calculates a = alpha * a + beta * b
  Mapping& combine(T alpha, Mapping& a, T beta, const Mapping& b) {
    size_t size = a.size();
    for (size_t i = 0; i < size; i++)
      a[i] = Ring::plus(Ring::multiply(alpha, a[i]),
                        Ring::multiply(beta, b[i]));
    return a;
  }


  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, 0)));
      Mapping &map = nonClassEdges.back().second;

      for (auto edge : elemCycle) {
        bool neg = (edge < 0);
        edge = neg ? -edge : edge;
        edge -= 1;
        map[edge] = neg ? Ring::one : Ring::negate(Ring::one);
      }
    }
  }
  
  Mapping& unpack(size_t index, Mapping& ret) {
    size_t m = Ring::size - 1;

    for (size_t i = 0; i < edges; i++) {
      ret[i] = (index % m) + 1;
      index /= m;
    }

    return ret;
  }

  Mapping& cannonize(Mapping& map) {
    for (const auto &i : nonClassEdges) {
      if (map[i.first] != Ring::zero)
        combine(Ring::one, map, 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() {
    Mapping forb(edges, 0);
    
    for (size_t i = 0; i < numForb; i++)
#if SAVE_MEMORY
      classes[pack(cannonize(unpack(i, forb)))] = true;
#else
      classes[pack(cannonize(unpack(i, forb)))]++;
#endif

    for (const auto &c : classes) if (!c) return (isConnected = false);

    return (isConnected = true);
  }

  virtual ~Tester() {}
};

#endif