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
shortest_paths.hpp needs documentation. It will be used as a template for other files.
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.
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.
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
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
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.
This library should not depend on fmt/format.h
, especially that on MSVC there is no reason to include it when we have <format>
.
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.
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.
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.
Implementation added, added to P1709, & reviewed in SG19.
Open questions/issues
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/
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.
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
Thanks for this work!
When attempting to consume this library through FetchContent as such:
FetchContent_Declare(
stdgraph
GIT_REPOSITORY https://github.com/stdgraph/graph-v2.git
GIT_TAG master
)
FetchContent_MakeAvailable(stdgraph)
One will experience errors such as:
Make Error at out/build/x64-debug/_deps/stdgraph-src/cmake/FetchFMT.cmake:23 (add_subdirectory):
1> [CMake] add_subdirectory not given a binary directory but the given source
1> [CMake] directory "C:/dev/qmatpp/out/build/x64-debug/_deps/fmt-src" is not a
1> [CMake] subdirectory of "C:/dev/qmatpp/out/build/x64-debug/_deps/stdgraph-src".
1> [CMake] When specifying an out-of-tree source a binary directory must be explicitly
1> [CMake] specified.
When a library already being consumed through FetchContent introduces further dependencies through FetchContent, those dependencies are placed adjacent to the consuming library in the same _deps
folder. As such, the use of add_subdirectory
will result in the above error.
Considering graph-v2/cmake/FetchCatch.cmake
:
message(STATUS "Cloning External Project: catch2")
FetchContent_Declare(
catch2
GIT_REPOSITORY https://github.com/catchorg/Catch2.git
GIT_TAG v3.5.2
)
FetchContent_GetProperties(catch2)
if(NOT catch2_POPULATED)
FetchContent_Populate(
catch2
)
endif()
set(CATCH2_SOURCE_DIR "${catch2_SOURCE_DIR}")
set(CATCH2_INCLUDE_DIR "${catch2_INCLUDE_DIR}")
FetchContent_MakeAvailable(catch2)
add_subdirectory(${catch2_SOURCE_DIR})
From the CMake documentation, I believe that the populated check is not required when using MakeAvailable
:
If the dependency has already been populated earlier in this run, set the _POPULATED, _SOURCE_DIR and _BINARY_DIR variables in the same way as a call to FetchContent_GetProperties(), then skip the remaining steps below and move on to the next dependency in the list. src
Second, I believe that the add_subdirectory
call that is introducing the issue at hand is not needed, as MakeAvailable
should automatically call add_subdirectory
:
If the dependency was not satisfied by a provider or a find_package() call, FetchContent_MakeAvailable() then uses the following logic to make the dependency available:
- .... (Other steps) ...
- If the top directory of the populated content contains a CMakeLists.txt file, call add_subdirectory() to add it to the main build. It is not an error for there to be no CMakeLists.txt file, which allows the command to be used for dependencies that make downloaded content available at a known location, but which do not need or support being added directly to the build. src
In my experience, the automatic add_subdirectory
does not introduce the above error.
I am happy to open a PR to introduce these changes, but I wanted to confirm that my interpretation of the build setup was correct first. Thanks.
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.
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.