An abstract base class for different types of graphs.
More...
#include <abstractgraph.hh>

class  CR_CEP 

struct  PathInfo 

An abstract base class for different types of graphs.
◆ add_edge()
virtual void bliss::AbstractGraph::add_edge 
( 
const unsigned int 
source, 


const unsigned int 
target 

) 
 

pure virtual 
Add an edge between vertices source and target. Duplicate edges between vertices are ignored but try to avoid introducing them in the first place as they are not ignored immediately but will consume memory and computation resources for a while.
Implemented in bliss::Graph, and bliss::Digraph.
◆ add_vertex()
virtual unsigned int bliss::AbstractGraph::add_vertex 
( 
const unsigned int 
color = 0  ) 


pure virtual 
◆ canonical_form()
const unsigned int * bliss::AbstractGraph::canonical_form 
( 
Stats & 
stats, 


const std::function< void(unsigned int n, const unsigned int *aut)> & 
report = nullptr , 


const std::function< bool()> & 
terminate = nullptr 

) 
 
Otherwise the same as find_automorphisms() except that a canonical labeling of the graph (a bijection on {0,...,get_nof_vertices()1}) is returned. The memory allocated for the returned canonical labeling will remain valid only until the next call to a member function with the exception that constant member functions (for example, bliss::Graph::permute()) can be called without invalidating the labeling. To compute the canonical version of an undirected graph, call this function and then bliss::Graph::permute() with the returned canonical labeling. Note that the computed canonical version may depend on the applied version of bliss as well as on some other options (for instance, the splitting heuristic selected with bliss::Graph::set_splitting_heuristic()).
If the terminate function argument is given, it is called in each search tree node: if the function returns true, then the search is terminated and thus (i) not all the automorphisms may have been generated and (ii) the returned labeling may not be canonical. The terminate function may be used to limit the time spent in bliss in case the graph is too difficult under the available time constraints. If used, keep the function simple to evaluate so that it does not consume too much time.
◆ change_color()
virtual void bliss::AbstractGraph::change_color 
( 
const unsigned int 
vertex, 


const unsigned int 
color 

) 
 

pure virtual 
◆ find_automorphisms()
void bliss::AbstractGraph::find_automorphisms 
( 
Stats & 
stats, 


const std::function< void(unsigned int n, const unsigned int *aut)> & 
report = nullptr , 


const std::function< bool()> & 
terminate = nullptr 

) 
 
Find a set of generators for the automorphism group of the graph. The function report (if nonnull) is called each time a new generator for the automorphism group is found. The first argument n for the function is the length of the automorphism (equal to get_nof_vertices()), and the second argument aut is the automorphism (a bijection on {0,...,get_nof_vertices()1}). The memory for the automorphism aut will be invalidated immediately after the return from the report function; if you want to use the automorphism later, you have to take a copy of it. Do not call any member functions from the report function.
The search statistics are copied in stats.
If the terminate function argument is given, it is called in each search tree node: if the function returns true, then the search is terminated and thus not all the automorphisms may have been generated. The terminate function may be used to limit the time spent in bliss in case the graph is too difficult under the available time constraints. If used, keep the function simple to evaluate so that it does not consume too much time.
◆ get_color()
virtual unsigned int bliss::AbstractGraph::get_color 
( 
const unsigned int 
vertex  ) 
const 

pure virtual 
◆ get_hash()
virtual unsigned int bliss::AbstractGraph::get_hash 
( 
 ) 


pure virtual 
◆ get_nof_vertices()
virtual unsigned int bliss::AbstractGraph::get_nof_vertices 
( 
 ) 
const 

pure virtual 
◆ is_automorphism() [1/2]
virtual bool bliss::AbstractGraph::is_automorphism 
( 
unsigned int *const 
perm  ) 
const 

pure virtual 
Check whether perm is an automorphism of this graph. Unoptimized, mainly for debugging purposes.
Implemented in bliss::Digraph, and bliss::Graph.
◆ is_automorphism() [2/2]
virtual bool bliss::AbstractGraph::is_automorphism 
( 
const std::vector< unsigned int > & 
perm  ) 
const 

pure virtual 
Check whether perm is an automorphism of this graph. Unoptimized, mainly for debugging purposes.
Implemented in bliss::Digraph, and bliss::Graph.
◆ permute() [1/2]
virtual AbstractGraph* bliss::AbstractGraph::permute 
( 
const unsigned int *const 
perm  ) 
const 

pure virtual 
Return a new graph that is the result of applying the permutation perm to this graph. This graph is not modified. perm must contain N=this.get_nof_vertices() elements and be a bijection on {0,1,...,N1}, otherwise the result is undefined or a segfault.
Implemented in bliss::Digraph, and bliss::Graph.
◆ permute() [2/2]
virtual AbstractGraph* bliss::AbstractGraph::permute 
( 
const std::vector< unsigned int > & 
perm  ) 
const 

pure virtual 
Return a new graph that is the result of applying the permutation perm to this graph. This graph is not modified. perm must contain N=this.get_nof_vertices() elements and be a bijection on {0,1,...,N1}, otherwise the result is undefined or a segfault.
Implemented in bliss::Digraph, and bliss::Graph.
◆ set_component_recursion()
void bliss::AbstractGraph::set_component_recursion 
( 
const bool 
active  ) 


inline 
Activate/deactivate component recursion. The choice affects the computed canonical labelings; therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same choice for both graphs. May not be called during the search, i.e. from an automorphism reporting hook function.
 Parameters

active  if true, activate component recursion, deactivate otherwise 
◆ set_failure_recording()
void bliss::AbstractGraph::set_failure_recording 
( 
const bool 
active  ) 


inline 
Activate/deactivate failure recording. May not be called during the search, i.e. from an automorphism reporting hook function.
 Parameters

active  if true, activate failure recording, deactivate otherwise 
◆ set_long_prune_activity()
void bliss::AbstractGraph::set_long_prune_activity 
( 
const bool 
active  ) 


inline 
Disable/enable the "long prune" method. The choice affects the computed canonical labelings; therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same choice for both graphs. May not be called during the search, i.e. from an automorphism reporting hook function.
 Parameters

active  if true, activate "long prune", deactivate otherwise 
◆ set_verbose_file()
void bliss::AbstractGraph::set_verbose_file 
( 
FILE *const 
fp  ) 

Set the file stream for the verbose output.
 Parameters

fp  the file stream; if null, no verbose output is written 
◆ set_verbose_level()
void bliss::AbstractGraph::set_verbose_level 
( 
const unsigned int 
level  ) 

Set the verbose output level for the algorithms.
 Parameters

level  the level of verbose output, 0 means no verbose output 
◆ write_dimacs()
virtual void bliss::AbstractGraph::write_dimacs 
( 
FILE *const 
fp  ) 


pure virtual 
Write the graph to a file in a variant of the DIMACS format. See the bliss website for the definition of the file format. Note that in the DIMACS file the vertices are numbered from 1 to N while in this C++ API they are from 0 to N1. Thus the vertex n in the file corresponds to the vertex n1 in the API.
 Parameters

fp  the file stream where the graph is written 
Implemented in bliss::Digraph, and bliss::Graph.
◆ write_dot() [1/2]
virtual void bliss::AbstractGraph::write_dot 
( 
FILE *const 
fp  ) 


pure virtual 
Write the graph to a file in the graphviz dotty format.
 Parameters

fp  the file stream where the graph is written 
Implemented in bliss::Digraph, and bliss::Graph.
◆ write_dot() [2/2]
virtual void bliss::AbstractGraph::write_dot 
( 
const char *const 
file_name  ) 


pure virtual 
Write the graph in a file in the graphviz dotty format. Do nothing if the file cannot be written.
 Parameters

file_name  the name of the file to which the graph is written 
Implemented in bliss::Digraph, and bliss::Graph.
The documentation for this class was generated from the following files: