5.2. canonicalization.hpp

Full path: graph_canon/canonicalization.hpp

template<typename SizeTypeT, bool ParallelEdgesV, bool LoopsV, typename GraphT, typename IndexMapT, typename EdgeHandlerT>
class config

A helper-class for holding type aliases.

using SizeType = SizeTypeT

The integer type used as element type in arrays.

static constexpr bool ParallelEdges = ParallelEdgesV

Indicator for whether the graph can have parallel edges.

static constexpr bool Loops = LoopsV

Indicator for whether the graph can have loop edge.

using Graph = GraphT

The graph type given as input.

using IndexMap = IndexMapT

The type of boost::ReadablePropertyMap that maps vertices to indices.

using EdgeHandler = EdgeHandlerT

The type of EdgeHandler used.

using Partition = detail::partition<SizeType>

The type of ordered partition used.

using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor

using Edge = typename boost::graph_traits<Graph>::edge_descriptor

template<typename ConfigT, typename VisitorT>
class canon_state

A class template representing he state of a canonicalization run. A reference to an object of this class will be passed to almost all functions in plugins. Note that the user is not supposed to instantiate an object of this class manually.

type Vis

The type of the complete Visitor type used.

type SizeType

The integer type used as element type in various arrays.

type Graph

The type of the input graph.

type IndexMap

The ReadablePropertyMap given to map vertices to indices.

type EHandler

The EdgeHandler type used.

static constexpr bool ParallelEdges

Configuration value for whether the given graph may have parallel edges or not.

static constexpr bool Loops

Configuration value for whether the given graph may have loop edges or not.

type Partition

The type of OrderedPartition used in the algorithm.

using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor

using Edge = typename boost::graph_traits<Graph>::edge_descriptor

using Perm = std::vector<SizeType>

The type of perm_group::Permutation returned from the algorithm

type TreeNode

The type used for instantiating tree nodes.

type OwnerPtr

A smart-pointer type that keeps a tree node alive (e.g., by reference counting).

type InstanceData

Instance data defined, e.g., by visitors, is all stored in an object of this type

void report_leaf(OwnerPtr node)

Submit a tree node as a valid leaf of the search tree.

Requires that the ordered partition represented by node is discrete, and that report_leaf has not been called before with this node.

Several Visitor methods may be called from this function:

• Visitor::tree_leaf, always called.

• Visitor::canon_new_best, if this node will be the best candidate leaf afterwards.

• Visitor::automorphism_leaf, if this node represents a canonical representation, equal to the current best candidate.

• Visitor::canon_worse, if this nodes represents a worse representation than the current best candidate.

void prune_canon_leaf()

Prune the current best candidate. Requires that at least one leaf will be added with repoort_leaf later.

TreeNode *get_canon_leaf() const

Returns

a pointer to the tree node representing the current best candidate.

const Graph &g

The input graph.

const SizeType n = num_vertices(g)

const IndexMap idx

The given ReadablePropertyMap that maps vertices to indices.

InstanceData data

The aggregated data structure holding all instance data. Use get(my_tag(), data) to access your data, tagged with some tag my_tag.

EHandler &edge_handler

A reference to the EdgeHandler used for this run.

Vis visitor

The complete Visitor used.

OwnerPtr root

A pointer to the root of the search tree. Note that this pointer is only set after the root has been fully constructed. Thus, in Visitor methods, if root is nullptr, then you have probably been given a reference to the root as the current tree node.

template<typename SizeType, typename EdgeHandlerCreatorT, bool ParallelEdges, bool Loops>
class canonicalizer

A reusable function object for canonicalizing graphs.

Requires SizeType to be an integer type and EdgeHandlerCreatorT to be an EdgeHandlerCreator.

using EdgeHandler = typename EdgeHandlerCreatorT::template type<SizeType>

canonicalizer(EdgeHandlerCreatorT edge_handler_creator)

template<typename Graph, typename IndexMap, typename VertexLess, typename Vis>
auto operator()(const Graph &g, IndexMap idx, VertexLess vertex_less, Vis visitor)

Compute a permutation that permutes the indices of the vertices of g into their canonical indices.

Requires:

• Graph must be a VertexListGraph, an EdgeListGraph, and a BidirectionalGraph.

• IndexMap must be a ReadablePropertyMap that maps the vertices of g into contiguous indices starting from 0.

• VertexLess must be a less-than predicate on the vertices of g that induces a strict weak ordering. The resulting canonical vertex order respects the ordering induced by vertex_less.

• Vis must be a Visitor type. Note that an invariant_coordinator is automatically prepended to the given visitor.

Note

Currently the expression vertex(i, g) for a vertex index i is also required to be valid, and returning the corresponding vertex descriptor. It must be the inverse of the index map idx. This requirement will be lifted in a future version.

Returns

A std::pair<std::vector<SizeType>, Data> where first is the permutation, and second is the auxiliary visitor data of an unspecified type Data. See each visitor for what data they may return and what it is tagged with. Use get(the_tag(), res.second) to access the data tagged with the_tag from the return value res.

template<typename SizeType, bool ParallelEdges, bool Loops, typename Graph, typename IndexMap, typename VertexLess, typename EdgeHandlerCreatorT, typename Visitor>
auto canonicalize(const Graph &graph, IndexMap idx, VertexLess vertex_less, EdgeHandlerCreatorT edge_handler_creator, Visitor visitor)

A shorhand function for canonicalization. The SizeType, ParallelEdges, and Loops must be specified explicitly while remaining template parameters can be deduced.

See canonicalizer::operator().