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.

Sign up for GitHub

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

Jump to bottom

Fix incorrectly copied code #405

Merged
merged 1 commit into from
Mar 19, 2024
Merged

Fix incorrectly copied code #405

merged 1 commit into from
Mar 19, 2024

Conversation

bbannier
Copy link
Contributor

This code looks like it was incorrectly copied from the outEdges overload for pointers. The test suite fails and ultimately segfaults for me, so I did not add an accompanying test.

@ZigRazor
Copy link
Owner

Yes! When you have done, you can trasform the PR in Ready state.
Thank you in advance!

@ZigRazor ZigRazor added the bug Something isn't working label Mar 19, 2024
@ZigRazor ZigRazor self-requested a review March 19, 2024 08:59
@bbannier bbannier marked this pull request as ready for review March 19, 2024 08:59
@bbannier
Copy link
Contributor Author

I marked the PR ready for review.

That being said, it looks to me that most of the methods inOutEdges or inOutNeighbors are implemented incorrectly for directed graphs. All these methods use the adjacency matrix to access edges, e.g.,

CXXGraph/include/CXXGraph/Graph/Graph_impl.hpp

Lines 715 to 725 in ae9bc56

Graph<T>::inOutEdges(shared<const Node<T>> node) const {
if (cachedAdjMatrix->find(node) == cachedAdjMatrix->end()) {
return std::unordered_set<shared<const Edge<T>>, edgeHash<T>>();
}
auto nodeEdgePairs = cachedAdjMatrix->at(node);
std::unordered_set<shared<const Edge<T>>, edgeHash<T>> outEdges;
for (auto pair : nodeEdgePairs) {
outEdges.insert(pair.second);
}

This works well-enough for undirected graphs where the adjacency matrix is kept symmetric,

CXXGraph/include/CXXGraph/Graph/Graph_impl.hpp

Lines 94 to 121 in ae9bc56

} else {
if (edge->isWeighted().has_value() && edge->isWeighted().value()) {
auto edge_shared = make_shared<UndirectedWeightedEdge<T>>(
*dynamic_cast<const UndirectedWeightedEdge<T> *>(edge));
this->edgeSet.insert(edge_shared);
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
edge_shared->getNodePair().second, edge_shared};
(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
std::move(elem));
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem1 = {
edge_shared->getNodePair().first, edge_shared};
(*cachedAdjMatrix)[edge_shared->getNodePair().second].push_back(
std::move(elem1));
} else {
auto edge_shared = make_shared<UndirectedEdge<T>>(*edge);
this->edgeSet.insert(edge_shared);
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
edge_shared->getNodePair().second, edge_shared};
(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
std::move(elem));
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem1 = {
edge_shared->getNodePair().first, edge_shared};
(*cachedAdjMatrix)[edge_shared->getNodePair().second].push_back(
std::move(elem1));
}
}

For directed graphs the adjacency matrix is not symmetric which means that it cannot be used as-is to obtain incoming edges for a node,

CXXGraph/include/CXXGraph/Graph/Graph_impl.hpp

Lines 76 to 93 in ae9bc56

if (edge->isWeighted().has_value() && edge->isWeighted().value()) {
auto edge_shared = make_shared<DirectedWeightedEdge<T>>(
*dynamic_cast<const DirectedWeightedEdge<T> *>(edge));
this->edgeSet.insert(edge_shared);
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
edge_shared->getNodePair().second, edge_shared};
(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
std::move(elem));
} else {
auto edge_shared = make_shared<DirectedEdge<T>>(*edge);
this->edgeSet.insert(edge_shared);
std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
edge_shared->getNodePair().second, edge_shared};
(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
std::move(elem));
}

@bbannier bbannier mentioned this pull request Mar 19, 2024
Open
@ZigRazor ZigRazor linked an issue Mar 19, 2024 that may be closed by this pull request
Methods inOut* broken for directed graphs #406
Open
@codecov Codecov
Copy link

codecov bot commented Mar 19, 2024

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 97.88%. Comparing base (1b31e63) to head (1a3f4f5).
Report is 15 commits behind head on master.

Additional details and impacted files 
@@            Coverage Diff             @@
##           master     #405      +/-   ##
==========================================
+ Coverage   97.58%   97.88%   +0.29%     
==========================================
  Files          87       87              
  Lines        9492    10063     +571     
  Branches        0      660     +660     
==========================================
+ Hits         9263     9850     +587     
+ Misses        229      213      -16
Flag Coverage Δ
unittests 97.88% <100.00%> (+0.29%) ⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@ZigRazor
Copy link
Owner

@ZigRazor, it looks like many of these CI runs failed because of preexisting issues; please let me know if you want me to change anything.

Don't worry @bbannier it's OK. This issue on CI will be analyzed in a second moment!

@ZigRazor ZigRazor merged commit 994e9b9 into ZigRazor:master Mar 19, 2024
27 of 33 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@ZigRazor ZigRazor ZigRazor approved these changes

Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Methods inOut* broken for directed graphs
2 participants
@bbannier @ZigRazor