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.

Header file: sneaker/algorithm/tarjan.h

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.