CXXGraph











Introduction
CXXGraph is a comprehensive C++ library that manages graph algorithms. This header-only library serves as an alternative to the
Boost Graph Library (BGL).
CXXGraph Website
We are Looking for
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
or contribute to this project. We are waiting for you!
Table of Contents
- CXXGraph
- Introduction
- We are Looking for
- Table of Contents
- Installation
- Prerequisites
- How to use
- Examples
- Unit-Test Execution
- Install GoogleTest
- How to Compile GoogleTest
- How to Run GoogleTest
- Benchmark Execution
- Install Google Benchmark
- How to Compile Google Benchmark
- How to Run Google Benchmark
- Benchmark Results
- Packaging
- Tarballs
- RPM
- (Fedora/CentOS/RedHat)
- DEB
- (Debian/Ubuntu)
- Algorithms, Classes and Network Dynamics
- Classes
- Network Dynamics
- Algorithms
- Graph Traversal Algorithms
- Shortest Path Algorithms
- Minimum Spanning Tree Algorithms
- Network Flow Algorithms
- Connectivity and Component Detection
- Topological \& Dependency Sorting
- Eulerian Path/Cycle Detection
- Graph Transformation
- Graph Coloring Algorithms
- Partition Algorithms
- How to contribute
- Roadmap
- Stars History
- Contact
- Support
- References
- Credits
- Contributors
- Cited By
- Cite Us
- Other Details
- Author
Installation
Run:
``bash
$ npm i cxxgraph.cxx
`
And then include CXXGraph.hpp as follows:
`cxx
// main.cxx
#include // or, CXXGraph/CXXGraph.hpp
int main() { / ... / }
`
Finally, compile while adding the path node_modules/cxxgraph.cxx to your compiler's include paths.
`bash
$ clang++ -std=c++17 -I./node_modules/cxxgraph.cxx main.cxx # or, use g++
$ g++ -std=c++17 -I./node_modules/cxxgraph.cxx main.cxx
`
You may also use a simpler approach with the cpoach tool, which automatically adds the necessary include paths of all the installed dependencies for your project.
`bash
$ cpoach clang++ -std=c++17 main.cxx # or, use g++
$ cpoach g++ -std=c++17 main.cxx
`
Prerequisites
- 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
How to use
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
Examples
In this example, the shortest path between nodeA and nodeC is obtained using Dijkstra's algorithm.
`cpp
#include
#include
int main(){
CXXGraph::Node nodeA("A", 1);
CXXGraph::Node nodeB("B", 2);
CXXGraph::Node nodeC("C", 3);
CXXGraph::DirectedWeightedEdge edge1("1", nodeA, nodeB, 1);
CXXGraph::DirectedWeightedEdge edge2("2", nodeB, nodeC, 1);
CXXGraph::UndirectedWeightedEdge edge3("3", nodeA, nodeC, 6);
CXXGraph::T_EdgeSet edgeSet;
edgeSet.insert(make_shared>(edge1));
edgeSet.insert(make_shared>(edge2));
edgeSet.insert(make_shared>(edge3));
CXXGraph::Graph 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.
Unit-Test Execution
The Unit-Test requires CMake 3.9 and later, and the GoogleTest library.
$3
GoogleTest
`bash
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 default
`
$3
From the base directory:
`bash
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 # Compile
`
$3
After the build has compiled, run the "test_exe" executable in the "build" directory with the following command:
./test_exe
Benchmark Execution
The Benchmark requires CMake 3.9 and later, the GoogleTest library, and the Google Benchmark library.
$3
Google Benchmark
`bash
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 install
`
$3
From the base directory:
`bash
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 # Compile
`
$3
After the build has compiled, run the "benchmark" executable in the "build" directory with the following command:
./benchmark
$3
You can check the benchmark result using this link.
Packaging
$3
To create a tarball package, execute the following from the command line:
`bash
Enter Packaging Directory
$ cd packaging
Execute the script to generate tarballs
$ ./tarballs.sh
`
$3
#### (Fedora/CentOS/RedHat)
To create an RPM package, execute the following from the command line:
`bash
Enter Packaging Directory
$ cd packaging/rpm
Execute the script to generate tarballs
$ ./make_rpm.sh
`
$3
#### (Debian/Ubuntu)
To create a deb package, execute the following from the command line:
`bash
Enter Packaging Directory
$ cd packaging/deb
Execute the script to generate tarballs
$ ./make_deb.sh
``
Algorithms, Classes and Network Dynamics
Both the Doxygen documentation and the website provide implementation and explanation information on the classes and algorithms of CXXGraph.
#### Classes
The Classes Explanation can be found in the classes section of the Doxygen documentation.
#### Network Dynamics
More information can be found here.
- Adjacency Matrix
- Degree Matrix
- Laplacian Matrix
- Transition Matrix
$3
The following is a list of all the implemented algorithms, more information on the algorithms can be found here.
#### Graph Traversal Algorithms
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Best First Search (a heuristic-based traversal)
- Bron–Kerbosch Algorithm (for finding maximal cliques; DFS-based)
#### Shortest Path Algorithms
- 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)
#### Minimum Spanning Tree Algorithms
- Prim's Algorithm
- Kruskal's Algorithm
- Borůvka's Algorithm
#### Network Flow Algorithms
- Ford–Fulkerson Algorithm (maximum flow)
- Hopcroft–Karp Algorithm (maximum bipartite matching)
#### Connectivity and Component Detection
- 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 & Dependency Sorting
- Topological Sort
- Kahn’s Algorithm (BFS-based topological sorting)
- Tarjan’s Algorithm (DFS-based topological sorting)
#### Eulerian Path/Cycle Detection
- Hierholzer's Algorithm
#### Graph Transformation
- Transitive Reduction (reduce graph to essential edges while preserving reachability)
#### Graph Coloring Algorithms
- Welsh–Powell Coloring Algorithm
#### Partition Algorithms
- Vertex-Cut
- Edge Balanced Vertex-Cut
- Edge Balanced Vertex-Cut based on this paper
- Greedy Vertex-Cut
- High Degree Replicated First
How to contribute

If you want to give your support you can create a pull request  or report an issue .
If you want to change the code, fix an issue, or implement a new feature please read our CONTRIBUTING Guide.
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 
Roadmap
| Completed | Description | Date of Completition |
| :-------: | :---------- | :-------------------: |
| :heavy_check_mark: | Release 0.4.0 | Oct 7, 2022 |
| :heavy_check_mark: | Release 0.5.0 | Mar 23, 2023 |
| :heavy_check_mark: | First Stable Release 1.0.0 | Mar 28, 2023 |
| :heavy_check_mark: | Release 1.0.1 | May 7, 2023 |
| :heavy_check_mark: | Release 1.1.0 | May 8, 2023 |
| :heavy_check_mark: | Stable Release 2.0.0 | Jun 1, 2023 |
| :heavy_check_mark: | Stable Release 3.0.0 | Nov 3, 2023 |
| :heavy_check_mark: | Release 3.1.0 | Jan 9, 2023 |
| :memo: | Introduce Hypergraph #122 | TBD |
| :memo: | Stable Release 4.0.0 | TBD |
Stars History

Contact
E-mail :

GitHub Profile !Profile views
!ZigRazor's github stats
Support
To support me, add a Star to the project  or follow me 
To stay updated, watch the project 
References
We are referenced by:
- awesome-hpp
- cppreference.com
- awesome-cpp
Credits
Thanks to the community of TheAlgorithms for some algorithm inspiration.
Thanks to GeeksForGeeks for some algorithm inspiration.
Contributors
Thank you to all the people who have already contributed to CXXGraph!

Cited By
- 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.
Cite Us
If you use this software please follow the CITATION instructions.
Thank you!
Other Details
We participated in Hacktoberfest 2021, 2022 and 2023. Thank you to all the contributors!
View the Estimated Value of the Project
Author
| 
@ZigRazor |
|:----:|



