IterOrbit/Symmetry_8h_source.html

#ifndef SYMMETRY_H

#define SYMMETRY_H


#include <cstdint>

#include <vector>

#include "AppGraph.h"

#include "OrbitCounter.h"


struct SymmetryBreaking {

    std::vector<std::vector<int>> smaller_than;

    uint64_t multiplier = 1;

    int levels = 0;

    bool truncated = false;

    long long work = 0;

};


SymmetryBreaking computeSymmetryBreaking(const AppGraph& pattern, const OrbitCounts& orbits,

                                         const std::vector<int>& order, long long budget = 20000000);


#endif

AppGraph.h
The graph type shared by the pattern, the data graph and its induced subgraphs.

OrbitCounter.h
Graphlet orbit counting on top of the Escape/EVOKE library.

OrbitCounts
std::vector< std::vector< long long > > OrbitCounts
Graphlet orbit counts of a graph: counts[i][k] is the number of non-induced occurrences of orbit k ro...
Definition OrbitCounter.h:16

computeSymmetryBreaking
SymmetryBreaking computeSymmetryBreaking(const AppGraph &pattern, const OrbitCounts &orbits, const std::vector< int > &order, long long budget=20000000)
Computes the constraints for pattern under the matching order order (node IDs).
Definition Symmetry.cpp:143

AppGraph
Definition AppGraph.h:32

SymmetryBreaking
Symmetry-breaking constraints for counting embeddings (Grochow and Kellis).
Definition Symmetry.h:17

SymmetryBreaking::smaller_than
std::vector< std::vector< int > > smaller_than
smaller_than[w]: the pattern vertices (internal indices) whose image must have a smaller data node ID...
Definition Symmetry.h:20

SymmetryBreaking::work
long long work
Work units spent, against the budget.
Definition Symmetry.h:30

SymmetryBreaking::levels
int levels
Number of vertices whose orbit contributed constraints.
Definition Symmetry.h:25

SymmetryBreaking::multiplier
uint64_t multiplier
Number of embeddings each counted one stands for: the product of the orbit sizes used,...
Definition Symmetry.h:23

SymmetryBreaking::truncated
bool truncated
The work budget ran out, or the multiplier would overflow.
Definition Symmetry.h:28