bliss: Source Code Documentation  0.73 (Debian 0.73-5)
Public Types | Public Member Functions | Static Public Member Functions | List of all members
bliss::Digraph Class Reference

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

#include <graph.hh>

Inheritance diagram for bliss::Digraph:
bliss::AbstractGraph

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)
 
bool is_automorphism (const std::vector< unsigned int > &perm) const
 
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 source, const unsigned int target)
 
void change_color (const unsigned int vertex, const unsigned int color)
 
int cmp (Digraph &other)
 
void set_splitting_heuristic (SplittingHeuristic shs)
 
Digraphpermute (const unsigned int *const perm) const
 
- Public Member Functions inherited from bliss::AbstractGraph
void set_verbose_level (const unsigned int level)
 
void set_verbose_file (FILE *const fp)
 
void set_failure_recording (const bool active)
 
void set_component_recursion (const bool active)
 
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)
 
void set_long_prune_activity (const bool active)
 

Static Public Member Functions

static Digraphread_dimacs (FILE *const fp, FILE *const errstr=stderr)
 

Additional Inherited Members

- Protected Attributes inherited from bliss::AbstractGraph
unsigned int cr_level
 

Detailed Description

The class for directed, vertex colored graphs.

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

Member Enumeration Documentation

◆ 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

◆ Digraph()

bliss::Digraph::Digraph ( const unsigned int  N = 0)

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

◆ ~Digraph()

bliss::Digraph::~Digraph ( )

Destroy the graph.

Member Function Documentation

◆ add_edge()

void bliss::Digraph::add_edge ( const unsigned int  source,
const unsigned int  target 
)
virtual

Add an edge from the vertex source to the vertex target. 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.

Implements bliss::AbstractGraph.

◆ add_vertex()

unsigned int bliss::Digraph::add_vertex ( const unsigned int  color = 0)
virtual

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

Implements bliss::AbstractGraph.

◆ change_color()

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

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

Implements bliss::AbstractGraph.

◆ cmp()

int bliss::Digraph::cmp ( Digraph other)

Compare this graph with the graph other. Returns 0 if the graphs are equal, and a negative (positive) integer if this graph is "smaller than" ("greater than", resp.) than other.

◆ get_hash()

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

Get a hash value for the graph.

Returns
the hash value

Implements bliss::AbstractGraph.

◆ get_nof_vertices()

unsigned int bliss::Digraph::get_nof_vertices ( ) const
inlinevirtual

Return the number of vertices in the graph.

Implements bliss::AbstractGraph.

◆ is_automorphism()

bool bliss::Digraph::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 from bliss::AbstractGraph.

◆ permute()

Digraph * bliss::Digraph::permute ( const unsigned int *const  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.

◆ read_dimacs()

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
fpthe file stream for the graph file
errstrif 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

◆ set_splitting_heuristic()

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.

◆ write_dimacs()

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
fpthe file stream where the graph is written

Implements bliss::AbstractGraph.

◆ write_dot() [1/2]

void bliss::Digraph::write_dot ( const char *const  file_name)
virtual

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

Parameters
file_namethe name of the file to which the graph is written

Implements bliss::AbstractGraph.

◆ write_dot() [2/2]

void bliss::Digraph::write_dot ( FILE *const  fp)
virtual

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

Parameters
fpthe file stream where the graph is written

Implements bliss::AbstractGraph.


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