Graph-Isomorphism/configuration.h at master · MadPidgeon/Graph-Isomorphism · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#pragma once
#include <vector>
#include <set>
#include <map>
#include "ext.h"
#include "matrix.h"

class RelationalStructure;
class ColoredPartition;
class Graph;
class BipartiteGraph;

class RelationalStructure {
	int _n;
	int _dimension;
	std::vector<std::set<std::vector<int>>> _relations;

	size_t c( const std::vector<int>& t ) const;
	void refine( bool print );
public:
	size_t domainSize() const;
	size_t arity() const;
	bool isBinary() const;
	bool isUniprimitive() const;
	bool isHomogeneous() const;
	bool isPrimitive() const;
	void individualize( std::vector<int> );
	RelationalStructure skeletalSubstructure( int t, std::vector<int> Delta ) const;
	void WeisfellerLeman( bool print = false );
	const std::vector<std::set<std::vector<int>>>& relations() const;
	RelationalStructure( std::vector<std::set<std::vector<int>>> relations, int n );
	RelationalStructure( const Graph& G, int k );
};

class ColoredPartition {
	int _n;
	std::vector<std::vector<std::set<int>>> _partition_to_elements;
	std::vector<std::pair<int,int>> _element_to_partitions;
public:
	void individualize( int i );
	ColoredPartition( std::vector<std::vector<std::set<int>>> partitions );
};

class Graph {
	matrix<bool> adjacency;
public:
	size_t vertices() const;
	std::vector<bool>::reference edge( int u, int v );
	std::vector<bool>::const_reference edge( int u, int v ) const;
	const matrix<bool>& adjacencyMatrix() const;
	Graph( int n );
};

class BipartiteGraph {
	std::vector<bool> _vertex_part;
	std::multimap<int,int> _edges;
	ColoredPartition _colors;
public:
	size_t domainSize() const;
	const ColoredPartition& coloring() const;
	bool vertex( int i ) const;
};


class JohnsonScheme {

};

Either<ColoredPartition,JohnsonScheme> bipartiteSplitOrJohnson( const BipartiteGraph& X, double alpha );
Either<ColoredPartition,RelationalStructure> splitOrUPCC( const RelationalStructure& X, double alpha );