bliss::Digraph Class Reference

The class for directed, vertex colored graphs. More...

#include <graph.hh>

Inheritance diagram for bliss::Digraph:

List of all members.

Public Types
enum	SplittingHeuristic {   shs_f = 0, shs_fs, shs_fl, shs_fm,   shs_fsm, shs_flm }
Public Member Functions
	Digraph (const unsigned int N=0)
	~Digraph ()
void	write_dimacs (FILE *const fp)
void	write_dot (FILE *const fp)
void	write_dot (const char *const file_name)
virtual unsigned int	get_hash ()
unsigned int	get_nof_vertices () const
unsigned int	add_vertex (const unsigned int color=0)
void	add_edge (const unsigned int v1, const unsigned int v2)
void	change_color (const unsigned int vertex, const unsigned int color)
void	set_splitting_heuristic (SplittingHeuristic shs)
Digraph *	permute (const unsigned int *perm) const
Static Public Member Functions
static Digraph *	read_dimacs (FILE *const fp, FILE *const errstr=stderr)

---

Detailed Description

The class for directed, vertex colored graphs.

Multiple edges between vertices are not allowed (i.e., are ignored).

---

Member Enumeration Documentation

enum bliss::Digraph::SplittingHeuristic

The possible splitting heuristics. The selected splitting heuristics 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 splitting heuristics for both graphs.

Enumerator:

shs_f	First non-unit cell. Very fast but may result in large search spaces on difficult graphs. Use for large but easy graphs.
shs_fs	First smallest non-unit cell. Fast, should usually produce smaller search spaces than shs_f.
shs_fl	First largest non-unit cell. Fast, should usually produce smaller search spaces than shs_f.
shs_fm	First maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.
shs_fsm	First smallest maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.
shs_flm	First largest maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

---

Constructor & Destructor Documentation

bliss::Digraph::Digraph

(

const unsigned int

N = 0

)

Create a new directed graph with N vertices and no edges.

bliss::Digraph::~Digraph

(

)

Destroy the graph.

---

Member Function Documentation

Digraph * bliss::Digraph::read_dimacs	(	FILE *const	fp,
		FILE *const	errstr = stderr
	)			[static]

Read the graph from the file fp 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 for the graph file
	errstr	if non-null, the possible error messages are printed in this file stream

Returns:

a new Digraph object or 0 if reading failed for some reason

void bliss::Digraph::write_dimacs

(

FILE *const

fp

)

[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

Implements bliss::AbstractGraph.

void bliss::Digraph::write_dot

(

FILE *const

fp

)

[virtual]

Write the graph to a file in the graphviz dotty format.

Parameters:

fp

the file stream where the graph is written

Implements bliss::AbstractGraph.

void bliss::Digraph::write_dot

(

const char *const

file_name

)

[virtual]

Write the graph in a file in the graphviz dotty format.

Parameters:

file_name

the name of the file to which the graph is written

Implements bliss::AbstractGraph.

unsigned int bliss::Digraph::get_hash

(

)

[virtual]

Get a hash value for the graph.

Returns:

the hash value

Implements bliss::AbstractGraph.

unsigned int bliss::Digraph::get_nof_vertices

(

)

const [inline, virtual]

Return the number of vertices in the graph.

Implements bliss::AbstractGraph.

unsigned int bliss::Digraph::add_vertex

(

const unsigned int

color = 0

)

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

void bliss::Digraph::add_edge	(	const unsigned int	v1,
		const unsigned int	v2
	)

Add an edge from vertix v1 to vertex v2. Duplicate edges 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.

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

Change the color of the vertex 'vertex' to 'color'.

void bliss::Digraph::set_splitting_heuristic

(

SplittingHeuristic

shs

)

[inline]

Set the splitting heuristic used by the automorphism and canonical labeling algorithm. The selected splitting heuristics 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 splitting heuristics for both graphs.

Digraph * bliss::Digraph::permute

(

const unsigned int *

perm

)

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

Implements bliss::AbstractGraph.

---

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

• graph.hh
• graph.cc

---