stdgraph / graph-v2 Goto Github PK
View Code? Open in Web Editor NEWGeneral-purpose C++ graph library
Home Page: https://stdgraph.github.io/graph-v2/
License: Boost Software License 1.0
General-purpose C++ graph library
Home Page: https://stdgraph.github.io/graph-v2/
License: Boost Software License 1.0
This library should not depend on fmt/format.h
, especially that on MSVC there is no reason to include it when we have <format>
.
The parameters for each are dynamic_graph<EV,VV,Sourced,VId,Traits> and csr_graph<EV,VV,VId,Sourced,Traits>. VId follows VV in csr_graph, and Sourced in dynamic_graph. dynamic_graph should be changed so the first 3 parameters match to avoid confusion when using both.
This change should be done sooner rather than later so we don't have to change a larger body of code.
shortest_paths.hpp needs documentation. It will be used as a template for other files.
I am using Microsoft Visual C++ 2022, version 17.3.4, both std C++20, and the experimental newest C++.
The compilation of std::graph::views::edges_breadth_first_search
fails with an error that std::_Fake_copy_init
is not defined. Removing this #ifndef
guard fixes the problem. I can see that other STL implementations (like this one) do have it defined.
Maybe to enable thecompilation on any MSVC build this library should define its own type std::graph::fake_copy_init
independent of the compiler used.
First, thank you for this great work on the world-class graph library!
P1709r4 gives a very promising example of with Bacon number that shows:
But it does not really compile, and trying to fix it does not work for me. I tried applying fixes, but it still won't compile. In fact, even the following code does not compile:
using G = std::vector<std::vector<int>>;
auto target_id(const G& g, std::graph::edge_reference_t<G> uv)
{ return uv; }
static_assert(std::graph::basic_adjacency_list<G>, "non-graph");
And this is because there is no way for me to create an ADL-discoverable funciton target_id
because G
-- as defined in P1709r4 -- is composed only from int
and declarations from the namespace std
, where I am not allowed to put overloads.
Also, the concept seems strange:
template <class G, class E>
concept targeted_edge = requires(G&& g, edge_reference_t<G> uv) {
target_id(g, uv);
target(g, uv);
};
It requires that target_id(g, uv)
exists, but does not require that it returns anything.
But if I nonetheless define target_id
inside namespace std
(which is UB), the following fails to compile:
G costar_adjacency_list{
{1, 5, 6}, {7, 10, 0, 5, 12}, {4, 3, 11}, {2, 11}, {8, 9, 2, 12}, {0, 1}, {7, 0},
{6, 1, 10}, {4, 9}, {4, 8}, {7, 1}, {2, 3}, {1, 4}
};
std::graph::views::sourced_edges_breadth_first_search(costar_adjacency_list, 1);
I get an error:
graph-v2/include/graph/views/breadth_first_search.hpp:73:29: error: no matching function for call to object of type 'const _Vertices::_Cpo'
if (seed < ranges::size(vertices(graph_)) && !ranges::empty(edges(graph_, seed))) {
^~~~~~~~
Is it because I have to provide an overload for vertices(G)
? But do I, given that G
itself is a list of vertices?
One compiling example would help answer all these questions.
Also a usecase for Dijkstra: https://github.com/milasudril/cheapest_route. In this case the graph is implicit. In particular, it will use 32 outgoing search directions. Also, it is not interesting to find the cost from the start pixel to every other pixel. You would rather pick a few pairs, and let the algorithm find a natural way connecting the vertices.
If you had to construct a graph using an adjacency list, you will most likely run out of memory. A solution to this is to make it possible somehow return the edges from a customization point, accepting a customized node id. In this case, the node id has to be the coordinates of the pixel. The cost function must be given two node id:s.
Searching the path to every point in the image is both space and time consuming. Thus, there must be a version of Dijkstra that stops at a requested vertex.
vertex_view, edge_edge_view and neighbor_view are used to determine values for respective object instances. They aren't Views in the context of ranges. This was identified by a review at CppCon 2022. Better names are needed that represent their purpose.
The new names will be vertex_descriptor, edge_descriptor and neighbor_descriptor.
The file they're in should be renamed from views_utility.hpp to graph_utility.hpp (or something similar), and maybe moved to the same directory as graph.hpp.
for (auto&& [uid, u] : views::vertexlist(g)) {
auto deg = degree(g, u);
}
or
for (auto&& u : vertices(g)) {
auto deg = degree(g, u);
}
error: no matching function for call to 'degree(std::graph::container::dynamic_graph<double, std::__cxx11::basic_string<char>, void, false, unsigned int, std::graph::container::vofl_graph_traits<double, std::__cxx11::basic_string<char> > >&, std::graph::container::dynamic_vertex<double, std::__cxx11::basic_string<char>, void, false, unsigned int, std::graph::container::vofl_graph_traits<double, std::__cxx11::basic_string<char> > >&)'
72 | auto deg = degree(g, u);
Specifically, in this piece of code:
graph-v2/include/graph/algorithm/pagerank.hpp
Lines 76 to 82 in c6ed28b
2 styles of Doxygen comments exist in our code and we should change it to be consistent. We've selected the /** ... */ style so all lines that start wtih /// need to be changed.
At BFS and DFS base, the three_color vectors are not follow the passed Allocator type.
https://github.com/stdgraph/graph-v2/blob/master/include/graph/views/breadth_first_search.hpp#L186
https://github.com/stdgraph/graph-v2/blob/master/include/graph/views/breadth_first_search.hpp#L72
So if I want to use my own allocator, like std::pmr::monotonic_buffer_resource, I got compile error.
Documentation for dynamic_graph and related classes for vertex and edge are weakly documented, and the documentation is referring to outdated implementations. This needs to be updated.
Install CMake: https://cmake.org/download/
Link cmake for terminal:
sudo "/Applications/CMake.app/Contents/bin/cmake-gui" --install
Download and install conan:
brew install conan
Then build:
mkdir build && cd build
cmake ..
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
/Users/neoblizz/graph-v2/test/csv_routes.hpp:14:34: warning: unknown warning group '-Wuseless-cast', ignored [-Wunknown-warning-option]
# pragma GCC diagnostic ignored "-Wuseless-cast"
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:20:
/Users/neoblizz/graph-v2/csv-parser/single_include/csv.hpp:8225:32: warning: implicit conversion increases floating-point precision: 'float' to 'std::vector<long double>::value_type' (aka 'long double') [-Wdouble-promotion]
mins.push_back(NAN);
~~~~~~~~~ ^~~
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/math.h:60:28: note: expanded from macro 'NAN'
# define NAN __builtin_nanf("0x7fc00000")
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:20:
/Users/neoblizz/graph-v2/csv-parser/single_include/csv.hpp:8226:33: warning: implicit conversion increases floating-point precision: 'float' to 'std::vector<long double>::value_type' (aka 'long double') [-Wdouble-promotion]
maxes.push_back(NAN);
~~~~~~~~~ ^~~
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/math.h:60:28: note: expanded from macro 'NAN'
# define NAN __builtin_nanf("0x7fc00000")
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:92:26: error: no template named 'range_value_t' in namespace 'std::ranges'
using vertex_t = ranges::range_value_t<vertex_range_t<G>>;
~~~~~~~~^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:94:36: error: no template named 'range_reference_t' in namespace 'std::ranges'
using vertex_reference_t = ranges::range_reference_t<vertex_range_t<G>>;
~~~~~~~~^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:136:49: error: no template named 'random_access_range' in namespace 'std::ranges'; did you mean 'random_access_iterator'?
requires tag_invoke::_has_find_vertex_adl<G> || ranges::random_access_range<vertex_range_t<G>>
^~~~~~~~~~~~~~~~~~~~~~~~~~~
random_access_iterator
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/concepts.h:155:9: note: 'random_access_iterator' declared here
concept random_access_iterator =
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:136:49: error: no template named 'random_access_iterator' in namespace 'std::ranges'; did you mean simply 'random_access_iterator'?
requires tag_invoke::_has_find_vertex_adl<G> || ranges::random_access_range<vertex_range_t<G>>
^~~~~~~~~~~~~~~~~~~~~~~~~~~
random_access_iterator
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/concepts.h:155:9: note: 'random_access_iterator' declared here
concept random_access_iterator =
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:140:22: error: no template named 'random_access_range' in namespace 'std::ranges'; did you mean 'random_access_iterator'?
else if constexpr (ranges::random_access_range<vertex_range_t<G>>)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
random_access_iterator
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/concepts.h:155:9: note: 'random_access_iterator' declared here
concept random_access_iterator =
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:140:22: error: no template named 'random_access_iterator' in namespace 'std::ranges'; did you mean simply 'random_access_iterator'?
else if constexpr (ranges::random_access_range<vertex_range_t<G>>)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
random_access_iterator
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/concepts.h:155:9: note: 'random_access_iterator' declared here
concept random_access_iterator =
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:141:45: error: no template named 'range_difference_t' in namespace 'std::ranges'; did you mean 'iter_difference_t'?
return begin(vertices(g)) + static_cast<ranges::range_difference_t<vertex_range_t<G>>>(uid);
^~~~~~~~~~~~~~~~~~~~~~~~~~
iter_difference_t
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/incrementable_traits.h:67:1: note: 'iter_difference_t' declared here
using iter_difference_t = typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:158:51: error: no template named 'vertex_reference_t'; did you mean 'iter_reference_t'?
concept _has_edges_vtxref_adl = requires(G&& g, vertex_reference_t<G> u) {
^~~~~~~~~~~~~~~~~~
iter_reference_t
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/iterator_traits.h:45:1: note: 'iter_reference_t' declared here
using iter_reference_t = decltype(*declval<_Tp&>());
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:170:19: error: no template named 'vertex_reference_t'; did you mean 'iter_reference_t'?
auto edges(G&& g, vertex_reference_t<G> u) -> decltype(tag_invoke::edges(g, u)) {
^~~~~~~~~~~~~~~~~~
iter_reference_t
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/iterator_traits.h:45:1: note: 'iter_reference_t' declared here
using iter_reference_t = decltype(*declval<_Tp&>());
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:182:68: error: use of undeclared identifier 'vertex_reference_t'
using vertex_edge_range_t = decltype(edges(declval<G&&>(), declval<vertex_reference_t<G>>()));
^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:184:51: error: use of undeclared identifier 'vertex_edge_range_t'
using vertex_edge_iterator_t = ranges::iterator_t<vertex_edge_range_t<G>>;
^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:186:24: error: no template named 'range_value_t' in namespace 'std::ranges'
using edge_t = ranges::range_value_t<vertex_edge_range_t<G>>;
~~~~~~~~^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:186:38: error: use of undeclared identifier 'vertex_edge_range_t'
using edge_t = ranges::range_value_t<vertex_edge_range_t<G>>;
^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:188:34: error: no template named 'range_reference_t' in namespace 'std::ranges'
using edge_reference_t = ranges::range_reference_t<vertex_edge_range_t<G>>;
~~~~~~~~^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:188:52: error: use of undeclared identifier 'vertex_edge_range_t'
using edge_reference_t = ranges::range_reference_t<vertex_edge_range_t<G>>;
^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:198:23: error: no template named 'edge_reference_t'
auto target_id(G&& g, edge_reference_t<const G> uv) -> decltype(tag_invoke::target_id(g, uv)) {
^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:213:53: error: no template named 'range_reference_t' in namespace 'std::ranges'
concept _has_target_adl = requires(G&& g, ranges::range_reference_t<ER> uv) {
~~~~~~~~^
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:218:28: error: no template named 'random_access_range' in namespace 'std::ranges'; did you mean 'random_access_iterator'?
concept _can_eval_target = ranges::random_access_range<vertex_range_t<G>> && requires(G&& g, ranges::range_reference_t<ER> uv) {
^~~~~~~~~~~~~~~~~~~~~~~~~~~
random_access_iterator
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/concepts.h:155:9: note: 'random_access_iterator' declared here
concept random_access_iterator =
^
In file included from /Users/neoblizz/graph-v2/test/examples.cpp:2:
In file included from /Users/neoblizz/graph-v2/test/csv_routes.hpp:28:
In file included from /Users/neoblizz/graph-v2/include/graph/graph.hpp:7:
/Users/neoblizz/graph-v2/include/graph/detail/graph_cpo.hpp:218:28: error: no template named 'random_access_iterator' in namespace 'std::ranges'; did you mean simply 'random_access_iterator'?
concept _can_eval_target = ranges::random_access_range<vertex_range_t<G>> && requires(G&& g, ranges::range_reference_t<ER> uv) {
^~~~~~~~~~~~~~~~~~~~~~~~~~~
random_access_iterator
/Library/Developer/CommandLineTools/SDKs/MacOSX12.3.sdk/usr/include/c++/v1/__iterator/concepts.h:155:9: note: 'random_access_iterator' declared here
concept random_access_iterator =
^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
3 warnings and 20 errors generated.
make[2]: *** [test/CMakeFiles/tests.dir/examples.cpp.o] Error 1
make[1]: *** [test/CMakeFiles/tests.dir/all] Error 2
make: *** [all] Error 2
A graph library is useful for build systems. In this case, you would most likely want toposort to fail if it sees a cyclic dependency. Would this be an option is this library.
Implementation added, added to P1709, & reviewed in SG19.
Open questions/issues
First of all, I would like to thank you all for the great library, and attempt for making graph into standard library ๐.
Currently, I'm using this at work and I'm having a small issue when using DFS views, as it doesn't traverse all the nodes in reachable edges, in some specific circumstances, especially a vertex (and branches connected to it) will be ignored from traversal, if it is the target of an edge whose source also connects to another vertex at the leaf of the graph (no more outgoing edges).
After debugging, I was able to trace back the issue to this line below in the advance()
method of dfs_base
class
I think that popping the stack at this stage is too early, and is the cause of the problem mentioned above. As elements on stack consist of a pair of source and edge (from that source), and if we are in the case where we reach this line, the edge is reaching a "black" target, so we want to pop it out. However, it is possible that the source of that edge has other outgoing edges to other vertices that are not visited yet. Therefore, popping out the element in this case is too early in my opinion. Anyway, the block of code just after that line also checks and pops elements on stack in case of unvisited edges. Thus, I think that the S_.pop()
mentioned above is not necessary and can cause problems.
I've just worked with graph-v2 recently so I'm not sure to have full understanding of the library. Hence, my analysis could be wrong. However, the issue that I'm facing is real, so I would like to mention it here and ask for help.
Thanks
sudo apt install build-essential gdb cmake
May not install the correct cmake version. Installing correct cmake version is easy!
wget https://github.com/Kitware/CMake/releases/download/v[x.xx.x]/cmake-[x.xx.x]-linux-x86_64.sh
chmod +x ./cmake-[x.xx.x]-linux-x86_64.sh
./cmake-[x.xx.x]-linux-x86_64.sh
sudo mv cmake-[x.xx.x]-linux-x86_64 /opt/cmake
sudo ln -s /opt/cmake/bin/* /usr/local/bin/
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.