A STL-like graph library written in C++
- Design goals
- Integration
- Documentation
- Quickstart example
- Features
- Common algorithms
- Supported compilers
- Execute unit tests
- Execute benchmarks
- License
- Used third-party tools
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.
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.
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.
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;
}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).
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|) |
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) |
To compile and run the tests, you need to execute
$ mkdir build
$ cd build
$ cmake ..
$ cmake --build .
$ ctestFor more information, have a look at the file .travis.yml.
To compile and run the benchmarks, you need to execute
$ mkdir build
$ cd build
$ cmake .. -DENABLE_BENCHMARKING=ON
$ cmake --build .
$ cd benchmarks
$ ./graph_benchmarksThis 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.
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!
- Artistic Style for format the code
- benchpress to benchmark the code
- Catch for the unit tests
- Clang for compilation with code sanitizers
- Cmake for build automation
- cppcheck for static analysis
- JSON for Modern C++ for [de]serialization of JSON files
- Travis for continuous integration on Linux
- Valgrind to check for correct memory management