Skip to content

Latest commit

 

History

History
94 lines (75 loc) · 3.05 KB

readme.md

File metadata and controls

94 lines (75 loc) · 3.05 KB
Raw

Graphs

An open-source modern graph (&trees) library built in C++ for exploring graphs with focus on ease of use.

It uses Google Tests for unit testing and Google Benchmark for benchmarking the library. Measure before optimization.

A clean succinct documentation is available on readthedocs.

Build Status

Features

  • Ease of use.
  • Generic graph representation
  • Inputs are ids of nodes. Or let the nodes be decided automatically by the data structure

Platform

  • CMake
  • C++11
  • Clang
  • Linux (Xenial/Ubuntu 18.04)

Build

As prequisites, CMAKE and git needs to be already installed.

cd graphs
sh install.sh

Data Structures for graph representation

The value of a graph library lies in making it easy to construct and analyze graphs.

  • adjacencyList
  • adjacencyMatrix
  • edgeList
  • (Coming Up) Multiple formats for printing graphs to make it easy to debug them.

Algorithms

  • Traversals (BFS, DFS, Level Order Traversal)
  • Topological Sort
  • Prim's Minimum Spanning Tree
  • Kruskals' Minimum Spanning Tree
  • Dijsktra's Shortest Path Algorithm (May not work for negative edges)
  • Floyd Warshall All Pairs Shortest Path Algorithm
  • Bellman Ford Shortest Path Algorithm (Works for negative edges)

TODO: Upcoming features and algorithms

  • More constructors for all data structures
  • Return list of edges as well as mst cost for minimum spanning tree (mst) queries
  • Connected Components (detect cycles, lca, number of connected components, etc)
  • Lowest Common Ancestor (Single Query and Multiple Query (Binary Uplifting))
  • Tarjan's Strongly Connected Components
  • Is the graph bipartite?
  • Serialization/deserialization

Questions that can be solved by graphs

  • Find dependency between files. Do topological sort on a graph representing files.
  • What is the degree of distance between two people? Just find the shortest distance between two people (the edges should have unit weight).
  • How many connected components are there in the graph?
  • Is there circular dependency in the graph? Or are there loops in the graph?

Sample usage

This section shows usage of dijkstra's algorithm on a directed graph. For more usage, see the sample directory.

#include "src/graphs.h"


int main() {
    edgeList edgeList(true); // directed edge list

    edgeList.add_edge(0, 1, 4);
    edgeList.add_edge(0, 2, 2);
    edgeList.add_edge(1, 2, 5);
    edgeList.add_edge(1, 3, 10);
    edgeList.add_edge(2, 4, 3);
    edgeList.add_edge(4, 3, 4);
    edgeList.add_edge(3, 5, 11);

    auto shortest_distance = dijkstra_shortest_distance(edgeList, 0);
    // Expect shortest distance: {0, 4, 2, 9, 5, 20};

    return 0;
}

Goals

  • Double the speed of the whole library.
  • Reduce memory consumption and memory leaks

Todo Devops

  • Test the library for multiple versions of C++ (14, 17, 20)
  • Test the library on multiple OS (MacOS, Windows)
  • Include Bazel build