Use Adjacency Matrix to populate the nodeSet.

[guru2396]

Use Adjacency Matrix to populate the nodeSet.

[badumbatish]

Hi there, how can I contribute to this, where can I get started?

[ZigRazor]

@nrkramer @sbaldu can you give some help to @badumbatish ?

[sbaldu]

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

[badumbatish]

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?

[sbaldu]

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.

[sbaldu]

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.

[badumbatish]

@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