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 [email protected] 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:

$ npm i cxxgraph.cxx

And then include CXXGraph.hpp as follows:

// main.cxx
#include <CXXGraph.hpp>  // or, CXXGraph/CXXGraph.hpp

int main() { /* ... */ }

Finally, compile while adding the path node_modules/cxxgraph.cxx to your compiler's include paths.

$ 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.

$ 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.

#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.

Unit-Test Execution

The Unit-Test requires CMake 3.9 and later, and the GoogleTest library.

Install GoogleTest

GoogleTest

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

How to Compile GoogleTest

From 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                 # Compile

How to Run GoogleTest

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.

Install Google Benchmark

Google Benchmark

# 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

How to Compile Google Benchmark

From 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                       # Compile

How to Run Google Benchmark

After the build has compiled, run the "benchmark" executable in the "build" directory with the following command:

./benchmark

Benchmark Results

You can check the benchmark result using this link.

Packaging

Tarballs

To create a tarball package, execute the following from the command line:

# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.sh

RPM

(Fedora/CentOS/RedHat)

To 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.sh

DEB

(Debian/Ubuntu)

To 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.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

Algorithms

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 : [email protected]

GitHub Profile

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. https://doi.org/10.1145/3658644.3670363

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