vytautas-hermann / sea

Space efficient (graph) algorithms

Space-Efficient
Algorithms

SEA is a project to research and implement an open C++ library for Space-Efficient (Graph) Algorithms (SEA). Besides the running time of algorithms, their space requirements cause a problem if dealing with huge data sets or executing them on tiny devices where memory is heavily limited. Therefore, we want to provide algorithms and data structures to tackle this problem by treating space as a scarce resource.

Table of Contents

• Algorithms and Data Structures
  • Algorithms
  • Data Structures
• Build
• Using the Library
• Project Structure
• Research
• License
• Acknowledgments

Algorithms and Data Structures

This section gives you a brief overview over the implemented algorithms and data structures. For a detailed documentation click on an algorithm. For some data structures and algorithms we also provide a folklore implementation that we use to compare the memory consumption and runtime efficiency.

Algorithms

Algorithm	Runtime	Memory (bits)	Details
Depth First Search	O(n+m)	O(n+m)	here
Depth First Search	O(n+m)	O(n log(log n))	here
Depth First Search	O((n+m) log n)	O((log(3)+ε) n)	here
Reverse DFS	O(n+m)	O(n log(log n))	here
Breadth First Search	O(n+m)	O(n)	here
Cut-Vertex	O(n+m)	O(n+m)	here
Biconnected-Component	O(n+m)	O(n+m)	here
Outerplanar Detection	O(n log(log n))	O(n)	here

Data Structures

• Graph(G = {V, E}): A adjacency list graph representation that occupies O((n + m) log n) bits.
• Bitset: A bitset of n bits that supports access in O(1) time and occupies O(n) bits.
• AVL tree: A self-balancing binary tree with O(log(n)) time for search, insertion and removal of a node.
• Choice Dictionary: A bitset that supports a choice operation in O(1) time that returns the position of a bit set to 1. The choice dictionary occupies O(n) bits.
• Rank-Select: A bit sequence that supports the operations rank(k) and select(k) in O(1) time and occupies O(n) bits. rank(k) returns the number of set bits up to index k, and select(k) returns the index of the k-th set bit.
• Ragged Dictionary: A set of n/log(n) key-value tuples with O(log(log(n))) time for get, insert and remove operations. The ragged dictionary occupies O(n) bits.
• Static-Space Storage: A sequence of n bit packs of variable size that can be accessed in O(1) time and occupies O(n + N) bits. N is the total usable size of the static-space storage.
• Subraph Stack: Initialized with an n-vertex m-edge graph the stack allows to remove vertices and edges and provides a resulting graph using O(n + m) bits.

Build

1. Install CMake and a C++ compiler for your specific operating system.
2. Build a make file for your system by using CMake -> cmake .
3. Build the artifacts by executing make -> make

Now, the include folder contains the necessary header files and the lib folder contains the build library.

If you encounter any bugs, missing or misleading documentation, do not hesitate to create an issue ticket.

Using the Library

• Copy the include/sealib folder into your own project's include path.
• Copy the lib/libsealib.so file into your own project's library path. Make sure that the environment variable LD_LIBRARY_PATH also points there, or else the shared library won't be found.
• Include the header files you want to use in your code.
• Compile with correct -I and -L flags, and use -std=c++11.

Usage example

#include <vector>
#include <sealib/_types.h>
#include <sealib/iterator/dfs.h>
#include <sealib/graph/graphcreator.h>

using namespace Sealib;

bool reachable(DirectedGraph &g, uint64_t a, uint64_t b) {
    bool ret = false;
    std::vector<bool> started(100);
    std::vector<bool> done(100);
    DFS::nloglognBitDFS(g,
                        [&](uint64_t u) {
                            started[u]=1;
                            if (u == b && started[a] && !done[a]) {
                                ret = true;
                            }
                        },
                        DFS_NOP_EXPLORE, DFS_NOP_EXPLORE,
                        [&](uint64_t u) { done[u]=1; });
    return ret;
}

int main(void) {
    DirectedGraph g = GraphCreator::kOutdegree(100, 30);
    return reachable(g, 10, 25);
}

Compile with:

clang++ -I<include-path> -L<libary-path> -std=c++11 -o reachable reachable.cpp -lsealib

Run the executable:

export LD_LIBRARY_PATH=<library-path>
./reachable

Project Structure

.
├── CMakeLists.txt  # CMake build script
├── LICENSE         # Licence description
├── README.md       # You are reading this file now
├── third-party     # Third party libraries
├── include         # The library's header files (*.h)
├── src             # The library's source files (*.cpp)
├── src-view        # The source files for the visualization (*.cpp)
├── test            # The test files
├── lib             # The library files
└── bin             # Executable files to test the project

Research

We publish most of our research on arXiv.org.

• Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. MFCS 2018: 65:1-65:16 | Full Version
• Linear-Time In-Place DFS and BFS on the Word RAM CIAC 2019 (to appear) | Full Version
• A Space-Optimal c-Color Choice Dictionary ISAAC 2018: 66:1-66:12 | Full Version
• Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs MFCS 2016: 56:1-56:14 | Full Version
• Space-Efficient Basic Graph Algorithms STACS 2015: 288-301 | Full Version

License

Licensed under the GNU General Public License version 3. For detailed license information look inside the LICENSE file.

Acknowledgments

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 379157101.