CXXGraph
CXXGraph copied to clipboard
ZigRazor
Use Adjacency Matrix to populate the nodeSet.
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.
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. On the other hand, if the node is directed I think that it would be more difficult. Any ideas? @nrkramer @ZigRazor
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 shared<const Node<T> and just put that into the newly created set?
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.
template <typename T>
shared<AdjacencyMatrix<T>> Graph<T>::getAdjMatrix() const {
auto adj = std::make_shared<AdjacencyMatrix<T>>();
auto addElementToAdjMatrix = [&adj](shared<const Node<T>> nodeFrom,
shared<const Node<T>> nodeTo,
shared<const Edge<T>> edge) {
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {nodeTo,
edge};
(*adj)[nodeFrom].push_back(std::move(elem));
};
for (const auto &edgeSetIt : edgeSet) {
if (edgeSetIt->isDirected().has_value() &&
edgeSetIt->isDirected().value()) {
shared<const DirectedEdge<T>> d_edge =
std::static_pointer_cast<const DirectedEdge<T>>(edgeSetIt);
addElementToAdjMatrix(d_edge->getNodePair().first,
d_edge->getNodePair().second, d_edge);
} else if (edgeSetIt->isDirected().has_value() &&
!edgeSetIt->isDirected().value()) {
shared<const UndirectedEdge<T>> ud_edge =
std::static_pointer_cast<const UndirectedEdge<T>>(edgeSetIt);
;
addElementToAdjMatrix(ud_edge->getNodePair().first,
ud_edge->getNodePair().second, ud_edge);
addElementToAdjMatrix(ud_edge->getNodePair().second,
ud_edge->getNodePair().first, ud_edge);
} else { // is a simple edge we cannot create adj matrix
return adj;
}
}
return adj;
}
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.
template <typename T>
const T_NodeSet<T> Graph<T>::getNodeSet() const {
T_NodeSet<T> nodeSet;
if (this->isUndirectedGraph() == true) {
for (const auto &[nodeFrom, nodeEdgeVec] : *getAdjMatrix()) {
nodeSet.insert(nodeFrom);
}
} else {
for (const auto &edgeSetIt : edgeSet) {
nodeSet.insert(edgeSetIt->getNodePair().first);
nodeSet.insert(edgeSetIt->getNodePair().second);
}
}
// Merge with the isolated nodes
nodeSet.insert(this->isolatedNodesSet.begin(), this->isolatedNodesSet.end());
return nodeSet;
}
I'm not sure where I went wrong but some test starts failing: [ RUN ] BoruvkaTest.test_3 /home/jjsm/CLionProjects/CXXGraph/test/BoruvkaTest.cpp:152: Failure Expected equality of these values: res.mst.size() Which is: 0 graph.getNodeSet().size() - 1 Which is: 18446744073709551615
[ FAILED ] BoruvkaTest.test_3 (0 ms)
[ RUN ] BoruvkaTest.test_2 /home/jjsm/CLionProjects/CXXGraph/test/BoruvkaTest.cpp:106: Failure Expected equality of these values: res.mst.size() Which is: 0 graph.getNodeSet().size() - 1 Which is: 18446744073709551615
[ FAILED ] BoruvkaTest.test_2 (0 ms)
Do you have any pointers on approaching this? My fork is https://github.com/badumbatish/CXXGraph