Skip to content

Terae/Graph

Repository files navigation

Build Status codecov Codacy Badge CII Best Practices Documentation Github Releases Github license Github Issues

Graph Library

A STL-like graph library written in C++

Design goals

The Graph library is a STL-like library which can be used as an std:: container. The class had these design goals:

  • Intuitive syntax. This container uses all the operator magic of modern C++ to achieve a good feeling in your code.
  • Trivial integration. The whole code consists of a single header file graph.hpp. No library, no subproject, no dependencies, no complex build system. The class is written in vanilla C++11. All in all, everything should require no adjustment of your compiler flags or project settings.
  • Serious testing. This class is heavily unit-tested and covers 100% of the code. Furthermore, I checked with Valgrind that there are no memory leaks. To maintain high quality, the project is following the Core Infrastructure Initiative (CII) best practices.

Integration

The library is header-only. To install and use simply copy the single required file [graph.hpp](https://github.com/terae/graph/blob/dev/single_include/graph.hpp) in your directory. After that, all you need to do is add

#include "graph.hpp"

to the files you want to process Graph.

This library requires also Clang or GCC with -std=c++11 enabled (or other compiler with sufficient C++11 or later support).

That's it.

Documentation

The UML diagram of the library can be found here: doc/diagram.pdf.

Beside the examples below, you may want to check the documentation.

The documentation will be finished once the functionality and interfaces are finalized.

Quickstart example

All example files can be compiled and executed on their own (e.g., file route_finding.cpp)

Once installed, let's initialize a sample graph:

#include "graph.hpp"

using namespace std;

struct Atom {
    char symbol;
    int atomic_number;
    double atomic_weight;
    Atom() = default;
    Atom(char s, int nr, double w) : symbol(s), atomic_number(nr), atomic_weight(w) {}
};

int main() {
    Atom carbon  ('C', 6, 12.01);
    Atom hydrogen('H', 1, 1.01);

    using covalent_bond = int;
    graph<string, Atom, covalent_bond> methane;
    /// Initializing the graph
    methane["C"] = carbon;

    for(int i{1}; i <= 4; ++i)
        methane["H" + to_string(i)] = hydrogen;

    /// Covalent bonds between atoms
    methane("C", "H1") = 1;
    methane("C", "H2") = 1;
    methane("C", "H3") = 1;
    methane("C", "H4") = 1;

    double total_weight{0.0};
    for_each(methane.begin(), methane.end(), [&](decltype(methane)::value_type p) {
        total_weight += p.second->get().atomic_weight;
    });

    cout << "Methane molecule has a molar mass of " << total_weight << " g/mol." << endl;

    return EXIT_SUCCESS;
}

Features

This library is built around the concept of mathematical graph theory (i.e.) it is not a charting library for drawing a graph of a function).

In essence, a graph is a set of nodes with any number of edges in between. Edges can be either undirected ("two-way") or directed ("one-way", aka di-edges). Edges are also allowed to form loops (i.e. an edge from node A pointing to node A again).

Common algorithms

One of the most common things to do with graphs is running algorithms to solve common graph problems. Therefore this library is being used as the basis for implementations for a number of commonly used graph algorithms:

Name Initial Complete? Optimal? Time complexity Space complexity Description
Breadth-First Search BFS YES YES O(b^d) O(b^d) Uses a FIFO queue
Deep-First Search DFS NO NO O(b^m) O(bm) Uses a LIFO queue
Depth-Limited Search DLS NO NO O(b^l) O(bl) Same as DFS with a predetermined depth limit
Iterative-Deepening Depth-First Search IDDFS YES YES O(b^d) O(bd) Benefits combination of BFS and DFS
Uniform-Cost Search UCS YES YES O(b^(1+C*/E)) O(b^(1+C*/E)) Uses a queue ordered by the lowest path cost g(n)
A* A* YES YES O((|V|+|E|)log|V|) Optimally efficient algorithm
Dijkstra Dijkstra YES YES O(|V|) O(|V| * log|V| + |E|) Find the shortest paths between nodes
Bellman-Ford Bellman-Ford YES YES O(|V| * |E|)

Supported compilers

Though it's 2017 already, the support for C++11 is still a bit sparse. Currently, the following compilers are known to work:

  • GCC 5.0 - 7.1 (and possibly later)
  • Clang 3.5 - 5.0 (and possibly later)

Please note that GCC 4.9 and earlier does not work.

The following compilers are currently used in continuous integration at Travis:

Compiler Operating System Version String
GCC 5.4.1 Ubuntu 14.04.5 LTS g++-5 (Ubuntu 5.4.1-2ubuntu1~14.04) 5.4.1 20160904
GCC 6.3.0 Ubuntu 14.04.5 LTS g++-6 (Ubuntu/Linaro 6.3.0-18ubuntu2~14.04) 6.3.0 20170519
GCC 7.2.0 Ubuntu 14.04.5 LTS g++-7 (Ubuntu 7.2.0-1ubuntu1~14.04) 7.2.0
Clang 3.8.0 Ubuntu 14.04.5 LTS clang version 3.8.0-2ubuntu3~trusty5 (tags/RELEASE_380/final)
Clang 3.9.1 Ubuntu 14.04.5 LTS clang version 3.9.1-4ubuntu3~14.04.3 (tags/RELEASE_391/rc2)
Clang 4.0.1 Ubuntu 14.04.5 LTS clang version 3.9.1-4ubuntu3~14.04.3 (tags/RELEASE_401/rc2)

Execute unit tests

To compile and run the tests, you need to execute

$ mkdir build
$ cd build
$ cmake ..
$ cmake --build .
$ ctest

For more information, have a look at the file .travis.yml.

Execute benchmarks

To compile and run the benchmarks, you need to execute

$ mkdir build
$ cd build
$ cmake .. -DENABLE_BENCHMARKING=ON
$ cmake --build .
$ cd benchmarks
$ ./graph_benchmarks

License

This Graph Library is certified Open Source software. It may be used for any purpose, including commercial purposes, at absolutely no cost. It is distributed under the terms of the permissive MIT license reproduced here.

MIT License

Copyright (c) 2017-2018 Benjamin BIGEY

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Used third-party tools

The library itself contains of a single header file licensed under the MIT license. However, it is build, tested and using a lot of third-party tools and services. Thanks a lot!