Simple Algorithms and Data Structures

Source and quick reference on github
SAL is a C++11 header only library containing simple implementations of efficient algorithms and data structures. Simplicity refers to how close the implementation represents the essence of each concept, leaving out convoluted optimizations.

Detailed documentation with examples of usage for each header follows.

Test algorithms online

Algorithms

Everything after still under construction

Data structures

(namespace sal is implicitely used for every example shown; functions that take iterator pairs are overloaded to take containers as well).

Testing console was compiled with emscripten into javascript. Random test data for some algorithms should be generated with '0' or '1' first; append -p to print full results.

Features

Decoupled algorithms so most files are standalone
Simple implementation of efficient algorithms

Getting started

  1. open cmd/terminal and change directory to somewhere in your include path (ex. /usr/local/include)
  2. type 
    git clone --recursive git@github.com:LemonPi/sal.git
  3. if you missed #2 and cloned it without `--recursive`, get the submodules with `git submodule update --init`

Motivation

While working on my Lisp interpreter, I was introduced to the boost library. It provided the feature I needed (variant) with a flexible interface, but I found the library too cumbersome as a whole. It was impossible to understand conceptual slices of it as they would be optimized into obscurity.

This library is more suited for learning than production usage, or for contests that allow custom libraries. I personally use it for Project Euler problems.

Simplicity Demonstration

Consider Djikstra's algorithm for shortest path in a non-negative directed graph. The pseudo code: 


Dijkstra(G, s)  {
   Initialize-single-source(G, s)
   S ← Ø
   Q ← V[G] // priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}
With direct parallels in the actual code: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

template <typename Graph>
SPM<Graph> dijkstra(const Graph& g, typename Graph::vertex_type s, DJ_visitor&& visitor = {}) {
	using V = typename Graph::vertex_type;
	using Cmp = Shortest_cmp<SPM<Graph>>;
	SPM<Graph> property;
	initialize_single_source(property, g, s);

	// comparator querying on distance

	Heap<V, Cmp> exploring {Cmp{property}};	 /* Q */
	exploring.batch_insert(g.begin(), g.end());

	while (!exploring.empty()) {
		V u {exploring.extract_top()};
		auto edges = g.adjacent(u);
		for (auto v = edges.first; v != edges.second; ++v) 
			visitor.relax(property, exploring, {u, v});
	}

	return property;
}



Initialize-single-source(G, s) {
   for each vertex v in V(G)
      d[v] ← ∞
      p[v] ← NIL
   d[s] ← 0
}

1
2
3
4
5
6

template <typename Property_map, typename Graph>
void initialize_single_source(Property_map& property, const Graph& g, typename Graph::vertex_type s) {
	for (auto v = g.begin(); v != g.end(); ++v) 
		property[*v] = {*v};	/* initially parent is itself, distance is infinity */
	property[s].distance = 0;
}	



Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      p[v] ← u
      update(Q, v)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

struct DJ_visitor {
	/* relaxes an edge if it meets certain requirements */
	template <typename Property_map, typename Queue>
	void relax(Property_map& property, Queue& exploring, 
		const Edge<typename Property_map::key_type, typename Property_map::mapped_type::edge_type>& edge) {
		/*
		   property keeps track of d[] and p[]
		   exploring is Q
		   edge is the (u,v) seen in the pseudo code 
		*/

		size_t d_i {exploring.key(edge.dest())};
		/* d_i == 0 means not in exploring */
		if (d_i && edge.weight() < property[edge.dest()].distance + edge.weight()) {
			property[edge.dest()].distance = property[edge.source()].distance + edge.weight();
			property[edge.dest()].parent = edge.source();
			/* fix heap property */
			exploring.check_key(d_i);
		}		
	}
};

Most of the library maintains this degree of correspondence to fundamental ideas. Optimizations are done if fundamentally changes the behaviour, such as reducing the complexity or removing memory constraints. For example, prime generation is implemented as a segmented sieve rather than a straight forward sieve since it effectively removes memory as a limit on the largest prime I can find.

Gains from Experience