Replies: 4 comments 7 replies
-
|
A couple of thoughts regarding the non-index adjacency list, that is, the situation where One. I can see that there already is a CPO Two. Is the case where |
Beta Was this translation helpful? Give feedback.
-
|
One. We do need a random_access_range range for vertices for an O(1) lookup for a target vertex when traversing a graph, or we need a O(log n) lookup for a map-like range. It has a direct impact to performance. I can agree that we tend to scan vertices in a number of algorithms, where a forward_range is sufficient, but it doesn't remove the requirement for the ability to find a vertex with known complexity. Two. I find that a lot of discussion for graphs is from academia or high-performance computing, where vertices are in random access containers with integral indices. It's simple and straight forward and is typically very high performance. However, I believe graphs come in far bigger varieties that don't fall within those constraints. |
Beta Was this translation helpful? Give feedback.
-
|
On defining concepts in terms of CPOs. One. When we see a constraint like requires(G&& g, vertex_id_t<G> uid) {
{ edges(g, uid) } -> forward_range;
}it is not clear if the constraint is on the CPO, or the function (the customization) provided by the author of Two. The implied requirements on CPOs -- in the form of using types like |
Beta Was this translation helpful? Give feedback.
-
Sorry, it is my misunderstanding of the name lookup rules. Having found a function object precludes any argument-dependent look-up of functions and function templates. The names must be CPOs. |
Beta Was this translation helpful? Give feedback.
-
|
The concept is the guarantee of behavior that an algorithm can rely on, so ultimately it is a requirement is on the graph container that supplies the functionality. |
Beta Was this translation helpful? Give feedback.
-
|
Hmm. Consider the following example where the user incorrectly adapts their type (CPO namespace MyLibrary {
struct MyEdge {
std::string content;
int indexOfTarget;
};
struct MyVertex {
std::string content;
std::vector<MyEdge> outEdges;
};
class MyGraph {
std::vector<MyVertex> _vertices;
public:
MyVertex const* getVertexByIndex(int index) const { return &_vertices[index]; }
auto getAllVertices() const { return std::views::all(_vertices); }
};
//auto vertices(MyGraph const& g) { return g.getAllVertices(); } // for vertex_range_t
auto edges(MyGraph const&, const MyLibrary::MyVertex& v) { return std::views::all(v.outEdges); }
auto edges(MyGraph const& g, int i) { return edges(g, *g.getVertexByIndex(i)); }
int vertex_id(MyGraph const& g, std::vector<MyVertex>::const_iterator it) { return std::distance(g.getAllVertices().begin(), it); }
int target_id(MyGraph const&, MyEdge const& uv) { return uv.indexOfTarget; }
}I get the following error message: But when I change two of the library concepts to: template <class G>
concept vertex_range = requires(G&& g) {
graph::vertices(g);
} &&
sized_range<vertex_range_t<G>> &&
forward_range<vertex_range_t<G>> &&
requires(G&& g, vertex_iterator_t<G> ui) {
{ vertex_id(g, ui) } -> std::copyable;
};
template <class G>
concept index_vertex_range = vertex_range<G> &&
random_access_range<vertex_range_t<G>> &&
integral<vertex_id_t<G>>;The error message for the user is: |
Beta Was this translation helpful? Give feedback.
-
|
I think I can now better articulate my observation. I believe that "random access range of forward ranges" may not be the best way to describe the adjacency list. I think a more accurate model would be: a forward range (of vertices) of forward ranges (of edges) with the ability to perform the look-up back into the outer collection of vertices. You need the forward iteration of vertices to count them or to apply something for each vertex (like initialization). And then, once you have found the id of the target vertex, to look it up in the collection of vertices. A random-access range happens to provide both these functions (forward iteration and efficient lookup), but in general you do not need the full power of a random-accees range. |
Beta Was this translation helpful? Give feedback.
-
|
I agree that we typically iterate through vertices in a forward direction when doing a number of algorithms. However, when the vertex id is an integral index, we need the ability to have a O(n) lookup to find the target (vertex) of an edge. |
Beta Was this translation helpful? Give feedback.
-
|
I acknowledge this. Let me explain a bit further what I mean. The goals to achieve when designing the adjacency list concept(s):
Each moderately complex algorithm, such as Dijkstra's shortest paths, or simple breadth-first iteration will do the following at some point:
For index-based adjacency list, we want this operation to be constant-time. For map-like access we have to accept that this will be in logarithmic type. Graph-v2 already uses the customization point These complexity guarantees could be reflected in two ways. Approach 1.Provide two concepts: void bfs(index_adjacency_list auto const& g , /*...*/);
// Complexity:
// O(V + E) visitations
// O(1) vertex ID comparisons
void bfs(map_adjacency_list auto const& g , /*...*/);
// Complexity:
// O(V + E) visitations
// O(E * log V) vertex ID comparisonsApproach 2.Just have one concept that does not discriminate based on the look-up complexity: void bfs(adjacency_list auto const& g , /*...*/);
// Complexity:
// O(V + E) visitations
// O(E) calls to CPO `find_vertex(g, uid)`And this would also work for representations where a vertex can only be found via a sequential search. You can make the two concepts There are known cases where we need two concepts that differ only by semantic requirements. One is template <typename T>
concept WithPlus = requires(T x, T y)
{
{x + y} -> same_as<T>;
};
template <typename T>
concept Addable = WithPlus && requires(T x, T y)
{
// commutative:
// x + y == y + x
};But so far, the motivation for having such two concepts has been:
In the case of |
Beta Was this translation helpful? Give feedback.
-
|
I've been answering your comments in reverse order. I've addressed everything except your first comment, which I'll do now. Two. Too many concepts. The addition of descriptors in P3130r3 allowed me to remove most of the "basic" concepts because there's no longer concepts for id-only and id+reference; they're now consolidated into single definitions. Are you referring to that or a previous version of the paper (or the current implementation, which doesn't include descriptors yet). If your comments are based on P3130r3 please clarify. Three. I wasn't aware of the hole for copyable vertex ids. That should be corrected. Four. I believe your get_vertex(g,uid) is an alias of the existing find_vertex(g,uid). The difference between adjacency_list and index_adjacency_list isn't just the ability to find a vertex, it's used to define the requirements by algorithms and what they support. Working with a vertex (or deque) is different than working with a map, and they offer different performance guarantees. |
Beta Was this translation helpful? Give feedback.
-
|
Let me quickly follow up on some points. One (which CPOs are crucial and which are optimization?): It is still not addressed, but I think I will address it myself, when I am done documenting the CPOs in this library. Two (too many concepts). When I say this, I am referring to the implementation of graph-v2 library that the programmers will use. I am not referring to the paper. I see graph-v2 as a library that stands on its own. But since you mention P3130r3, I can see that it has fewer concepts than R2. I still believe that the number of concepts can be reduced further. Three (missing copyable requirements). I will be happy to fix this. I am just waiting on other clarifications. Four (random access versus map look-up). I think that for this part of the discussion to be resolved, I would have to prepare some minimum code examples. So for now, I will only make a statement. I understand and acknowledge the observation that the operation of getting a target vertex is O(1) in some graph representations and O(log n) in other representations, and amortized O(1) in yet other representations. My claim is that whatever the representation, a generic algorithm will have to do the same thing in any case: get from the edge to the target vertex. So there is no value in using a different syntax for getting to the target vertex in constant time and getting to the target vertex in logarithmic time. I know that there are concepts that differ only by semantic properties, but these are the cases where not adhering to the semantic constraints render the algorithm results incorrect. In your case not adhering to the time complexities would render the algorithm slower, but still correct. I still acknowledge that the complexity guarantees are important. But this does not have to be reflected via multiple concepts. I will try to provide an illustration of this within the next couple of days. |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
-
I would like to start the discussion on changing the concepts a bit. The current one (
index_adjacency_list) is buggy and somewhat unfriendly to users. But rather than patching individual bugs, I would go with some principal approach.The things that I consider in need of fixing:
One. If a concept is defined in terms of CPOs, the defining CPOs require a more clear specification. We have to know which of the many CPOs are crucial for the definition of the concepts, and which are just optimization.
Two. Too many concepts.
Three. A hole in
index_adjacency_list. It requires thattarget_idreturns something copyable (thecopyablerequirement is concealed inside the CPO), but nothing more. Whereas viewbfs_baseapparently requires that the result oftarget_idis convertible tovertex_id_t<G>(see here). As a result, I can customize my graph, so that it satisfies conceptindex_adjacency_list, but any algorithm using my type fails to compile (see bad_type_that_satisfies_the_concept.cpp.txt).Four. Unnecessary two concepts: one for accessing vertices by index, the other for looking up vertices as if in a map. They can be merged by providing another CPO:
get_vertex(g, vid)that will perform the look-up in a way most appropriate for the user graph.Beta Was this translation helpful? Give feedback.
All reactions