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 |
|:----:|