Select Git revision
group-connectivity.h
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;