An abstract base class for different types of graphs.
More...
#include <graph.hh>
List of all members.
Protected Member Functions |
bool | search (const bool canonical, Stats &stats) |
Protected Attributes |
unsigned int | cr_level |
Detailed Description
An abstract base class for different types of graphs.
Member Function Documentation
const unsigned int * bliss::AbstractGraph::canonical_form |
( |
Stats & |
stats, |
|
|
void(*)(void *user_param, unsigned int n, const unsigned int *aut) |
hook, |
|
|
void * |
hook_user_param |
|
) |
| |
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()). This function returns NULL if there is insufficient memory, or another internal error occurs.
bool bliss::AbstractGraph::find_automorphisms |
( |
Stats & |
stats, |
|
|
void(*)(void *user_param, unsigned int n, const unsigned int *aut) |
hook, |
|
|
void * |
hook_user_param |
|
) |
| |
Find a set of generators for the automorphism group of the graph. The function hook (if non-null) is called each time a new generator for the automorphism group is found. The first argument user_param for the hook is the hook_user_param given below, the second argument n is the length of the automorphism (equal to get_nof_vertices()) and the third 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 hook function; if you want to use the automorphism later, you have to take a copy of it. Do not call any member functions in the hook. The search statistics are copied in stats.
- Returns:
- true if successful, false if insufficient memory to search or other internal error.
virtual unsigned int bliss::AbstractGraph::get_hash |
( |
| ) |
|
|
pure virtual |
virtual unsigned int bliss::AbstractGraph::get_nof_vertices |
( |
| ) |
const |
|
pure virtual |
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.
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,...,N-1}, otherwise the result is undefined or a segfault.
Implemented in bliss::Digraph, and bliss::Graph.
bool bliss::AbstractGraph::search |
( |
const bool |
canonical, |
|
|
Stats & |
stats |
|
) |
| |
|
protected |
- Returns:
- true if successful, false if insufficient memory to complete or other internal error
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 |
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 |
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 |
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 |
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 |
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 N-1. Thus the vertex n in the file corresponds to the vertex n-1 in the API.
- Parameters:
-
fp | the file stream where the graph is written |
Implemented in bliss::Digraph, and bliss::Graph.
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.
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.
Member Data Documentation
unsigned int bliss::AbstractGraph::cr_level |
|
protected |
The currently traversed component
The documentation for this class was generated from the following files: