stdgraph/graph-v2

General-purpose C++ graph library

Graph Library Proposal for the C++ Standard

This library is in the alpha stage that may include significant changes to the interface. It is not recommended for general use.

Overview

This library designed to provide a useful set of algorithms, views and container(s) for graphs. It also defines a core Graph Container Interface that provide the basis of interacting with an abstract adjacency list graph, and to provide easy integration with external adjacency list graphs.

• bi-partite and n-partite graphs are under investigation.
• Hyper-graphs are outside the scope of this project.
• Comments and questions are welcome and can be directed to GitHub discussions or issues.

Purpose

This prototype library is an implementation of the proposed Graph Library for ISO Standard C++ as described in P1709. It has gone through major revisions since it was first introduced in 2019. While we are comfortable of the core design, there is still plenty of activity being done and refinements made in its design and implementation. Experimenting with this library is encouraged, keeping in mind that breaking changes are expected.

Goals

The goals of the library include:

1. Support creation of high-performance, state-of-the-art algorithms.
2. Syntax that is simple, expressive and easy to understand when writing algorithms.
3. Define useful concepts and traits that can be used by algorithms to describe their requirements.
4. Support views for graph traversal commonly used by algorithms.
5. Support optional, user-defined value_types for an edge, vertex and graph.
6. Easy integration of existing graph containers.
7. Have an open design to allow for extensions in the future:
   1. Support for partite (partitioned) graphs. This requires extending (changing?) the Graph Container Interface. This is under investigation.
   2. Support the incoming edges on a vertex (e.g. bidirectional graphs).
   3. Investigate features that might make the Interface useful outside P1709, such as sparse vertex_ids. This can help validate the existing design and guide decisions for the future.

Getting Started

This is being actively developed with the latest releases of MSVC (VS2022) on Windows and gcc (11) on Linux/MacOS. Other releases or compilers may or may not work.

Prerequesites

• C++20 compliant compiler that fully supports concepts and ranges.
• CMake 20 or later (for CMake Presets)

Quick Start Guide (Linux, WSL, MacOS)

git clone https://github.com/stdgraph/graph-v2.git
cd graph-v2
mkdir build && cd build
cmake ..
make -j8

Editor/IDE Configuration (Windows)

You'll need to assure CMake Presets are enabled in your IDE or other development tool. See https://docs.microsoft.com/en-us/cpp/build/cmake-presets-vs?view=msvc-170 for configuring Microsoft tools.

Description

In the following tables, P1709 identifies that the feature is in the P1709 proposal. A value of "TBD" indicates that it is being considered, subject to the size of the proposal and other priorities.

Graph Algorithms

Algorithm	P1709	Status
Dijkstra Shortest Paths	Yes	dijkstra_clrs: needs review
Bellman-Ford Shortest Paths	Yes	needs implementation
Connected Components	Yes	needs implementation
Strongly Connected Components	Yes	needs implementation
Bi-Connected Components	Yes	needs implementation
Articulation Points	Yes	needs implementation
Minimum Spanning Tree	Yes	needs implementation
Page Rank	TBD	needs implementation
Betweenness Centrality	TBD	needs implementation
Triangle Count	TBD	needs implementation
Subgraph Isomorphism	TBD	needs implementation
Kruskell Minimum Spanning Tree	TBD	needs implementation
Prim Minimum Spanning Tre	TBD	needs implementation
Louvain (Community Detection)	TBD	needs implementation
Label propagation (Comm. Detection)	TBD	needs implementation

Graph Views

View	Done?	Description
vertexlist	Yes	Iterates over vertices
incidence	Yes	Iterates over outgoing edges of a vertex
neighbors	Yes	Iterates over outgoing neighbor vertices of a vertex
edgelist	Yes	Iterates over edges of a graph
depth_first_search	Yes	Iterates over vertices or edges of a seed vertex in depth-first order
breadth_first_search	Yes	Iterates over vertices or edges of a seed vertex in breadth-first order
topological_sort	No	Iterates over vertices or edges of a seed vertex in topological sort order

Graph Containers

Container	P1709	Description
compressed_graph	Yes	Compresed Sparse Row graph. High performance, static structure.
dynamic_graph	No	Easy to use different containers for vertices and edges.

Acknowledgments

• The NWGraph team for all their collaborations and support, along with providing the algorithm implementations NWGraph Library
• Numerous comments and support from the Machine Learning study group (SG19) in the ISO C++ Standards Committee (WG21).
• Bob Steagal for his gcc-builder & clang-builder scripts
• Jason Turner for his cpp_starter_project
• Vincent La for his cvs-parser
• The ISO C++ Standards Committee (WG21) for C++

graph-v2's Issues

Dijkstra Shortest Path

Implementation added, added to P1709, & reviewed in SG19.
Open questions/issues

1. pass BFS in instead of Queue? (Andrew); Kevin is thinking about it
2. add example to P1709

BFS and DFS with unique allocator

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.

Support for implicit graphs

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.

Support for non-DAG detection

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.

Publish graph-v2 github repository

• add license file (boost)
• README.md completion
• Views: bfs + dfs
• Algorithms: dijkstra + warshall_transitive_closure
• Validate Sphinx output is OK

GitHub Actions: Windows, Linux

Maximal Independent Set

Add documentation for graph.hpp and graph_cpo.hpp

Change /// style Doxygen comments to our standard style

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.

Missing `std::_Fake_copy_init` in MSVC build

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.

Recommend `graph-v2` to just `graph`?

dynamic_graph template parameters should have same order as csr_graph

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.

README.md

• Add general description
• Add Getting Started

Code coverage

Connected Components

Make graph-v2 Public

• 2+ algorithms implemented
• bfs and dfs implemented
• README.md with Description + Getting Started

Triangle Counting

Header `shortest_paths.hpp` adds dependency on `fmt/format.h`

This library should not depend on fmt/format.h, especially that on MSVC there is no reason to include it when we have <format>.

Rename the vertex_view, edge_edge_view and neighbor_view to avoid confusion

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.

Build issues: macOS

Installation Process

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 ..

Output

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

Generate doxygen output

Create mtx parser (from nwgraph)

Add documentation for shortest_paths.hpp

shortest_paths.hpp needs documentation. It will be used as a template for other files.

`degree(g, u)` no matching function.

Simple Example

for (auto&& [uid, u] : views::vertexlist(g)) {
      auto deg = degree(g, u);
}

or

for (auto&& u : vertices(g)) {
    auto deg = degree(g, u);
}

Error

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

	for (auto&& [uid, u] : views::vertexlist(g)) {
	// Calculate the degree of each vertex.
	size_t edge_cnt = 0;
	for (auto&& uv : edges(g, u)) {
	++edge_cnt;
	}
	degrees[uid] = edge_cnt;

(this is the work around)

Min/Max Weight Spanning Tree

Document dynamic_graph and related classes

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.

Strongly Connected Components

Build instructions may need some work.

sudo apt install build-essential gdb cmake

May not install the correct cmake version. Installing correct cmake version is easy!

1. Find the respective version here; https://github.com/Kitware/CMake/releases, and
2. replace the [x.xx.x] in the following commands with the version number (remove the brackets). For example, if you are installing CMake 3.22.1, replace [x.xx.x] with 3.22.1:

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/

Biconnected Components

Provide an example with Bacon number that compiles

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:

• How I can use my own data structure for representing a graph
• That this code can be very brief.

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.

Edge List (Coordinate format list)

Bug in DFS advance: premature unwinding element from DFS stack

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

graph-v2/include/graph/views/depth_first_search.hpp

Line 163 in fedd598

S_.pop();

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

CppCon 2022 Presentation

Use sphinx for code documentation

PageRank

https://github.com/pnnl/NWGraph/blob/master/include/nwgraph/experimental/algorithms/page_rank.hpp