zigrazor / cxxgraph Goto Github PK
View Code? Open in Web Editor NEWHeader-Only C++ Library for Graph Representation and Algorithms
Home Page: https://zigrazor.github.io/CXXGraph/
License: GNU Affero General Public License v3.0
Header-Only C++ Library for Graph Representation and Algorithms
Home Page: https://zigrazor.github.io/CXXGraph/
License: GNU Affero General Public License v3.0
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.
Implementation of Import/Export function in .tsv file
Provide a full Examples implementation.
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.
Implementation of compression mechanism for Import/Export
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
Implement an import/export of Graph in Binary File
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.
It's needed to add the section for Bellman-Ford Algorithm in the Readme.
With an accurate description and useful links to understand it.
Implementation of Bellman–Ford Algorithm
Here we need tests for Thread-Safe Bellman-Ford Algorithm
Here we need benchmark for Floyd-Warshall Algorithm
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.
Introduce the possibility to create .deb package for the library
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.
There is the necessity to write more test on BFS Algorithm.
Specialy on limit case.
Any contribution is appreciated.
Implement an import/export funzionalities in standard file format
Mechanism to create RPM of the library for system Fedora-Like
Create a mechanism to export a tarballs of the library
Introduction of Dial’s Algorithm.
In the README is missing the section for Prim's Algorithm
Implementation of an interface for custom import/export from file
Please add the Topological Sort algorithm for the Graph
Applications of Prim's algorithm
Useful links:
Implementation of Greedy Algorithm for Vertex-cut partiton (possible a one-pass)
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
Benchmarck CI is too long, and the work is stopped after 6h, consider to reduce time
Consider the possibility to install the library on the system
Implementation of Floyd Warshall 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.
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.
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);
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
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)
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)
There is the necessity to write more test on Node class.
Specialy on limit case.
Any contribution is appreciated.
Here we need tests for Thread-Safe Bellman-Ford Algorithm
Here we need to add benchmarck for Bellman-Ford Algorithm
Add Thread Safety to the graph critical operations
There is the necessity to write more test on DFS Algorithm.
Specialy on limit case.
Any contribution is appreciated.
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.
Implementation of Graph Partitioning with HDRF (One-Pass Vertex-Cut Algorithm)
Here we need tests for Thread-Safe Floyd-Warshall Algorithm
There is the necessity to write more test on Edge class.
Specialy on limit case.
Any contribution is appreciated.
There is the necessity to write more test on Graph class.
Specialy on limit case.
Any contribution is appreciated.
Implementation of Ford-Fulkerson Algorithm for Maximum Flow Problem
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.
There is the necessity to write more test on Dial Algorithm.
Specialy on limit case.
Any contribution is appreciated.
you may want to put lib name into the guard (CXXGRAPH_NODE_H), or you'll conflict with all of these guys
There is the necessity to write more test on Djikstra Algorithm.
Specialy on limit case.
Any contribution is appreciated.
There is the necessity to write more test on Cycle Check Algorithm.
Specialy on limit case.
Any contribution is appreciated.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.