Algorithms¶

Implementations of advanced algorithms that are handy for solving frequently encountered problems.

Tarjan’s Strongly Connected Graph Algorithm¶

Abstraction that implements Tarjan’s Strongly Connected Graph Algorithm.

class `sneaker::algorithm::``tarjan`<T>

This class is a templated class that takes a type of the encapsulating value in the vertices. The method get_components() takes a list of vertices, assuming that the vertices form the graph in mind. It returns an instance of strongly_connected_component_list, which has information on the independent components as well as cycles in the entire graph.

NOTE: An instance of the class can only perform cycle detection once. Running the method on the same instance more than once will result in inaccurate results.

```#include <sneaker/algorithm/tarjan.h>

/* Tests the following object graph:
* (1) -> (2) -> (3)
* ^             |
* |_____________|
*/

using namespace sneaker::algorithm;

std::vector<tarjan<int>::vertex*> vertices;

tarjan<int>::vertex v1(1);
tarjan<int>::vertex v2(2);
tarjan<int>::vertex v3(3);

v1.dependencies().push_back(&v2);
v2.dependencies().push_back(&v3);
v3.dependencies().push_back(&v1);

vertices.push_back(&v1);
vertices.push_back(&v2);
vertices.push_back(&v3);

tarjan<int> algo;
auto components = algo.detect_cycle(vertices);

// This graph has one component, which is an independent component,
// thus no cycles detected.
assert(1 == components.size());
assert(0 == components.independent_components().size());
assert(1 == components.cycles().size());
```
`typedef std::vector<T> Enumerable`

Type represents each strongly connected component in the graph.

`typedef std::vector<vertex*> VerticesSet`

Type of a set of vertices in the graph.

class `sneaker::algorithm::tarjan<T>::``vertex`

Type represents a vertex in a graph.

`vertex`()

Constructor.

explicit `vertext`(T)

Constructor that takes an instance of the encapsulating type.

type `iterator`

The iterator for the list of neighbor vertices.

bool `operator==`(const vertex&)

Equality operator.

bool `operator!=`(const vertex&)

Inequality operator.

iterator `begin`()

Returns an iterator that points to the beginning of the neighbor vertices.

iterator `end`()

Returns an iterator that points to the end of the neighbor vertices.

int `index`() const

Returns the index value associated with this vertex.

int `lowlink`() const

Returns the low link value associated with this vertex.

T `value`() const

Returns a copy of the encapsulating value.

void `set_index`(int)

Sets the index value of this vertex.

void `set_lowlink`(int)

Sets the low link value of this vertex.

VerticesSet &`dependencies`()

Returns the list of neighbor vertices.

class `sneaker::algorithm::tarjan<T>::``strongly_connected_component_list`

Represents a set of strongly connected components in a directed graph.

`strongly_connected_component_list`()

Constructor.

void `add`(const Enumerable&)

Adds a strongly connected component list to the collection.

size_t `size`() const

Returns the number of strongly connected components in the graph.

std::vector<Enumerable> `independent_components`() const

Gets the set of independent components in the graph.

std::vector<Enumerable> `cycles`() const

Gets the set of cycles in the graph.

`tarjan`()

Constructor.

strongly_connected_component_list `get_components`(const VerticesSet&)

Given a set of vertices in a graph, returns a set of connected components in the graph.