CXXGraph is a comprehensive C++ library that manages graph algorithms. This header-only library serves as an alternative to the Boost Graph Library (BGL).
We are looking for:
- A Web Developer for the development of the CXXGraph website. All documentation is currently hosted on this GitHub page.
- Developers and Contributors to provide input. If you are new to the open-source world, we will guide you step by step!
If you are interested, please contact us at [email protected] or contribute to this project. We are waiting for you!
- CXXGraph
- Introduction
- We are Looking for...
- Table of Contents
- Install and Uninstall
- Requirements
- How to use
- Examples
- Unit-Test Execution
- Benchmark Execution
- Packaging
- Algorithms, Classes and Network Dynamics
- How to contribute
- Roadmap
- Contact
- Support
- References
- Credits
- Contributors
- Cite Us
- Other Details
- Author
To install on Unix/Linux systems, execute the following from the command line:
$ sudo tar xjf CXXGraph-{version}.tar.bz2
To uninstall:
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
To install on Fedora/CentOS/RedHat systems, execute the following from the command line:
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
To uninstall:
$ sudo rpm -e CXXGraph-{version}
To install on Debian/Ubuntu systems, execute the following from the command line:
$ sudo dpkg -i CXXGraph_{version}.deb
To uninstall:
$ sudo apt-get remove CXXGraph
For self-compiled installations using CMake, execute the following from the command line once compilation is complete:
$ sudo make install
- The minimum C++ standard required is C++17
- A GCC compiler version 7.3.0 and later OR a MSVC compiler that supports C++17
To use the library simply include the header file CXXGraph.hpp, (make sure to add the include folder to your compiler's inlcude path).
CXXGraph revolves around the graph object which contains nodes and edges. This object can then be manipulated with a wide variety of algorithms. Please see the examples section, examples folder and website for more information
In this example, the shortest path between nodeA and nodeC is obtained using Dijkstra's algorithm.
#include <iostream>
#include "CXXGraph/CXXGraph.hpp"
int main(){
CXXGraph::Node<int> nodeA("A", 1);
CXXGraph::Node<int> nodeB("B", 2);
CXXGraph::Node<int> nodeC("C", 3);
CXXGraph::DirectedWeightedEdge<int> edge1(1, nodeA, nodeB, 1);
CXXGraph::DirectedWeightedEdge<int> edge2(2, nodeB, nodeC, 1);
CXXGraph::UndirectedWeightedEdge<int> edge3(3, nodeA, nodeC, 6);
CXXGraph::T_EdgeSet<int> edgeSet;
edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge1));
edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge2));
edgeSet.insert(make_shared<CXXGraph::UndirectedWeightedEdge<int>>(edge3));
CXXGraph::Graph<int> graph(edgeSet);
CXXGraph::DijkstraResult res = graph.dijkstra(nodeA, nodeC);
for(auto node_user_id : res.path){
std::cout << node_user_id << '\n';
}
}See more examples in the examples folder.
The Unit-Test requires CMake 3.9 and later, and the GoogleTest library.
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by defaultFrom the base directory:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # CompileAfter the build has compiled, run the "test_exe" executable in the "build" directory with the following command:
./test_exe
The Benchmark requires CMake 3.9 and later, the GoogleTest library, and the Google Benchmark library.
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory "build"
# Generate the build system files with CMake
$ cmake -E chdir "build" cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build "build" --config Release
# Install the library
$ sudo cmake --build "build" --config Release --target installFrom the base directory:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # CompileAfter the build has compiled, run the "benchmark" executable in the "build" directory with the following command:
./benchmark
You can check the benchmark result using this link.
To create a tarball package, execute the following from the command line:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shTo create an RPM package, execute the following from the command line:
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shTo create a deb package, execute the following from the command line:
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shBoth the Doxygen documentation and the website provide implementation and explanation information on the classes and algorithms of CXXGraph.
The Classes Explanation can be found in the classes section of the Doxygen documentation.
More information can be found here.
- Adjacency Matrix
- Degree Matrix
- Laplacian Matrix
- Transition Matrix
The following is a list of all the implemented algorithms, more information on the algorithms can be found here.
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Best First Search (a heuristic-based traversal)
- Bron–Kerbosch Algorithm (for finding maximal cliques; DFS-based)
- Dijkstra's Algorithm (single-source shortest path, non-negative weights)
- Bellman-Ford Algorithm (handles negative weights)
- Floyd–Warshall Algorithm (all-pairs shortest path)
- Dial's Algorithm (optimized Dijkstra for small integer weights)
- Prim's Algorithm
- Kruskal's Algorithm
- Borůvka's Algorithm
- Ford–Fulkerson Algorithm (maximum flow)
- Hopcroft–Karp Algorithm (maximum bipartite matching)
- Kosaraju's Algorithm (strongly connected components in directed graphs)
- Tarjan's Algorithm (strongly connected components or articulation points)
- Connectivity (general graph connectivity checking)
- Cycle Detection
- Topological Sort
- Kahn’s Algorithm (BFS-based topological sorting)
- Tarjan’s Algorithm (DFS-based topological sorting)
- Hierholzer's Algorithm
- Transitive Reduction (reduce graph to essential edges while preserving reachability)
- Welsh–Powell Coloring Algorithm
- Vertex-Cut
- Edge Balanced Vertex-Cut
- Edge Balanced Vertex-Cut based on this paper
- Greedy Vertex-Cut
- High Degree Replicated First
If you want to discuss new features or you have any questions or suggestions about the library, please open a Discussion or simply chat on
| Completed | Description | Date of Completition |
|---|---|---|
| ✔️ | Release 0.4.0 | Oct 7, 2022 |
| ✔️ | Release 0.5.0 | Mar 23, 2023 |
| ✔️ | First Stable Release 1.0.0 | Mar 28, 2023 |
| ✔️ | Release 1.0.1 | May 7, 2023 |
| ✔️ | Release 1.1.0 | May 8, 2023 |
| ✔️ | Stable Release 2.0.0 | Jun 1, 2023 |
| ✔️ | Stable Release 3.0.0 | Nov 3, 2023 |
| ✔️ | Release 3.1.0 | Jan 9, 2023 |
| 📝 | Introduce Hypergraph #122 | TBD |
| 📝 | Stable Release 4.0.0 | TBD |
E-mail : [email protected]
To support me, add a Star to the project 
To stay updated, watch the project
We are referenced by:
Thanks to the community of TheAlgorithms for some algorithm inspiration.
Thanks to GeeksForGeeks for some algorithm inspiration.
Thank you to all the people who have already contributed to CXXGraph!
- Ruizhe Wang, Meng Xu, and N. Asokan. 2024. SeMalloc: Semantics-Informed Memory Allocator. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security (CCS '24). Association for Computing Machinery, New York, NY, USA, 1375–1389. https://doi.org/10.1145/3658644.3670363
If you use this software please follow the CITATION instructions. Thank you!
We participated in Hacktoberfest 2021, 2022 and 2023. Thank you to all the contributors!
View the Estimated Value of the Project
 @ZigRazor |
|---|
![@dependabot[bot]](https://avatars.githubusercontent.com/in/29110?s=64&v=4){kind=small}
