# 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
- numerics
- permutation and combination
- prime generation and manipulation
- searching and matching
- comparison, distributive, and hybrid sorts

**Everything after still under construction**

- string edit distances
- utility and testing functions
**graph searches****utility graph algorithms****shortest paths for graphs and trees**- linear programming with graphs

- basic linked list
- binary heap
- 2D matrix
- red black tree and augmentations of it
**directed and undirected graphs**

(`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- contest friendly
- paste specific functions in without the rest of the library

Simple implementation of efficient algorithms

- learning friendly
- engineered for readability
- clarity of ideas is top priority
- algorithms with low complexities

## Getting started ¶

- open cmd/terminal and change directory to somewhere in your include path (ex. /usr/local/include)
- type
`git clone --recursive git@github.com:LemonPi/sal.git`

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

- Strong foundation in algorithms and data structures
- C++ implementation experience (creating my own iterators, visitors, and lower level data structures)
- Experience easily expressing ideas in efficient code