-
Notifications
You must be signed in to change notification settings - Fork 115
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Use Adjacency Matrix to populate the nodeSet. #367
Comments
Hi there, how can I contribute to this, where can I get started? |
@nrkramer @sbaldu can you give some help to @badumbatish ? |
If the graph is undirected then we can same some execution time by only checking the upper triangle of the adj matrix, because other triangle will be identical but inverted. In other words you could iterate over the adj matrix, and if a source node (which is the key of the map) has already been added to the nodeSet, you can just skip it. Ps. sorry for the delay |
maybe I'm missing sth but why can't we just iterate over the keys of the adj matrix, which is the |
The keys of the map are the source nodes, and for every source node you have a vector of edge/destination node pairs. If a node is not the source of any link but just a destination, and in directed graphs this can easily happen, you will miss it. |
For a directed edge you only add one element to the adjacency matrix. |
@sbaldu Hi there, i followed your directions and implemented the change on my branch. If the graph is undirected, I just add all source nodes from the adjacency matrix to the nodeSet, together with the isolatedNodeSet.
I'm not sure where I went wrong but some test starts failing: [ FAILED ] BoruvkaTest.test_3 (0 ms) [ RUN ] BoruvkaTest.test_2 [ FAILED ] BoruvkaTest.test_2 (0 ms) Do you have any pointers on approaching this? My fork is https://github.com/badumbatish/CXXGraph |
At present, the getNodeSet() method iterates over all the edges to populate the nodeSet.
A better solution can be to use the adjacency matrix of the graph to populate the nodes.
The text was updated successfully, but these errors were encountered: