Select Git revision
prvocisla-else.py
-
Martin Mareš authoredMartin Mareš authored
group-connectivity.h 3.33 KiB
#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