Loading...
Searching...
No Matches
bliss::Graph Class Reference

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

`#include <graph.hh>`

Inheritance diagram for bliss::Graph:
[legend]

## Classes

class | Vertex

## Public Types

enum | SplittingHeuristic { shs_f = 0 , shs_fs , shs_fl , shs_fm , shs_fsm , shs_flm }

## Public Member Functions

| Graph (const unsigned int N=0)
| ~Graph ()
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
Graph * | permute (const unsigned int *const perm) const
Graph * | permute (const std::vector< unsigned int > &perm) const
bool | is_automorphism (unsigned int *const perm) const
bool | is_automorphism (const std::vector< unsigned int > &perm) const
unsigned int | add_vertex (const unsigned int color=0)
void | add_edge (const unsigned int v1, const unsigned int v2)
unsigned int | get_color (const unsigned int vertex) const
void | change_color (const unsigned int vertex, const unsigned int color)
Graph * | copy () const
int | cmp (Graph &other)
void | set_splitting_heuristic (const SplittingHeuristic shs)
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, const std::function< void(unsigned int n, const unsigned int *aut)> &report=nullptr, const std::function< bool()> &terminate=nullptr)
const unsigned int * | canonical_form (Stats &stats, const std::function< void(unsigned int n, const unsigned int *aut)> &report=nullptr, const std::function< bool()> &terminate=nullptr)
void | set_long_prune_activity (const bool active)

## Static Public Member Functions

static Graph * | read_dimacs (FILE *const fp, FILE *const errstr=stderr)

## Detailed Description

The class for undirected, vertex colored graphs.

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

## Member Enumeration Documentation

## SplittingHeuristic

enum bliss::Graph::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

## Graph()

bliss::Graph::Graph | ( | const unsigned int | N = 0 | ) |

Create a new graph with N vertices and no edges.

## ~Graph()

bliss::Graph::~Graph | ( |  | ) |

Destroy the graph.

## Member Function Documentation

## add_edge()

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

virtual

Add an edge between vertices v1 and v2. 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.

Implements bliss::AbstractGraph.

## add_vertex()

unsigned int bliss::Graph::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.

## 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 )

inherited

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

void bliss::Graph::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::Graph::cmp | ( | Graph & | other | ) |

Compare this graph to the other graph in a total orger on graphs.

Returns
  0 if the graphs are equal, -1 if this graph is "smaller than" the other, and 1 if this graph is "greater than" the other.

## copy()

Graph * bliss::Graph::copy | ( |  | ) | const

Get a copy of the graph.

## 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 )

inherited

Find a set of generators for the automorphism group of the graph. The function report (if non-null) 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()

unsigned int bliss::Graph::get_color | ( | const unsigned int | vertex | ) | const

virtual

Get the color of a vertex.

Implements bliss::AbstractGraph.

## get_hash()

unsigned int bliss::Graph::get_hash | ( |  | ) |

virtual

Get a hash value for the graph.

Returns
  the hash value

Implements bliss::AbstractGraph.

## get_nof_vertices()

unsigned int bliss::Graph::get_nof_vertices | ( |  | ) | const

inline virtual

Return the number of vertices in the graph.

Implements bliss::AbstractGraph.

## is_automorphism() [1/2]

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

virtual

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

Implements bliss::AbstractGraph.

## is_automorphism() [2/2]

bool bliss::Graph::is_automorphism | ( | unsigned int *const | perm | ) | const

virtual

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

Implements bliss::AbstractGraph.

## permute() [1/2]

Graph * bliss::Graph::permute | ( | const std::vector< 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.

## permute() [2/2]

Graph * bliss::Graph::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()

Graph * bliss::Graph::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 Graph object or 0 if reading failed for some reason

## set_component_recursion()

void bliss::AbstractGraph::set_component_recursion | ( | const bool | active | ) |

inline inherited

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 inherited

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 inherited

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

void bliss::Graph::set_splitting_heuristic | ( | const 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.

## set_verbose_file()

void bliss::AbstractGraph::set_verbose_file | ( | FILE *const | fp | ) |

inherited

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

inherited

Set the verbose output level for the algorithms.

Parameters

  level | the level of verbose output, 0 means no verbose output

## write_dimacs()

void bliss::Graph::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.

Implements bliss::AbstractGraph.

## write_dot() [1/2]

void bliss::Graph::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_name | the name of the file to which the graph is written

Implements bliss::AbstractGraph.

## write_dot() [2/2]

void bliss::Graph::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.

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

- src/graph.hh
- src/graph.cc