zigrazor/cxxgraph

Header-Only C++ Library for Graph Representation and Algorithms

Hi 👋, I'm Zig Razor

I'm a Software Engineer. I love programming, and low level problems. I'm interested in CyberSecurity, Machine Learning, Advanced Algorithms.

• 🔭 I’m currently working on CXXGraph, CXXAutomata and PyStateMachine and MTL

• 🌱 I’m currently learning Graph Partitioning for ML Application

• 👯 I’m looking to collaborate on CXXGraph, CXXAutomata and PyStateMachine and MTL

• 🤝 I’m looking for help with CXXGraph, CXXAutomata and PyStateMachine and MTL

• 👨‍💻 All of my projects are available at Repositories

• 💬 Ask me about C++ Tips and Tricks

• 📫 How to reach me [email protected]

• Follow me on figshare

DEV.to Blog Post

• Mon Oct 09 2023 8:26 AM - Hacktoberfest is ON CXXGraph
• Tue Mar 28 2023 9:54 AM - Revolutionizing Data Processing with CXXGraph: A Comprehensive Guide to Graph Data Structures in C++
• Fri Mar 03 2023 7:16 AM - CXXGraph Library : Header-Only C++ Library for Graph Representation and Algorithms
• Fri Oct 14 2022 6:23 AM - 2 Weeks of Hacktoberfest, How is it going??
• Mon Oct 03 2022 9:40 AM - Hacktoberfest is started, give your contribution!
• Fri Sep 30 2022 1:02 PM - Hacktobefest 2022: My Repo
• Tue May 24 2022 7:48 AM - MicroService Framework in C++
• Fri Feb 25 2022 10:20 AM - MTL First Beta Release
• Fri Feb 18 2022 12:52 PM - Node.js New Project Ideas Discussion
• Thu Feb 03 2022 11:21 AM - Python New Project Ideas Discussion

StackOverflow Post

• Mon Nov 20 2023 9:36 AM - Answer by Zig Razor for Confusion about -c option in bash
• Tue Jun 27 2023 9:32 AM - Answer by Zig Razor for Can I repeat a std::string_view without copying when printing indentation?
• Tue Jun 27 2023 9:21 AM - Answer by Zig Razor for Where and why to use preprocessor macros and directives in C++?
• Mon Jun 26 2023 9:02 AM - Answer by Zig Razor for get Linux Monitor resolution with C
• Wed Jun 21 2023 8:28 AM - Answer by Zig Razor for Out Of Memory happened when there is lots of free memory
• Wed Jun 21 2023 8:13 AM - Answer by Zig Razor for How to reverse last commit in git, when should use git checkout -f, or git restore <filename>
• Wed Jun 21 2023 7:47 AM - Answer by Zig Razor for An error occurred while constructing a 3D vector class
• Wed Jun 21 2023 7:43 AM - Answer by Zig Razor for Github desktop showing a number at branch like #46
• Thu Dec 15 2022 9:52 AM - Answer by Zig Razor for Write a Bash Script to edit a csv file
• Wed Dec 07 2022 9:34 AM - Answer by Zig Razor for In yaml-cpp, can the node tags be used to store custom data?

⚡ Recent Activity

1. ❗ Opened issue #417 in ZigRazor/CXXGraph
2. 🗣 Commented on #415 in ZigRazor/CXXGraph
3. 🎉 Merged PR #23 in ZigRazor/JTaskFlow
4. 🗣 Commented on #416 in ZigRazor/CXXGraph
5. 🔒 Closed issue #415 in ZigRazor/CXXGraph

Connect with me:

Languages and Tools:

 

cxxgraph's Issues

Example Implementation

Provide a full Examples implementation.

Add Test on Node Class

There is the necessity to write more test on Node class.
Specialy on limit case.
Any contribution is appreciated.

Introduce Tests for Thread-Safe Dijkstra algorithm

Here we need tests for Thread-Safe Bellman-Ford Algorithm

Check if a directed graph is connected or not

Some algorithms (like prim) assume that the graph is connected for them to work properly. So, we need to add function for checking graph is connected or not.

Compilation Error on Graph_TS.hpp

After merge the #73, it not compile anymore.

The error is the following:

In file included from /home/runner/work/CXXGraph/CXXGraph/include/CXXGraph.hpp:12,
                 from /home/runner/work/CXXGraph/CXXGraph/test/GraphTest.cpp:2:
/home/runner/work/CXXGraph/CXXGraph/include/Graph/Graph_TS.hpp: In instantiation of ‘const BellmanFordResult CXXGRAPH::Graph_TS<T>::bellmanford(const CXXGRAPH::Node<T>&, const CXXGRAPH::Node<T>&) const [with T = int; CXXGRAPH::BellmanFordResult = CXXGRAPH::BellmanFordResult_struct]’:
/home/runner/work/CXXGraph/CXXGraph/include/Graph/Graph_TS.hpp:323:29:   required from here
/home/runner/work/CXXGraph/CXXGraph/include/Graph/Graph_TS.hpp:326:46: error: ‘bellmanFord’ is not a member of ‘CXXGRAPH::Graph<int>’
  326 |         auto bellford = Graph<T>::bellmanFord(source, target);
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

__NODE_H__ header guard can create conflict

you may want to put lib name into the guard (CXXGRAPH_NODE_H), or you'll conflict with all of these guys

Possibility to create .deb package

Introduce the possibility to create .deb package for the library

Implement statistic results of the partition

Request of implementation of statistic results of the partition.
For example Vertex/Node Replication, Replication Factor, Max and Min load of partitions(balance), and other scores.

Add FP-GraphMiner algorithm

FP-GraphMiner - A Fast Frequent Pattern Mining Algorithm for Network Graphs

A novel Frequent Pattern Graph Mining algorithm, FP-GraphMiner, that compactly
represents a set of network graphs as a Frequent Pattern Graph (or FP-Graph).
This graph can be used to efficiently mine frequent subgraphs including maximal
frequent subgraphs and maximum common subgraphs.

URL: https://www.researchgate.net/publication/235255851

You can take inspiration from this :
https://github.com/TheAlgorithms/Python/blob/master/graphs/frequent_pattern_graph_miner.py

Introduce the Thread-Safe Version of Bellman-Ford Algorithm

As done with other algorithm also the Bellman-Ford algorithm need it's thread safe implementation in the Graph_TS.hpp file.
Add also test for the implementation in the test file.

Graph Partition with Greedy Algorithm

Implementation of Greedy Algorithm for Vertex-cut partiton (possible a one-pass)

Introduce Tests for Thread-Safe Floyd-Warshall algorithm

Here we need tests for Thread-Safe Floyd-Warshall Algorithm

Add Tests on BFS Algorithm

There is the necessity to write more test on BFS Algorithm.
Specialy on limit case.
Any contribution is appreciated.

Error when exporting to Output File with a complete path and not only Filename

When to filename is passed a complete path, the export of Node Features and EdgeWeight goes wrong.

Suggest:
Maybe is possible to specify a working root (export root) , and then the filename

Mechanism to install the library

Consider the possibility to install the library on the system

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.

Add Tests on DFS Algorithms

There is the necessity to write more test on DFS Algorithm.
Specialy on limit case.
Any contribution is appreciated.

Add Tarjan's algorithm

Tarjan's algorithm for finding strongly connected components in a directed graph
Uses two main attributes of each node to track reachability, the index of that node
within a component(index), and the lowest index reachable from that node(lowlink).
We then perform a dfs of the each component making sure to update these parameters
for each node and saving the nodes we visit on the way.
If ever we find that the lowest reachable node from a current node is equal to the
index of the current node then it must be the root of a strongly connected
component and so we save it and it's equireachable vertices as a strongly
connected component.

Dial’s Algorithm (Optimized Dijkstra for small range weights)

Introduction of Dial’s Algorithm.

Implementation of compression mechanism for Import/Export

Implementation of compression mechanism for Import/Export

Missing Documentation on README for Prim's algorithm

In the README is missing the section for Prim's Algorithm

Readme for Bellman-Ford Algorithm

It's needed to add the section for Bellman-Ford Algorithm in the Readme.
With an accurate description and useful links to understand it.

Add Tests to Djikstra Algorithm

There is the necessity to write more test on Djikstra Algorithm.
Specialy on limit case.
Any contribution is appreciated.

Add Some example in the "Example" Section of the README.md

Please add some good example in the Example Section.
The desired is that there is the basic example of use of the library and then subsection for each algorithm.
Please add also a good explanation for example code.

Add benchmark for Floyd-Warshall algorithm

Here we need benchmark for Floyd-Warshall Algorithm

Ford-Fulkerson Algorithm for Maximum Flow Problem

Implementation of Ford-Fulkerson Algorithm for Maximum Flow Problem

Import/export of Graph in Binary File

Implement an import/export of Graph in Binary File

Prim's algorithm for finding minimum spanning tree

Applications of Prim's algorithm

• Traveling Salesman Problem
• If you want to connect several cities using highways or rail networks, you can use these algos to find the minimum length of roads/railtracks connecting all these cities.
• You want to apply a set of houses with - Electric Power, Telephone Lines, Sewage Lines.

Useful links:

• https://en.wikipedia.org/wiki/Prim's_algorithm
• https://stackoverflow.com/questions/7320465/applications-of-kruskal-and-prims-algorithms

Introduce Tests for Thread-Safe Bellman-Ford algorithm

Here we need tests for Thread-Safe Bellman-Ford Algorithm

Import/Export in ".tsv" file

Implementation of Import/Export function in .tsv file

Introduce the Thread-Safe Version of Floyd-Warshall Algorithm

As done with other algorithm also the Floyd-Warshall algorithm need it's thread safe implementation in the Graph_TS.hpp file.
Add also test for the implementation in the test file.

Possible deadlock in thread safe algorithms

When I try replacing CXXGRAPH::Graph with CXXGRAPH::Graph_TS in the dijkstra/bellman-ford tests, the algorithm seems to freeze. It could be because of possible deadlock while calling thread safe functions like getNodeSet. The algorithm has already acquired the lock, so when getNodeSet again tries to acquire lock, it results in a dead-lock.
It will be great if someone can investigate and correct the issue.

Add tests on Dial Algorithm

There is the necessity to write more test on Dial Algorithm.
Specialy on limit case.
Any contribution is appreciated.

Import/export to standard file format

Implement an import/export funzionalities in standard file format

Create Rpm for the library

Mechanism to create RPM of the library for system Fedora-Like

Problem with CI automation in benchmark

Benchmarck CI is too long, and the work is stopped after 6h, consider to reduce time

Add Eulerian Path algorithm

Eulerian Path is a path in graph that visits every edge exactly once.
Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
time complexity is O(V+E)
space complexity is O(VE)

Implementation of HDRF Graph Partitioning

Implementation of Graph Partitioning with HDRF (One-Pass Vertex-Cut Algorithm)

Bellman–Ford Algorithm

Implementation of Bellman–Ford Algorithm

Add Borůvka's algorithm

Borůvka's algorithm.

Determines the minimum spanning tree (MST) of a graph using the Borůvka's algorithm.
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a
connected graph, or a minimum spanning forest if a graph that is not connected.
The time complexity of this algorithm is O(ELogV), where E represents the number
of edges, while V represents the number of nodes.
O(number_of_edges Log number_of_nodes)
The space complexity of this algorithm is O(V + E), since we have to keep a couple
of lists whose sizes are equal to the number of nodes, as well as keep all the
edges of a graph inside of the data structure itself.
Borůvka's algorithm gives us pretty much the same result as other MST Algorithms -
they all find the minimum spanning tree, and the time complexity is approximately
the same.
One advantage that Borůvka's algorithm has compared to the alternatives is that it
doesn't need to presort the edges or maintain a priority queue in order to find the
minimum spanning tree.
Even though that doesn't help its complexity, since it still passes the edges logE
times, it is a bit simpler to code.
Details: [Wikipedia](https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm)

Implement Graph Topological Sort

Please add the Topological Sort algorithm for the Graph

Add Tests On Graphs

There is the necessity to write more test on Graph class.
Specialy on limit case.
Any contribution is appreciated.

Add Benchmark for Bellman-Ford Algorithm

Here we need to add benchmarck for Bellman-Ford Algorithm

Thread Safety

Add Thread Safety to the graph critical operations

Tarballs of the library

Create a mechanism to export a tarballs of the library

Add Test on Cycle Check Algorithm

There is the necessity to write more test on Cycle Check Algorithm.
Specialy on limit case.
Any contribution is appreciated.

Add Tests on Edge Class

There is the necessity to write more test on Edge class.
Specialy on limit case.
Any contribution is appreciated.

Custom export and import

Implementation of an interface for custom import/export from file

Floyd Warshall Algorithm

Implementation of Floyd Warshall Algorithm

Not removed non compressed files when compression is flagged

When the compress flag is set, i expect that the file not compressed are removed or never written, but it remains in the written in the location.
Please consider to remove it after the compression or never write them.