Reviewing files that changed from the base of the PR and between 50d8a48 and 9a91834.

• doc/contraction/images/sample_graph.png is excluded by !**/*.png
• doc/contraction/images/sample_graph_with_shortcuts.png is excluded by !**/*.png

• NEWS.md (1 hunks)
• doc/conf.py.in (1 hunks)
• doc/contraction/CMakeLists.txt (1 hunks)
• doc/contraction/contraction-family.rst (1 hunks)
• doc/contraction/images/CMakeLists.txt (1 hunks)
• doc/contraction/pgr_contractionHierarchies.rst (1 hunks)
• doc/src/experimental.rst (1 hunks)
• doc/src/pgRouting-introduction.rst (2 hunks)
• doc/src/release_notes.rst (1 hunks)
• docqueries/contraction/CMakeLists.txt (1 hunks)
• docqueries/contraction/contractionHierarchies.pg (1 hunks)
• docqueries/contraction/contractionHierarchies.result (1 hunks)
• docqueries/contraction/test.conf (1 hunks)
• include/c_types/contractionHierarchies_rt.h (1 hunks)
• include/contraction/ch_graphs.hpp (1 hunks)
• include/contraction/contractionGraph.hpp (3 hunks)
• include/contraction/contractionHierarchies.hpp (1 hunks)
• include/cpp_common/identifiers.hpp (4 hunks)
• include/cpp_common/to_postgres.hpp (2 hunks)
• include/drivers/contraction/contractionHierarchies_driver.h (1 hunks)
• include/visitors/dijkstra_visitors.hpp (1 hunks)
• locale/pot/pgrouting_doc_strings.pot (10 hunks)
• pgtap/contraction/contractionHierarchies/edge_cases/directed.pg (1 hunks)
• pgtap/contraction/contractionHierarchies/edge_cases/undirected.pg (1 hunks)
• pgtap/contraction/contractionHierarchies/inner_query.pg (1 hunks)
• pgtap/contraction/contractionHierarchies/no_crash_test.pg (1 hunks)
• pgtap/contraction/contractionHierarchies/types_check.pg (1 hunks)
• sql/contraction/CMakeLists.txt (1 hunks)
• sql/contraction/_contractionHierarchies.sql (1 hunks)
• sql/contraction/contractionHierarchies.sql (1 hunks)
• sql/sigs/pgrouting--3.8.sig (1 hunks)
• src/contraction/CMakeLists.txt (1 hunks)
• src/contraction/contractionHierarchies.c (1 hunks)
• src/contraction/contractionHierarchies_driver.cpp (1 hunks)
• tools/testers/contractionHierarchies_data.sql (1 hunks)
• tools/testers/setup_db.sh (1 hunks)

tools/testers/setup_db.sh (1)

35-35: Confirm the new data file loads in right order
You’ve added ${DIR}/contractionHierarchies_data.sql after sampledata.sql, which makes sense. Please verify this ordering doesn’t conflict with downstream tests that expect those tables.

sql/contraction/CMakeLists.txt (1)

5-6: New SQL files correctly added to build
The addition of _contractionHierarchies.sql and contractionHierarchies.sql aligns with the other modules. Filenames follow naming conventions, and ordering groups internal (_) then public. No changes needed here.

doc/src/pgRouting-introduction.rst (1)

66-74: Release contributors list updated
Aurélie Bousquet has been added to the 3.8.x contributors. The list remains in alphabetical order by surname. Good.

doc/contraction/images/CMakeLists.txt (1)

6-7: Approve inclusion of new example images
The two new files, sample_graph.png and sample_graph_with_shortcuts.png, are correctly added to LOCAL_FILES so they'll be copied into the documentation build.

doc/contraction/CMakeLists.txt (1)

7-7: Approve documentation file addition
The pgr_contractionHierarchies.rst entry has been properly added to LOCAL_FILES, ensuring the new Contraction Hierarchies docs are included in the build.

src/contraction/CMakeLists.txt (1)

5-6: Approve new source files in build target
contractionHierarchies.c and contractionHierarchies_driver.cpp have been correctly added to the contraction library target.

docqueries/contraction/CMakeLists.txt (1)

6-6: Approve inclusion of query script in docqueries
Adding contractionHierarchies to LOCAL_FILES ensures the new .pg test script is processed in the documentation query tests.

doc/src/experimental.rst (1)

63-68: LGTM: Properly integrates contraction-family into experimental functions listing

The changes correctly add the contraction-family documentation to the experimental functions section, following the consistent format used for other function families. The inclusion is properly positioned between the existing coloring-family and transformation-family sections.

sql/sigs/pgrouting--3.8.sig (1)

90-91:

✅ Verification successful

LGTM: Function signatures properly defined

The new signatures for contraction hierarchies functions are correctly added, following pgRouting's naming conventions with both internal (_pgr_contractionhierarchies) and public (pgr_contractionhierarchies) functions.

Note that according to previous communications, this signature file is auto-generated by a command and should not be modified manually. If the file was manually edited, ensure the changes are also made in the source code that generates these signatures.

---

🏁 Script executed:

#!/bin/bash
# Check if the signatures match what would be generated
cd sql
make
# Check for any differences in the generated signatures file
diff ../sql/sigs/pgrouting--3.8.sig sigs/pgrouting--3.8.sig.new

Length of output: 237

---

🏁 Script executed:

#!/bin/bash
# Display context around the new signatures in the .sig file
echo "=== Signature file context (lines 80–110) ==="
sed -n '80,110p' sql/sigs/pgrouting--3.8.sig

echo ""
echo "=== SQL source definitions for contractionhierarchies ==="
# Search all SQL files for both internal and public function definitions
rg -n -C2 "contractionhierarchies" -g '*.sql'

Length of output: 2694

---

Verified: Contractionhierarchies signatures are correct

• _pgr_contractionhierarchies(text, BIGINT[], boolean) matches the definition in sql/contraction/_contractionHierarchies.sql
• pgr_contractionhierarchies(text, boolean, BIGINT[]) matches the SQL wrapper in sql/contraction/contractionHierarchies.sql

This signature file is auto-generated—please do not edit it directly. Any changes should be made in the generator sources.

doc/conf.py.in (1)

384-384: LGTM: Output format for contraction hierarchies results

Added a properly formatted substitution for the contraction hierarchies result tuple, which will ensure consistent documentation of the function's return value.

include/cpp_common/identifiers.hpp (1)

174-174: Documentation fixes

Fixed typos in Doxygen comments, improving code documentation.

Also applies to: 184-184, 233-233

include/contraction/ch_graphs.hpp (1)

53-56: LGTM! Good choice using boost::setS for edge uniqueness

The addition of CHUniqueUndirectedGraph using boost::setS as the edge container selector is a good design choice. Unlike the existing CHUndirectedGraph that uses boost::listS, this ensures edge uniqueness in the graph, which is important for the contraction hierarchies algorithm to avoid duplicate shortcuts.

pgtap/contraction/contractionHierarchies/types_check.pg (1)

21-54: LGTM! Comprehensive type checking test suite

The test suite is well-structured with proper version checking, function existence verification, and detailed argument type validation. The version-dependent test planning ensures backward compatibility.

include/c_types/contractionHierarchies_rt.h (2)

40-50: LGTM! Well-structured return type for contraction hierarchies

The contractionHierarchies_rt struct is well-designed to capture all necessary information:

• Edge properties (id, source, target, cost)
• Contraction data (contracted_vertices array with size)
• Hierarchy information (vertex_order, metric)

The type field allows for differentiating between different types of results (e.g., edges vs. shortcuts).

---

4-5: 🧹 Nitpick (assertive)

Fix copyright year

The copyright year needs to be corrected to the current year.

-Copyright (c) 2025 pgRouting developers
+Copyright (c) 2024 pgRouting developers

Likely an incorrect or invalid review comment.

sql/contraction/_contractionHierarchies.sql (2)

37-53: SQL function definition looks correct

The internal _pgr_contractionhierarchies function is well-defined with appropriate parameters and return structure. The VOLATILE STRICT modifiers ensure proper behavior with respect to function calls and NULL handling.

---

57-58: Clear function documentation

Good practice to explicitly mark this as an internal function to guide users toward the public API.

sql/contraction/contractionHierarchies.sql (2)

41-60: Well-structured public function definition

The public pgr_contractionHierarchies function is correctly implemented, with appropriate default values for optional parameters and proper use of the internal helper function.

---

64-74: Comprehensive function documentation

The comment clearly indicates the experimental status of the function and provides detailed information about parameters and documentation. This helps users understand how to use the function and sets expectations about potential API changes.

doc/contraction/contraction-family.rst (4)

35-44: Clear categorization of the new function

Good organization by properly placing the new function in the experimental section with appropriate warnings.

---

57-63: Improved introduction to contraction benefits

The expanded description of graph contraction and its benefits provides good context for users. The clarification that "original edges can be kept in some methods" is an important distinction.

---

65-73: Clear differentiation between contraction algorithms

Good explanation of how the algorithms relate to each other, particularly noting that the first two can be combined via pgr_contraction while the third (contraction hierarchies) is implemented separately.

---

80-81: Additional relevant references

The addition of academic references enhances the documentation by providing users with resources for further reading on contraction hierarchies.

pgtap/contraction/contractionHierarchies/inner_query.pg (1)

39-41:

✅ Verification successful

Double-check style_dijkstra concatenation – missing space may create invalid SQL

The call builds a string like

pgr_contractionHierarchies(… , true, ARRAY[1]::BIGINT[])

Because the opening parenthesis is inside the first argument and the comma starts
the second argument, the resulting query ends up with (..., (no space) which is fine
for PostgreSQL unless the helper adds its own punctuation.

To prevent fragile implicit string concatenation you could delegate arguments
cleanly:

SELECT style_dijkstra(
  'pgr_contractionHierarchies',
  ', true, ARRAY[1]::BIGINT[]'
);

Please verify the generated SQL with RAISE NOTICE.

---

🏁 Script executed:

#!/bin/bash
set -e
# Locate and inspect the definition and usage of style_dijkstra
rg -n "style_dijkstra" -A5 -B5 --glob '*.sql' --glob '*.pg' || true

Length of output: 66791

---

🏁 Script executed:

#!/bin/bash
set -e
# Extract the entire style_dijkstra function definition for analysis
awk '/CREATE OR REPLACE FUNCTION style_dijkstra/,/^\\$\\$ LANGUAGE plpgsql;/' tools/testers/inner_styles.sql

Length of output: 13722

---

🏁 Script executed:

#!/bin/bash
set -e
# Search for test_anyInteger definition to inspect how fn and rest_sql are used
rg -n "CREATE OR REPLACE FUNCTION test_anyInteger" -A20 -B0 --glob '*.sql' --glob '*.pg'

Length of output: 6180

---

🏁 Script executed:

#!/bin/bash
set -e
# Extract full definition of test_anyInteger to inspect how rest_sql is concatenated
awk '/CREATE OR REPLACE FUNCTION test_anyInteger/,/\$BODY\$ LANGUAGE plpgsql;/' tools/testers/innerQuery.sql

Length of output: 4114

---

No change needed: style_dijkstra invocation is already safe

The rest_sql argument begins with ', …', so when it’s concatenated after the $$ delimiter you get $$, …, which is valid. The function uses explicit two‐argument passing and dollar‐quoting—no implicit string concatenation gap exists.

src/contraction/contractionHierarchies.c (1)

196-202: Potential leak of result_tuples after last row

result_tuples is never freed when SRF_RETURN_DONE is reached.
Even though the multicall memory context is cleaned up at end-of-query, explicitly pfree-ing large results (>MB) shortens PortalDrop time and lowers peak memory.

else {
    pfree(result_tuples);
    SRF_RETURN_DONE(funcctx);
}

docqueries/contraction/contractionHierarchies.pg (1)

28-31: Negative reverse_cost may break shortest-path algorithms

The script inserts shortcut edges with reverse_cost = -1.
While pgr_bdDijkstra ignores negative costs on forward cost, many pgRouting algorithms treat any negative weight as “prohibitively expensive” (or error).
Confirm that every consumer of edges tolerates -1; otherwise store the same positive value as cost or NULL for one-way semantics.

pgtap/contraction/contractionHierarchies/edge_cases/directed.pg (4)

44-65: Good test case design for minimal graph.

This test case provides a solid baseline by testing the simplest possible graph (just two vertices connected by an edge). The expected results are well-defined and the assertions are appropriate.

---

89-121: Well-structured test for full graph.

The full graph test case is comprehensive and properly ordered by ID for consistent comparison. The expected solution includes both vertices and edge entries with appropriate metrics and ordering.

---

155-189: Good edge case testing with forbidden vertices.

These test cases effectively verify the behavior with forbidden vertices, including the extreme case where all vertices are forbidden (resulting in an empty result set). Using is_empty() for the final test is an appropriate assertion.

---

194-197: Good transaction handling.

The test properly calls the test function, finishes the pgTAP test, and rolls back the transaction to avoid persisting any changes made during the test. This follows best practices for database tests.

locale/pot/pgrouting_doc_strings.pot (9)

2560-2594: New contraction hierarchies documentation properly added to contraction family documentation

The PR adds comprehensive documentation for the new experimental function pgr_contractionHierarchies to the contraction family of functions. The documentation includes a proper explanation of the contraction hierarchies method, how it builds a hierarchical order of vertices, and its purpose in optimizing shortest path algorithms.

---

3571-3572: References to the related issue correctly added

The documentation correctly references the GitHub issue #2536 which this implementation addresses: "Support for contraction hierarchies (pgr_contractionHierarchies)".

---

8503-8511: Correctly marked as experimental function with appropriate metadata

The new function is properly marked as experimental, with its full signature and description. This is important to indicate to users that the API may change in future versions.

---

8512-8544: Comprehensive explanation of the algorithm's purpose and benefits

The documentation provides an excellent explanation of how contraction hierarchies work, their purpose in speeding up shortest path calculations, and the hierarchical nature of the algorithm. The description of prioritizing vertices in highway networks versus secondary roads is particularly helpful for users to understand the practical applications.

---

8545-8560: Clear description of algorithm behavior and output

The documentation clearly explains that the algorithm doesn't delete vertices but adds shortcut edges and maintains hierarchical ordering, which is important for users to understand how to use the results properly.

---

8587-8603: Well-documented example usage

The documentation includes examples showing how to use the function, which is essential for users to understand the practical application of the algorithm.

---

8612-8709: Detailed explanation of the algorithm's internal workings

The documentation provides a detailed explanation of how the contraction hierarchies algorithm works internally, including the process of building shortcuts, initializing the queue, and building the final vertex order. This is valuable for users who want to understand the algorithm in depth.

---

2566-2570: Clear explanation of function purpose with suitable references

The documentation includes appropriate references to support the implementation, which adds credibility to the documentation and provides users with resources for further reading.

---

2590-2594: Good integration with existing architecture

The documentation properly explains how this function fits into the existing contraction family of functions, noting that it's implemented on its own rather than being combined with other contraction algorithms through the iterative procedure used by pgr_contraction.

include/cpp_common/to_postgres.hpp (1)

172-176: Populate metric for shortcut edges

The documentation states that metric for rows of type 'e' must hold the
edge’s weight. Currently both metric and vertex_order are hard-coded to
-1.

-            edge.source, edge.target, edge.cost,
-            contracted_vertices, count, -1, -1};
+            edge.source, edge.target, edge.cost,
+            contracted_vertices, count,
+            static_cast<int64_t>(edge.cost),  /* metric  */
+            -1                                /* vertex_order */
+        };

include/contraction/contractionGraph.hpp (1)

60-63: 🧹 Nitpick (assertive)

Remove unused / low-value type aliases

E_i and V_p are introduced but never used in this header. Dead aliases add noise and may confuse future readers who go looking for their purpose.

-    using E_i = typename boost::graph_traits < G >::edge_iterator;
-    using V_p = typename std::pair< double, V >;

Unless you have an imminent use-case, please drop them (or add the first use in this patch) to keep the public API lean.

Likely an incorrect or invalid review comment.

Reviewing files that changed from the base of the PR and between 9a91834 and 7db16c3.

• docqueries/contraction/contractionHierarchies.pg (1 hunks)
• docqueries/contraction/test.conf (1 hunks)
• include/contraction/contractionHierarchies.hpp (1 hunks)
• include/cpp_common/identifiers.hpp (4 hunks)
• include/visitors/dijkstra_visitors.hpp (1 hunks)
• pgtap/contraction/contractionHierarchies/edge_cases/directed.pg (1 hunks)
• pgtap/contraction/contractionHierarchies/edge_cases/undirected.pg (1 hunks)
• pgtap/contraction/contractionHierarchies/no_crash_test.pg (1 hunks)

• GitHub Check: Codacy Static Code Analysis
• GitHub Check: documentation (zh_Hans)
• GitHub Check: Ubuntu clang
• GitHub Check: documentation (es)
• GitHub Check: Ubuntu Boost (80)
• GitHub Check: macos (macos-latest)
• GitHub Check: Check for changelog entry
• GitHub Check: macos (macos-14)
• GitHub Check: Ubuntu Boost (84)
• GitHub Check: Ubuntu Boost (75)
• GitHub Check: Ubuntu Boost (77)
• GitHub Check: Ubuntu Boost (79)
• GitHub Check: Ubuntu Boost (68)
• GitHub Check: Ubuntu Boost (56)
• GitHub Check: Ubuntu Boost (86)
• GitHub Check: Ubuntu Boost (83)
• GitHub Check: Ubuntu Boost (78)
• GitHub Check: Ubuntu Boost (76)
• GitHub Check: Check queries

include/cpp_common/identifiers.hpp (1)

54-59: LGTM: New method to replace identifier set

The new set_ids method appropriately passes the parameter by const reference, which avoids unnecessary copying of potentially large sets. This implementation is correct and efficient.

include/visitors/dijkstra_visitors.hpp (1)

55-79: LGTM: Well-designed visitor for bounded Dijkstra search

The implementation of dijkstra_max_distance_visitor is well-structured and follows the established pattern of other visitor classes in this file. The class correctly implements:

1. A constructor that takes the distance threshold and storage for reached vertices
2. An examine_vertex method that throws an exception when exceeding the distance threshold
3. Proper tracking of reached vertices by their IDs

This implementation will effectively limit Dijkstra's algorithm search to vertices within the specified maximum distance.

pgtap/contraction/contractionHierarchies/edge_cases/undirected.pg (1)

1-190: LGTM: Comprehensive test suite for contraction hierarchies on undirected graphs

The test suite thoroughly exercises the pgr_contractionHierarchies function with undirected graphs, covering a variety of edge cases:

• Single edge graphs
• Partially connected graphs
• Full graphs
• Various forbidden vertex configurations
• Empty result cases

The test structure with prepared statements and expected results is clear and well-organized. The plan count (6) correctly matches the number of assertions.

pgtap/contraction/contractionHierarchies/no_crash_test.pg (1)

23-23: Double-check that plan(5) matches the number of assertions

The script emits:

1. isnt_empty → 1 assertion
2. no_crash_test(…) → typically 4 assertions
   Total = 5 (as planned) only if no_crash_test really returns four checks in this context.

If the helper ever changes its internal count, this file will silently drift out of sync. Consider guarding with tests_planned() or explicitly documenting the expectation.

pgtap/contraction/contractionHierarchies/edge_cases/directed.pg (1)

27-28: Plan count is consistent – good catch

plan(6) aligns with the five set_eq() checks plus the final is_empty() assertion.
The early‐exit skip() branch correctly downgrades to plan(1). No action required.

Reviewing files that changed from the base of the PR and between 7db16c3 and 60b5b26.

• docqueries/contraction/contractionHierarchies.result (1 hunks)

• GitHub Check: Ubuntu Boost (86)
• GitHub Check: Ubuntu Boost (84)
• GitHub Check: Ubuntu Boost (80)
• GitHub Check: Ubuntu Boost (78)
• GitHub Check: Ubuntu Boost (75)
• GitHub Check: Ubuntu Boost (77)
• GitHub Check: Ubuntu Boost (56)
• GitHub Check: Ubuntu Boost (83)
• GitHub Check: Ubuntu Boost (68)
• GitHub Check: Ubuntu Boost (76)
• GitHub Check: Ubuntu Boost (79)
• GitHub Check: Codacy Static Code Analysis
• GitHub Check: Ubuntu clang
• GitHub Check: documentation (zh_Hans)
• GitHub Check: Check queries
• GitHub Check: documentation (es)

docqueries/contraction/contractionHierarchies.result (8)

1-5: Transcript Formatting Verified

This segment cleanly demonstrates starting a transaction and the psql client messages (BEGIN, SET) as expected in a documentation example.

---

6-27: Initial Edges Listing is Clear

The SELECT id, source, target, cost FROM edges ORDER BY id; query and its output correctly illustrate the base graph input for the contraction hierarchy example.

---

29-56: Contraction Hierarchies Invocation (Undirected) Looks Good

The call to pgr_contractionHierarchies with directed => false and the raw output table (type, id, contracted_vertices, etc.) provide a precise illustration of the function’s behavior on an undirected graph.

---

58-91: Contraction Hierarchies with Forbidden Vertices is Correct

The example invoking pgr_contractionHierarchies with a forbidden array properly demonstrates how excluded vertices alter the contraction order and shortcuts. The output aligns with expectations.

---

93-102: Schema Modifications Illustrated Properly

The ALTER TABLE edges ... and ALTER TABLE vertices ... commands show how to prepare the tables for storing contraction hierarchy metadata. Wrapping them in the transaction is appropriate for a docs example.

---

110-120: Edge Insertion and Vertex Update Examples are Solid

The INSERT INTO edges … FROM contraction_results WHERE type = 'e'; and subsequent UPDATE vertices … commands correctly show how shortcuts and metadata are applied. The psql output (INSERT 0 4, UPDATE 17) is accurate.

---

122-134: Bidirectional Dijkstra Demonstration is Effective

The final SELECT * FROM pgr_bdDijkstra query against the augmented graph clearly illustrates how contraction hierarchies integrate with pathfinding. The displayed path sequence and aggregated cost match expectations.

---

136-139: Transaction Rollback Ensures No Side Effects

The concluding ROLLBACK; and its client output cleanly revert all schema and data changes, making this safe for documentation runs.