boostorg / boostorg/graph

[API] Add simplified overloads for algorithms (starting with Dijkstra)

Offen
#470 1 Kommentar 0 Reaktionen 1 zugewiesene Person Beansprucht von @Becheler Auf GitHub ansehen
Vorherrschende Sprache
C++
Sterne
392
Forks
239
Ø Merge
1 T. 11 Min.
Gemergte PRs (30 T.)
20

Beschreibung

## Problem

I am reworking the documentation, and in need of a nice example for the landing page. The most popular algorithm is Dijkstra. However, given that named parameters should be deprecated, illustrating the current API for Dijkstra shortest path algorithm would require full positional argument list and makes the alternative to named parameters rather painful:

```cpp
dijkstra_shortest_paths(g, vertex(0, g),
make_iterator_property_map(pred.begin(), index),
make_iterator_property_map(dist.begin(), index),
costs,
index,
std::less(),
std::plus(),
std::numeric_limits::max(),
0,
dijkstra_visitor());
```

Users expect to write simpler things, like:
- `dijkstra_shortest_paths(g, s, pred, dist, weight);`
- `dijkstra_shortest_paths(g, s, pred, dist, weight, index);` with custom index map when `VertexList=listS`

## Proposal

Add two overloads to cover most use cases. Arity 5 overload should cover 90% of use cases.

```
Arity 3: (g, s, named_params) // existing, to be dropped
Arity 5: (g, s, pred, dist, weight) // NEW, safe
Arity 6: (g, s, pred, dist, weight, ix) // NEW, safe
Arity 11: (g, s, pred, dist, weight, ix, cmp, combine, inf, zero, vis) // existing
Arity 12: (g, s, pred, dist, weight, ix, cmp, combine, inf, zero, vis, color) // existing
```

## List of candidate algorithms to benefit from a better overload set

| Algorithm | Min positional arity | Proposed min | Saved |
|-----------|---------------------|-------------|-------|
| `dijkstra_shortest_paths` | 11 | 5 | 6 |
| `dag_shortest_paths` | 11 | 6 | 5 |
| `bellman_ford_shortest_paths` | 8 | 5 | 3 |
| `astar_search` | 14 | 5 | 9 |
| `prim_minimum_spanning_tree` | 7 | 2 | 5 |
| `johnson_all_pairs_shortest_paths` | 5 | 4 | 1 |
| `breadth_first_search` | 5 | 2 | 3 |
| `depth_first_search` | 3 | 1 | 2 |

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.