Select Git revision
org_submit_list.html
-
Jan Prachař authoredJan Prachař authored
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