Invariant contiguous range requirement removal
- Vertex invariants for use in isomorphism algorithm must no longer have
low upper bounds due to a hidden allocation linear in the maximum
encountered vertex invariant.
- Vertex invariants must no longer be convertible to `size_t`, but can
be any comparable and hashable types
- Build `unordered_map`-backed invariant multiplicity map efficiently
from sorted vertex invariants
max_invariant initialization
- Zero-initialize `max_invariant` and ensure no UB happens since
`invar?_array` vecs may be empty if their corresponding graph is empty
expand doc
- More explanation on why `vertex_max_invariant` is ignored
First of all, I want to congratulate you for the amazing job you are doing.
I am the main developer of pgRouting, and the project is part of the OSGeo
Foundation [2] community projects.
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide
geospatial routing functionality.
I would like pgRouting [1] to be added on the list of
"Boost Graph Library Users"
The Boost license is on the projects repository [3] and we document when a
boost graph function is used for example in [4]
[1] https://pgrouting.org/
[2] https://www.osgeo.org
[3] https://github.com/pgRouting/pgrouting
[4] https://docs.pgrouting.org/latest/en/pgr_aStar.html
Isomorphism: Ignore vertex_max_invariant
- vertex_max_invariant and invariant2.max() are misnomers since what is
expected is an upper exclusive bound on the possible invariant values,
not their maximum value.
- The parameter can be ignored and the upper exclusive bound found
cheaply at the start of test_isomorphism
- Removes the additional requirement of a nullary max member function on
invariant2
Isomorphism docs
- The expected concept for invariant functors is AdaptableUnaryFunction,
not UnaryFunction
- Null vertices can appear in the isomorphism map output if both graphs
contain disconnected vertices, add a note to that parameter's
documentation
This commit changes the relax function that dijkstra shortest paths uses to only update the distance and predecessor map of the target vertex of each edge. This has the benefit that from now on we can use std::plus as the default combine function.
