Skip to content
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

Open
guru2396 opened this issue Oct 30, 2023 · 7 comments
Open

Use Adjacency Matrix to populate the nodeSet. #367

guru2396 opened this issue Oct 30, 2023 · 7 comments
Labels
core something about core development Development of new Functionalities enhancement New feature or request hacktoberfest hacktoberfest issue Priority:Medium Priority Label for medium priority issue

Comments

@guru2396
Copy link
Contributor

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.

@ZigRazor ZigRazor added enhancement New feature or request development Development of new Functionalities core something about core Priority:Medium Priority Label for medium priority issue hacktoberfest hacktoberfest issue labels Oct 30, 2023
@badumbatish
Copy link
Contributor

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

@ZigRazor
Copy link
Owner

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

@sbaldu
Copy link
Collaborator

sbaldu commented Nov 29, 2023

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
Copy link
Contributor

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
Copy link
Collaborator

sbaldu commented Dec 5, 2023

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
Copy link
Collaborator

sbaldu commented Dec 5, 2023

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
Copy link
Contributor

@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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
core something about core development Development of new Functionalities enhancement New feature or request hacktoberfest hacktoberfest issue Priority:Medium Priority Label for medium priority issue
Projects
None yet
Development

No branches or pull requests

4 participants