Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Moving pgr_sequentialVertexColoring to proposed on 3.3 #2202

Closed
krashish8 opened this issue Oct 25, 2021 · 0 comments
Closed

Moving pgr_sequentialVertexColoring to proposed on 3.3 #2202

krashish8 opened this issue Oct 25, 2021 · 0 comments

Comments

@krashish8
Copy link
Member

The function pgr_sequentialVertexColoring - Experimental under the traversal family of functions can be moved to proposed on version 3.3. Function's documentation can be found on https://docs.pgrouting.org/latest/en/pgr_sequentialVertexColoring.html

This function has all the types of tests that are required, and hence is less likely to crash the server. It has a single signature and is based on the straightforward greedy graph coloring algorithm. The tests that are present:

  • No crash tests, when the parameters are NULL.
  • Types check
  • Inner queries check
  • Edge cases on a subset of edges & vertices of the Sample Data (18 tests)

The function belongs to a new family of function (Coloring family), and can be used to color a graph such that no adjacent vertices have the same color. In other words, it can be used as an alternative to (not-so-optimal) job scheduling such that jobs (= vertices) with clashing constraints are colored differently (= assigned different slots). It can be also used as a way of checking whether a graph is bipartite (i.e. when only two colors can be used to color a graph), or dividing some set of clashing tasks into two sets of non-clashing tasks.

Hence, this function can be moved to proposed on 3.3.

cc: @cvvergara

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants