bliss::AbstractGraph Class Reference

An abstract base class for different types of graphs. More...

#include <graph.hh>

Inheritance diagram for bliss::AbstractGraph:

Public Member Functions
void	set_verbose_level (const unsigned int level)
void	set_verbose_file (FILE *const fp)
virtual unsigned int	add_vertex (const unsigned int color=0)=0
virtual void	add_edge (const unsigned int source, const unsigned int target)=0
virtual void	change_color (const unsigned int vertex, const unsigned int color)=0
virtual bool	is_automorphism (const std::vector< unsigned int > &perm) const
void	set_failure_recording (const bool active)
void	set_component_recursion (const bool active)
virtual unsigned int	get_nof_vertices () const =0
virtual AbstractGraph *	permute (const unsigned int *const perm) const =0
void	find_automorphisms (Stats &stats, void(*hook)(void *user_param, unsigned int n, const unsigned int *aut), void *hook_user_param)
const unsigned int *	canonical_form (Stats &stats, void(*hook)(void *user_param, unsigned int n, const unsigned int *aut), void *hook_user_param)
virtual void	write_dimacs (FILE *const fp)=0
virtual void	write_dot (FILE *const fp)=0
virtual void	write_dot (const char *const file_name)=0
virtual unsigned int	get_hash ()=0
void	set_long_prune_activity (const bool active)

Protected Attributes
unsigned int	cr_level

Detailed Description

An abstract base class for different types of graphs.

Member Function Documentation

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

Add a new vertex with color color in the graph and return its index.

Implemented in bliss::Digraph, and bliss::Graph.

canonical_form()

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()).

change_color()

virtual void bliss::AbstractGraph::change_color ( const unsigned int  vertex, const unsigned int  color  )

pure virtual

Change the color of the vertex vertex to color.

Implemented in bliss::Digraph, and bliss::Graph.

find_automorphisms()

void 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.

get_hash()

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

pure virtual

Get a hash value for the graph.

Returns

the hash value

Implemented in bliss::Digraph, and bliss::Graph.

get_nof_vertices()

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

pure virtual

Return the number of vertices in the graph.

Implemented in bliss::Digraph, and bliss::Graph.

is_automorphism()

bool bliss::AbstractGraph::is_automorphism ( const std::vector< unsigned int > &  perm ) const

virtual

Check whether perm is an automorphism of this graph. Unoptimized, mainly for debugging purposes.

Reimplemented in bliss::Digraph, and bliss::Graph.

permute()

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.

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 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.

write_dot() [1/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.

write_dot() [2/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.

Member Data Documentation

cr_level

unsigned int bliss::AbstractGraph::cr_level

protected

The currently traversed component

---

The documentation for this class was generated from the following files:

• graph.hh
• graph.cc