CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++.

Overview

CXXGraph

codecov CodeFactor

GitHub license GitHub release

LGTM Alerts LGTM Grade

Generic badge Generic badge Generic badge

Generic badge Generic badge

Share on Tweet







Table of Contents

Introduction

CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".

Algorithm Explanation

Dijkstra

Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path) Dijkstra's Algorithm is used to find the shortest path from a source node to all other reachable nodes in the graph. The algorithm initially assumes all the nodes are unreachable from the given source node so we mark the distances of all nodes as infinity. (infinity) from source node (INF / infinity denotes unable to reach).

Dial

Dial specialization of dijkstra’s algorithm.

When edge weights are small integers (bounded by a parameter C), specialized queues which take advantage of this fact can be used to speed up Dijkstra's algorithm. The first algorithm of this type was Dial's algorithm (Dial 1969) for graphs with positive integer edge weights, which uses a bucket queue to obtain a running time O(|E|+|V|C).(source wikipedia)

Below is complete algorithm:

  1. Maintains some buckets, numbered 0, 1, 2,…,wV.
  2. Bucket k contains all temporarily labeled nodes with distance equal to k.
  3. Nodes in each bucket are represented by list of vertices.
  4. Buckets 0, 1, 2,..wV are checked sequentially until the first non-empty bucket is found. Each node contained in the first non-empty bucket has the minimum distance label by definition.
  5. One by one, these nodes with minimum distance label are permanently labeled and deleted from the bucket during the scanning process.
  6. Thus operations involving vertex include:
    • Checking if a bucket is empty
    • Adding a vertex to a bucket
    • Deleting a vertex from a bucket.
  7. The position of a temporarily labeled vertex in the buckets is updated accordingly when the distance label of a vertex changes.
  8. Process repeated until all vertices are permanently labeled (or distances of all vertices are finalized).

At this link you can find a step-by-step illustrations.

BFS

(Breadth First Search) Breadth First Search Algorithm(Breadth First Search) Breadth First Search, also quoted as BFS, is a Graph Traversal Algorithm. Time Complexity O(|V| + |E|) where V are the number of vertices and E are the number of edges in the graph. Applications of Breadth First Search are :

  1. Finding shortest path between two vertices say u and v, with path length measured by number of edges (an advantage over depth first search algorithm)
  2. Ford-Fulkerson Method for computing the maximum flow in a flow network.
  3. Testing bipartiteness of a graph.
  4. Cheney's Algorithm, Copying garbage collection.

And there are many more...

DFS

(Depth First Search) Depth First Search Algorithm (Depth First Search) Depth First Search, also quoted as DFS, is a Graph Traversal Algorithm. Time Complexity O(|V| + |E|) where V is number of vertices and E is number of edges in graph. Application of Depth First Search are:

  1. Finding connected components
  2. Finding 2-(edge or vertex)-connected components.
  3. Finding 3-(edge or vertex)-connected components.
  4. Finding the bridges of a graph.
  5. Generating words in order to plot the limit set of a group.
  6. Finding strongly connected components.

And there are many more...

Cycle Detection

Cycle (graph theory)

The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.

For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).

Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.

WORK IN PROGRESS

Bellman-Ford

Bellman-Ford Algorithm can be used to find the shortest distance between a source and a target node. Time Complexity O(|V| . |E|) where V is number of vertices and E is number of edges in graph which is higher than Dijkstra's shortest path algorithm. The time complexity of dijkstra's algorithm is O(|E| + |V| log |v| ). The advantage of bellman-ford over dijkstra is that it can handle graphs with negative edge weights. Further, if the graph contains a negative weight cycle then the algorithm can detect and report the presense of negative cycle.

This video gives a nice overview of the algorithm implementation. This MIT lecture gives a proof of Bellman-Ford's correctness & its ability to detect negative cycles. Applications:

  • Distance‐vector routing protocol
  • Routing Information Protocol (RIP)
  • Interior Gateway Routing Protocol (IGRP)

Floyd Warshall

Floyd Warshall Algorithm

We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and updates all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of the source and destination vertices respectively, there are two possible cases.

  1. k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
  2. k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]

Partition Algorithm Explanation

Vertex-Cut

A vertex-cut partitioning divides edges of a graph into equal size partitions. The vertices that hold the endpoints of an edge are also placed in the same partition as the edge itself. However, the vertices are not unique across partitions and might have to be replicated (cut), due to the distribution of their edge across different partitions.

Replication factor quantifies how many vertexes are replicated over computers compared with the the number of vertexes of the original input graph.

Greedy Vertex-Cut

This Algorithm is a simple vertex-cut in Round-Robin fashion. It takes the original graph edges and assign them to the partitions, dividing it in equal(or similar) size. This algorithm does not take care of optimization in vertex replication ( Replication Factor) but only balance the edge in the partitions.

Graph Slicing based on connectivity

Mathematical definition of the problem: Let G be the set of nodes in a graph and n be a given node in that set. Let C be the non-strict subset of G containing both n and all nodes reachable from n, and let C' be its complement. There's a third set M, which is the non-strict subset of C containing all nodes that are reachable from any node in C'. The problem consists of finding all nodes that belong to C but not to M.

Currently implemented Algorithm:

  • Use DFS to find all nodes reachable from n. These are elements of set C.
  • Initialize C' to be complement of C (i.e. all nodes - nodes that are in C)
  • For all nodes in C', apply DFS and get the list of reachable nodes. This is set M.
  • Finally removes nodes from C that belong to M. This is our solution.

Application:

This algorithm is used in garbage collection systems to decide which other objects need to be released, given that one object is about to be released.

Classes Explanation

The Classes Explanation can be found in the Doxygen Documentation, in the Classes Section

Requirements

The minimun C++ standard required is C++17 and a G++ compiler version greater than 7.3.0.

How to use

The use of the library is very simple, just put the header file where you need!

Unit-Test Execution

The Unit-Test required the CMake version greater than 3.9 and the google test library.

Google Test Installation

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 Test

From the base directory:

mkdir -p build       # Create a directory to hold the build output.
cd build             # Enter the build folder
cmake ..             # Generate native build scripts for GoogleTest.
make                 # Compile

How to Run Test

After the compilation, you can run the executable that is under the "build" directory with the name "test_exe", with the simple command ./test_exe.

Benchmark Execution

The Benchmark required the CMake version greater than 3.9 and the google test and the google benchmark library.

Google Benchmark Installation

Google Benchmark

# Check out the library.
$ git clone https://github.com/google/benchmark.git
# Benchmark requires Google Test as a dependency. Add the source tree as a subdirectory.
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library root directory
$ cd benchmark
# Make a build directory to place the build output.
$ cmake -E make_directory "build"
# Generate build system files with cmake.
$ cmake -E chdir "build" cmake -DCMAKE_BUILD_TYPE=Release ../
# or, starting with CMake 3.13, use a simpler form:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library.
$ cmake --build "build" --config Release
# install library
$ sudo cmake --build "build" --config Release --target install

How to Compile Benchmark

From the base directory:

mkdir -p build       # Create a directory to hold the build output.
cd build             # Enter the build folder
cmake ..             # Generate native build scripts for GoogleTest.
make                 # Compile

How to Run Benchmark

After the compilation, you can run the executable that is under the "build" directory with the name "benchmark", with the simple command ./benchmark.

Benchmark Results

You can check benchmark result at this link

Packaging

Tarballs

To create tarballs package you need to follow the following steps:

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

RPM

(Fedora/CentOS/RedHat)

To create rpm package you need to follow the following steps:

# Enter Packaging Directory
$ cd packaging/rpm
# execute the script to generate tarballs
$ ./make_rpm.sh

DEB

(Debian/Ubuntu)

To create deb package you need to follow the following steps:

# Enter Packaging Directory
$ cd packaging/deb
# execute the script to generate tarballs
$ ./make_deb.sh

Install and Uninstall

Install Linux Tarballs

On Unix/Linux system you need to execute the following command to install:

$ sudo tar xjf CXXGraph-{version}.tar.bz2

to uninstall:

$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*

Install RPM

On Fedora/CentOS/RedHat system you need to execute the following command to install:

$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm

to uninstall:

$ sudo rpm -e CXXGraph-{version}

Install DEB

On Debian/Ubuntu system you need to execute the following command to install:

$ sudo dpkg -i CXXGraph_{version}.deb

to uninstall:

$ sudo apt-get remove CXXGraph

Install From Source

You can install from source the library using CMake. After the compilation phase, you can use:

$ sudo make install

to install the library.

Example

Work in Progess

How to contribute

GitHub contributors If you want give your support you can create a pull request GitHub pull-requests or report an issue GitHub issues. If you want to change the code, or fix issue, or implement a new feature please read our CONTRIBUTING Guide

Site

CXXGraph Site

Contact

E-Mail : [email protected]

GitHub Profile Profile views

ZigRazor's github stats

Support

To support me just add Star the project GitHub stars or follow me GitHub followers

To get updated watch the project GitHub watchers

References

We are referenced by:

Credits

Thanks to the community of TheAlgorithms for some algorithms ispiration.

Thanks to GeeksForGeeks for some algorithms inspiration.

Hacktoberfest 2k21

We participate at Hacktoberfest 2021, if you want to contribute, you can take an issue and solve it, or if you want to add a functionalities just open a PR with the label hacktoberfest.

Happy Hack!

We are Looking for...

We are looking for developers and committer, also at first experience, we will guide you step by step to the open-source world! If you are interested, please contact us at [email protected] or contribute to this project. We are waiting for you!

Other Details

View the Estimated Value of the Project

Comments
  • add multithread-bfs

    add multithread-bfs

    • implement multi-thread bfs
    • add test cases for multi-thread bfs(in BFSTest.cpp)
    • add benchmark for multi-thread bfs(in BFS_BM.cpp)

    I actually implement a much more simple multithread-bfs with OpenMP at first, which is very similar to the pseudocode of the paper from the corresponding issue. But there are two problems with that version of implementation:

    • pseudo-multi-thread (parameter num_threads = 1) has a performance advantage over true multi-thread in each benchmark test, even when a graph is large.
    • it forces users to load the OpenMP package when they compile their projects

    Finally, I change the code to a version with std::threads using condition_variable to synchronize threads and do some code optimization. Although the result of the benchmark is still not good as I expected, at least in the CitHepPh graph true multi-thread performs better than pseudo-multi-thread. 3U5MK3ALBi

    test core repo 
    opened by suncanghuai 9
  • Implement best first search

    Implement best first search

    Closes #239 Implement best first search algorithm and tests. @ZigRazor This is my first PR and it's not complete yet. I am working on the documentation and I am happy to get some early feedback, thanks.

    test core 
    opened by pradkrish 8
  • Bug found in RWOutputTest test_22 and test_25 (at least)

    Bug found in RWOutputTest test_22 and test_25 (at least)

    Those 2 tests supposedly check that compressed files are created (.csv.gz and tsv.gz) and the normal .csv and .tsv are not. This is checked via ASSERT_FALSE(exists_test(filename)).

    If we run test_exe and check the content in the folder, we can see that .csv and .tsv files have been created, exist in the folder and the test still passes. This is quite scaring because could be hiding other bugs

    Steps to reproduce the behavior:

    1. Build test_exe
    2. Run ./test_exe and it will pass
    3. Run ls
    4. Check that supposed non-existing files are there and test still passed.

    I would expect both:

    • Files are not created
    • Test fails if files exist

    Test piece of code related to the files - expected results ASSERT_FALSE(exists_test("test_25.tsv")); --> This file exists and it passes = INCORRECT ASSERT_FALSE(exists_test("test_25_NodeFeat.tsv")); --> This file exists and it passes = INCORRECT ASSERT_FALSE(exists_test("test_25_EdgeWeight.tsv")); --> This file exists and it passes = INCORRECT ASSERT_TRUE(exists_test("test_25.tsv.gz")); --> This file exists and it passes = CORRECT ASSERT_TRUE(exists_test("test_25_NodeFeat.tsv.gz")); --> This file exists and it passes = CORRECT ASSERT_TRUE(exists_test("test_25_EdgeWeight.tsv.gz")); --> This file exists and it passes = CORRECT

    bug test Priority:High 
    opened by AlfredCP 8
  • Refactoring: writeToStandardFile and readFromStandardFile

    Refactoring: writeToStandardFile and readFromStandardFile

    Resolves Refactoring: writeToStandardFile_tsv and writeToStandardFile_csv #168

    • The readFromStandardFile_csv and readFromStandardFile_tsv is replaced with readFromStandardFile() with an additional parameter of type InputOutputFormat.
    • The writeToStandardFile_csv and writeToStandardFile_tsv is replaced with writeToStandardFile() with an additional parameter of type InputOutputFormat.

    @ZigRazor @AlfredCP @sidml

    enhancement core 
    opened by pavan-pan 6
  • replace map with unordered_map

    replace map with unordered_map

    Resolves Use Unordered_map instead of map #157 Replaced all the instances of map with unordered_map. For instances of unordered_map where key is a std::pair, an implementation to calculate hash has been provided.

    test core 
    opened by pavan-pan 6
  • Sometimes BellmanFordTest.test_5 fails

    Sometimes BellmanFordTest.test_5 fails

    BellmanFordTest.test_5 fails but not always

    Steps to reproduce:

    • Run tests several times, and som of them it fails under error:
    BellmanFordTest.cpp:170: Failure
    Value of: res.negativeCycle
      Actual: true
    Expected: false
    
    bug test core Priority:High 
    opened by AlfredCP 6
  • Graph Slicing based on connectivity

    Graph Slicing based on connectivity

    Add graph slicing based on connectivity. E.g. given A -> B -> C <- D A -> E -> C -> F and the starting node A: A, B, and E can be sliced off. Mathematical definition of the problem: Let G be the set of nodes in a graph and n be a given node in that set. Let C be the non-strict subset of G containing both n and all nodes reachable from n, and let C' be its complement. There's a third set M, which is the non-strict subset of C containing all nodes that are reachable from any node in C'. The problem consists of finding all nodes that belong to C but not to M.

    The reason why this problem is relevant is because it's used in garbage collection systems to decide which other objects need to be released, given that one object is about to be released.

    enhancement help wanted good first issue development Priority:High hacktoberfest 
    opened by ZigRazor 6
  • Refactoring: writeToStandardFile_tsv and writeToStandardFile_csv

    Refactoring: writeToStandardFile_tsv and writeToStandardFile_csv

    The methods writeToStandardFile_tsv and writeToStandardFile_csv in Graph.hpp have duplicate code. Moving the duplicate code to a common method makes it easier to make future changes. Similar issue with readFromStandardFile_tsv and readFromStandardFile_csv.

    enhancement good first issue core Priority:Low 
    opened by pavan-pan 5
  • Add structs default niitial values

    Add structs default niitial values

    • Resolves https://github.com/ZigRazor/CXXGraph/issues/158
    • Added initial values for the different structs and member variables not to have unexpected behaviors.
    enhancement core 
    opened by AlfredCP 5
  • Floyd Warshall Algorithm

    Floyd Warshall Algorithm

    i am glad to contribute in your repos. i have added the coded for Floyd Warshall Aglorithm. please accept my PR and add the label hacktoberfest-accepted.

    enhancement hacktoberfest 
    opened by BharaniSri10 5
  • Test_11 Failes if it is not the first time being run

    Test_11 Failes if it is not the first time being run

    Afted building tests, test_11 only passes the first time it is run in a clean build

    Steps to reproduce the behavior:

    1. From a clean checkout, follow steps to build tests
    2. Run tests with './test_exe'
    3. All of them will PASS
    4. Run it again
    5. Test_11 will fail

    Expected test pass always

    Suspect that a file is created during a test and it is not clean after the run since it is throwing the following message: "Value of: exists_test("graph.tsv") Actual: true Expected: false"

    enhancement good first issue test Priority:Medium hacktoberfest 
    opened by AlfredCP 4
  • Return type of Kosaraju

    Return type of Kosaraju

    I'm writing some tests for Kosaraju's algorithm (these can potentially close #221), and this made me wonder about kosaraju() return type. Specifically, why does it return a std::vector<std::vector<Node<T>>>?

    Wouldn't it be more appropriate to use std::unordered_set's or something similar? While this could maybe slightly lower the performance, I think it would have much more sense:

    • Kosaraju's algorithm returns the set of strongly connected components, that is, a partition of the vertices of the graph. These are just sets of vertices. And neither the sets in the partition or the vertices in each partition have some special ordering
    • It would be consistent with the T_EdgeSet type (maybe we can even introduce a typedef for a set of vertices)
    • It would allow for easier comparisons between vertex partitions and between individual components

    What do you think about that?

    enhancement good first issue core Priority:Medium 
    opened by dvd2000 3
Releases(v0.4.0)
  • v0.4.0(Oct 7, 2022)

    What's Changed

    • Documentation Update by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/181
    • Introduced New Logo by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/184
    • Added Author by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/185
    • Introduced Boruvka Readme. by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/188
    • Removed Useless Thread Safe Version of Graph. by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/189
    • Introduced Graph Connectivity, also for Prim's Algorithm by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/190
    • Update Image on README.md by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/192
    • Updated README.md with some correction by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/193
    • Test for Graph Connectivity by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/194
    • Updated Readme by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/195
    • Add a Gitter chat badge to README.md by @gitter-badger in https://github.com/ZigRazor/CXXGraph/pull/198
    • 36 ford fulkerson algorithm for maximum flow problem by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/199
    • Optimization ( Partial ) by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/201
    • Added Roadmap to README by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/202
    • Fix Dijkstra can not work with DirectedWeightedEdge #205 by @aengusjiang in https://github.com/ZigRazor/CXXGraph/pull/206
    • Fix errors causing some tests in PartitionTest to fail. by @daniepin in https://github.com/ZigRazor/CXXGraph/pull/207
    • Added One Useful Resource Under Dijkstra Section by @arjunkumar09 in https://github.com/ZigRazor/CXXGraph/pull/210
    • Issue 211 (Add Kosaraju Algorithm) by @sarthak17jain in https://github.com/ZigRazor/CXXGraph/pull/219
    • Benchmark and optimization by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/223
    • correcting spelling and gramatical errors in readme by @thesmartdeveloperr in https://github.com/ZigRazor/CXXGraph/pull/227
    • updated Readme.md. by @Adw8 in https://github.com/ZigRazor/CXXGraph/pull/228
    • Corrected Memory Leak in Partitioning by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/230
    • Preparation for Release 0.4.0 by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/231

    New Contributors

    • @gitter-badger made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/198
    • @aengusjiang made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/206
    • @daniepin made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/207
    • @arjunkumar09 made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/210
    • @sarthak17jain made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/219
    • @thesmartdeveloperr made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/227
    • @Adw8 made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/228

    Full Changelog: https://github.com/ZigRazor/CXXGraph/compare/v0.3.0...v0.4.0

    Download CXXGraph

    Source code(tar.gz)
    Source code(zip)
    CXXGraph-0.4-0.noarch.rpm(39.77 KB)
    CXXGraph-0.4-0.tar.bz2(24.90 KB)
    CXXGraph-0.4-0.zip(51.57 KB)
    CXXGraph_0.4-0.deb(25.01 KB)
  • v0.3.0(Jan 26, 2022)

    What's Changed

    • Partitioning HDRF and Other by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/137
    • Added examples using dijkstra and dial. by @joechai93 in https://github.com/ZigRazor/CXXGraph/pull/176
    • Introduced EBV Partition Algorithm by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/179
    • Release v0.3.0 by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/180

    New Contributors

    • @joechai93 made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/176

    Full Changelog: https://github.com/ZigRazor/CXXGraph/compare/v0.2.2...v0.3.0

    Source code(tar.gz)
    Source code(zip)
    CXXGraph-0.3-0.noarch.rpm(40.23 KB)
    CXXGraph-0.3-0.tar.bz2(24.52 KB)
    CXXGraph-0.3-0.zip(52.62 KB)
    CXXGraph_0.3-0.deb(24.47 KB)
  • v0.2.1(Oct 22, 2021)

    What's Changed

    • Documentation Update by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/50
    • Documentation Update by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/52
    • Update README.md for Hacktoberfest by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/62
    • Fixed typos by @SaloniThete in https://github.com/ZigRazor/CXXGraph/pull/63
    • Update README.md by @sanson-robotics in https://github.com/ZigRazor/CXXGraph/pull/67
    • Add CodeSee architecture diagram workflow to repository by @codesee-architecture-diagrams in https://github.com/ZigRazor/CXXGraph/pull/68
    • Bellman-Ford algorithm by @sidml in https://github.com/ZigRazor/CXXGraph/pull/69
    • Floyd Warshall Algorithm by @sidml in https://github.com/ZigRazor/CXXGraph/pull/72
    • Update README.md by @Sandeep-BlackHat in https://github.com/ZigRazor/CXXGraph/pull/66
    • Thread-Safe version of Bellman-Ford Algorithm by @Dishantdhillon in https://github.com/ZigRazor/CXXGraph/pull/73
    • Thread-Safe version of Floyed-Warshall Algorithm by @Dishantdhillon in https://github.com/ZigRazor/CXXGraph/pull/77
    • add bellman-ford description by @sidml in https://github.com/ZigRazor/CXXGraph/pull/79
    • Graph Slicing based on connectivity by @sidml in https://github.com/ZigRazor/CXXGraph/pull/82
    • Add more tests by @sidml in https://github.com/ZigRazor/CXXGraph/pull/85
    • Update label.yml by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/92
    • Prim's algorithm for finding minimum spanning tree by @sidml in https://github.com/ZigRazor/CXXGraph/pull/89
    • Better Format for README by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/94
    • Delete packaging/deb/CXXGraph/usr directory by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/98
    • added prim's algorithm description. #95 by @oliviacarino in https://github.com/ZigRazor/CXXGraph/pull/96
    • Update CMakeLists.txt by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/97
    • Update README.md by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/99
    • Update benchmark.yml by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/100
    • Tests & Thread safe dijkstra by @sidml in https://github.com/ZigRazor/CXXGraph/pull/93
    • Release version 0.2.0 (2021-10-15) by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/108
    • Documentation Update by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/109
    • Update of Haxelib config file by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/111
    • Union-Find Data Structure by @sidml in https://github.com/ZigRazor/CXXGraph/pull/113
    • Boruvka's Algorithm for MST by @sidml in https://github.com/ZigRazor/CXXGraph/pull/115
    • Adding library name (CXXGRAPH) in header guards to avoid possible conflicts in include folders Node and Graph by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/117
    • Cycle check using Union-Find for Undirected Graphs by @sidml in https://github.com/ZigRazor/CXXGraph/pull/120
    • Update contributing links by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/124
    • Clean up temporary test files by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/126
    • Kruskal's Algorithm for MST by @sidml in https://github.com/ZigRazor/CXXGraph/pull/127
    • Remove intemediate files by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/129
    • Add kruskal algorithm description by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/131
    • Fix prim algorithm link by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/135
    • Add node tests by @AlfredCP in https://github.com/ZigRazor/CXXGraph/pull/136
    • Resolves #106 by @sidml in https://github.com/ZigRazor/CXXGraph/pull/138
    • Update benchmark.yml by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/139
    • Create benchmark_pr.yml by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/141
    • Removed Alert of LGTM for Graph.hpp by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/142

    New Contributors

    • @SaloniThete made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/63
    • @sanson-robotics made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/67
    • @codesee-architecture-diagrams made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/68
    • @sidml made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/69
    • @Sandeep-BlackHat made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/66
    • @Dishantdhillon made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/73
    • @oliviacarino made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/96
    • @AlfredCP made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/117

    Full Changelog: https://github.com/ZigRazor/CXXGraph/compare/v0.1.6...v0.2.1

    Download CXXGraph

    Source code(tar.gz)
    Source code(zip)
  • v0.2.0(Oct 15, 2021)

    What's Changed

    • Documentation Update by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/50
    • Documentation Update by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/52
    • Update README.md for Hacktoberfest by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/62
    • Fixed typos by @SaloniThete in https://github.com/ZigRazor/CXXGraph/pull/63
    • Update README.md by @sanson-robotics in https://github.com/ZigRazor/CXXGraph/pull/67
    • Add CodeSee architecture diagram workflow to repository by @codesee-architecture-diagrams in https://github.com/ZigRazor/CXXGraph/pull/68
    • Bellman-Ford algorithm by @sidml in https://github.com/ZigRazor/CXXGraph/pull/69
    • Floyd Warshall Algorithm by @sidml in https://github.com/ZigRazor/CXXGraph/pull/72
    • Update README.md by @Sandeep-BlackHat in https://github.com/ZigRazor/CXXGraph/pull/66
    • Thread-Safe version of Bellman-Ford Algorithm by @Dishantdhillon in https://github.com/ZigRazor/CXXGraph/pull/73
    • Thread-Safe version of Floyed-Warshall Algorithm by @Dishantdhillon in https://github.com/ZigRazor/CXXGraph/pull/77
    • add bellman-ford description by @sidml in https://github.com/ZigRazor/CXXGraph/pull/79
    • Graph Slicing based on connectivity by @sidml in https://github.com/ZigRazor/CXXGraph/pull/82
    • Add more tests by @sidml in https://github.com/ZigRazor/CXXGraph/pull/85
    • Update label.yml by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/92
    • Prim's algorithm for finding minimum spanning tree by @sidml in https://github.com/ZigRazor/CXXGraph/pull/89
    • Better Format for README by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/94
    • Delete packaging/deb/CXXGraph/usr directory by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/98
    • added prim's algorithm description. #95 by @oliviacarino in https://github.com/ZigRazor/CXXGraph/pull/96
    • Update CMakeLists.txt by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/97
    • Update README.md by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/99
    • Update benchmark.yml by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/100
    • Tests & Thread safe dijkstra by @sidml in https://github.com/ZigRazor/CXXGraph/pull/93
    • Release version 0.2.0 (2021-10-15) by @ZigRazor in https://github.com/ZigRazor/CXXGraph/pull/108

    New Contributors

    • @SaloniThete made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/63
    • @sanson-robotics made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/67
    • @codesee-architecture-diagrams made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/68
    • @sidml made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/69
    • @Sandeep-BlackHat made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/66
    • @Dishantdhillon made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/73
    • @oliviacarino made their first contribution in https://github.com/ZigRazor/CXXGraph/pull/96

    Full Changelog: https://github.com/ZigRazor/CXXGraph/compare/v0.1.6...v0.2.0

    Source code(tar.gz)
    Source code(zip)
    CXXGraph-0.2-0.noarch.rpm(34.38 KB)
    CXXGraph-0.2-0.tar.bz2(19.94 KB)
    CXXGraph_0.2-0.deb(20.07 KB)
  • v0.1.6(Aug 30, 2021)

    Commits

    • 8062ce5: Corrected README Test and Benchmark sections (ZigRazor)
    • b84f162: Update README.md for Packaging (ZigRazor)
    • df17b76: introduced Install/uninstall section on README.md (ZigRazor)
    • 129aeee: Introduced Compression/Decompression for Export/Import (ZigRazor)
    • ec972e6: Merge branch 'master' of https://github.com/ZigRazor/CXXGraph (ZigRazor)
    • 5c91adf: Inserted Header File heading (ZigRazor)
    • 9a7c555: Introduced New Benchmark for remove Edge (ZigRazor)
    • 7daeb9b: Solved a bug where the mutex are locked twice (ZigRazor)
    • 96020a6: Adjustment for new version of Google Benchmark (ZigRazor)
    • 8b6e56b: Fix #48 : (ZigRazor)
    • 69262e6: Documentation update for WriteToFile Function (ZigRazor)
    • d5c0a28: Updated Version to 0.1.6 (ZigRazor)

    Download CXXGraph

    Source code(tar.gz)
    Source code(zip)
    CXXGraph-0.1-6.noarch.rpm(21.27 KB)
    CXXGraph-0.1-6.tar.bz2(12.69 KB)
    CXXGraph_0.1-6.deb(12.68 KB)
    LICENSE(33.71 KB)
    README.md(15.84 KB)
  • v0.1.5(Jul 27, 2021)

    Commits

    • 0441deb: Added installation of lib under /usr/include (ZigRazor)
    • dd36b64: Introduced Script to create tarballs (ZigRazor)
    • ef746b5: Introduced Generation of RPM (ZigRazor)
    • ac6b443: Introduced Packaging for Debian/Ubuntu (ZigRazor)
    • 3860594: Create automatic_tagged_release.yml (ZigRazor)
    • 1a97f7b: Update Version to 0.1.5 (ZigRazor)
    • 8ffb0fb: Documentation Update (#44) (ZigRazor) #44
    • afec411: Update automatic_tagged_release.yml (ZigRazor)
    • 9628bc0: Update Doxyfile (ZigRazor)
    • a6f33d1: Update automatic_tagged_release.yml (ZigRazor)
    • 70ee404: Update Doxyfile (ZigRazor)
    • 1edefbb: Update automatic_tagged_release.yml (ZigRazor)
    • 9312f03: Corrected Spec file (ZigRazor)
    • 1285d8f: Merge branch 'master' of https://github.com/ZigRazor/CXXGraph (ZigRazor)
    Source code(tar.gz)
    Source code(zip)
    CXXGraph-0.1-5.noarch.rpm(20.09 KB)
    CXXGraph-0.1-5.tar.bz2(11.57 KB)
    CXXGraph_0.1-5.deb(11.74 KB)
    LICENSE(33.71 KB)
    README.md(13.62 KB)
  • v0.1.4(Jul 26, 2021)

    Introduced Features

    • Introduced Benchmark
    • Introduced ThreadSafe Class
    • Introduced ThreadSafe Graph Class (Graph_TS)
    • Introduced Dial's Algorithm

    Introduced Tests

    • Introduced Tests for Thread Safe Graph
    • Introduced Tests for Dial's Algorithm

    Fixed Issues

    • #33
    • #37

    Future Developments

    • Implementation of other formats for Import/Export.
    • New Algorthims
    • New Partition Algorithms
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • v0.1.3(Jul 16, 2021)

    Introduced Features

    • Partitioning Statistic, and enhanched Partition class

    Introduced Tests

    • Introduced Tests for Partitioning Statistic

    Fixed Issues

    • #29

    Future Developments

    • Implementation of other formats for Import/Export.
    • New Algorthims
    • New Partition Algorithms
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • v0.1.2(Jul 8, 2021)

    Introduced Features

    • Added Partition with Greedy Vertex.Cut Algorithm

    Introduced Tests

    • Introduced Tests for Partition Algorithm

    Fixed Issues

    • #8

    Future Developments

    • Implementation of other formats for Import/Export.
    • New Algorthims
    • New Partition Algorithms
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • v0.1.1(Jul 7, 2021)

    Introduced Features

    • Added Import/Export from/to .tsv files

    Introduced Tests

    • Introduced Tests for import/export tsv

    Fixed Issues

    • #20

    Future Developments

    • Implementation of other formats for Import/Export.
    • New Algorthims
    • Partition Algorithms
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • v0.1.0(Jul 6, 2021)

    Introduced Features

    • Added Import from .csv files

    Introduced Tests

    • Introduced Tests for import

    Fixed Issues

    • #4

    Resolved Major Bug

    In this realese is solved a major bug that affects the "addEdge" functions. A good rework to substitute std:set with std::list container but manteining the uniqueness of the edge and the node.

    Future Developments

    • Implementation of other formats for Export.
    • New Algorthims
    • Partition Algorithms
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • v0.0.9(Jul 5, 2021)

    Introduced Features

    • Added Working Directory to interface to Export the Graph

    Introduced Tests

    • Adapted Tests to new interface

    Fixed Issues

    • #16

    Future Developments

    • Implementation of other formats for Export.
    • New Algorthims
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • v0.0.8(Jun 30, 2021)

    Introduced Features

    Introduced Export for Standard Output File (.csv) of Node Features and Edge Weights

    Introduced Tests

    Introduced basic Test for Standard Output File (.csv) export

    Future Developments

    • Implementation of other formats for Export.
    • New Algorthims
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • 0.0.7(Jun 28, 2021)

    Introduced Features

    • Introduced basic implementation of writeToFile function.

    Introduced Tests

    • Introduced basic Test for writeToFile

    Future Developments

    • More detailed implementation of csv format for output file and other formats.
    • New Algorthims
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • 0.0.6(Jun 22, 2021)

    Release Version 0.0.6

    Introduced Features

    Introduced Cycle Check for Directed Graph with BFS.
    

    Introduced Tests

    Introduced Test for Cycle Checks
    

    Future Developments

    • New Algorthims
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • 0.0.5(Jun 22, 2021)

    Release Version 0.0.5

    Introduced Features

    Introduced Cycle Check for Directed Graph, DFS.

    Introduced Tests

    Introduced Test for Cycle Checks

    Future Developments

    • New Algorthims
    • More in-depth tests
    Source code(tar.gz)
    Source code(zip)
  • 0.0.4(Oct 16, 2020)

  • 0.0.3(Oct 16, 2020)

    Added BFS algorithm. Tests on BFS. Added Test and some extreme cases correction in the Dijkstra algorithm. Added the funtion that return the node set from the graph and test for this functionalities.

    Source code(tar.gz)
    Source code(zip)
  • 0.0.2(Oct 15, 2020)

  • v0.0-beta.1(Oct 15, 2020)

    This pre-release is a beta with only the base structures for the manage of the Graph in C++. Added the Adjacency Matrix from the Graph. No algorithm over the graph implemented yet.

    Source code(tar.gz)
    Source code(zip)
FDF is a 42 Project to learn about 3d programming. The program takes a map as parameter and creates its 3d representation.

FDF Project Overview FDF is a 42 Project to learn about 3d programming. The program takes a map as parameter and creates its 3d representation. Render

Mmoumni08 7 Dec 1, 2022
Graphlite is a lightweight C++ generic graph library

Introduction Graphlite is a lightweight generic graph library that supports node properties edge properties directed/undirected graphs multi-edges & s

null 52 Aug 14, 2022
C++14 network/graph visualization library / Qt node editor.

QuickQanava QuickQanava is a C++14 library designed to display graphs and relational content in a Qt/QML application. QuickQanava provide QML componen

null 883 Jan 7, 2023
Tiny and efficient graph abstractions.

Tiny and efficient graph abstractions. Usage See tinygraph-example.c Interface See documentation in tinygraph.h Building The tinygraph library require

tinygraph 18 Dec 14, 2022
A standalone Dear ImGui node graph implementation.

ImNodes A standalone Dear ImGui node graph implementation. Library provides core features needed to create a node graph, while leaving it to the user

Rokas Kupstys 548 Dec 15, 2022
A header-only C-like shading language compiler that writes Metal, HLSL, GLSL

GPUC A generic shading language compiler that writes metal, HLSL, and GLSL GPUC is a work in progress, not ready for prime time. The primary motivatio

Garett Bass 61 Oct 18, 2022
ROS package for visualizing Open Motion Planning Library (OMPL) algorithms in 2D with Rviz.

OMPL 2D Rviz Visualizer Visualizing, animating and debugging Open Motion Planning Library (OMPL) algorithms in ROS Rviz. The package allows OMPL plann

Phone Thiha Kyaw 11 Oct 10, 2022
A small cross-platform graphics library made in C

minigfx Small graphics library made in C Intended to be: Simple to understand Intuitive Fun to use Features Cross platform: Windows and Linux. To see

Laurentino Luna 27 Jul 18, 2021
LibGizmo is a small, standalone library that adds a 3D matrix (4x4 floats) manipulation control called 'Gizmo'

LibGizmo is a small, standalone library that adds a 3D matrix (4x4 floats) manipulation control called 'Gizmo'

Cedric Guillemet 128 Dec 16, 2022
Im3d is a small, self-contained library for immediate mode rendering of basic primitives

Im3d is a small, self-contained library for immediate mode rendering of basic primitives (points, lines, triangles), plus an immediate mode UI which provides 3d manipulation 'gizmos' and other tools. It is platform and graphics API agnostic and designed to be compatible with VR.

John Chapman 835 Jan 2, 2023
Horde3D is a small 3D rendering and animation engine. It is written in an effort to create an engine being as lightweight and conceptually clean as possible.

Horde3D Horde3D is a 3D rendering engine written in C++ with an effort being as lightweight and conceptually clean as possible. Horde3D requires a ful

Volker Vogelhuber 1.3k Dec 31, 2022
Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog

In this project, Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog. The input image is stored on a PC and fed to the FPGA. The output processed image is displayed on a VGA monitor.

Jeffrey Samuel 4 Jan 4, 2023
A small dx11 base program I use to test shaders and techniques

Dx11Base A small DirectX 11 program I use to test shaders and techniques (windows only). It is meant to be simple and straightforward. Nothing fancy t

SebH 82 Dec 8, 2022
Single header C library for rendering truetype text to the screen

kc_truetypeassembler.h Single header C library for assembling textured quads for text rendering using a graphics API. It generates a vertices and text

Kevin Chin 24 Nov 12, 2022
This is a single-header, multithreaded C++ library for simulating the effect of hydraulic erosion on height maps.

TinyErode This is a single-header, multithreaded C++ library for simulating the effect of hydraulic erosion on height maps. The algorithm is based on

Taylor 43 Aug 4, 2022
A scratch built kernel original planed to only render a Utah-teapot

teapot-OS (sine wave animation) (first 3d renderer, with mouse controll) Current progress Bootloader enter 32 bit protected mode and run c code Switch

Gustaf franzèn 2 Feb 9, 2022
A modern, feature-rich single header C++ interface system for GLFW

A modern, feature-rich single header C++ interface system for GLFW

Vortex 3 Dec 27, 2021
Single header KTX/DDS reader

dds-ktx: Portable single header DDS/KTX reader for C/C++ @septag Parses from memory blob. No allocations No dependencies Single-header for easy integr

Sepehr Taghdisian 89 Dec 26, 2022