New Functionality in pgRouting: pgr_depthFirstSearch function

[krashish8]

• Description: Implementation of the Depth First Search algorithm in pgRouting.
• Kind of graphs it works with: Both directed and undirected.
• Uses which boost function: boost::depth_first_search and boost::undirected_dfs
• Discussion of the name to be used when added to pgRouting: pgr_depthFirstSearch.
• User documentation including automatically generated results of example queries. (deployed link)
• pgTAP unit tests with different graphs on the created by edges_SQL (E set) where the vertices are deduced from E, +1 node given by the start_vid.
  • E = {}
  • E has one vertex
  • E has 2 vertices and one edge
    • second node is reachable from start_vid exactly
    • second node is unreachable from start_vid so result is within the lone edge
  • E has 3 vertices
    • many combinations of possible edges that can exist with 3 vertices
    • together with many combinations of reach-ability
  • E has 4 vertices
    • many combinations of possible edges that can exist with 4 vertices
    • together with many combinations of reach-ability
  • No server crash test
    • Normally happens when data is NULL
  • Test of persistence
    • So that in the future no one accidentally removes the function, changes signature, without our knowledge
    • example
    • Note that compulsory parameters are unnamed parameters and optional parameters are named parameters see RFC 3
  • [not required] Equivalence tests, examples:
    • if the reached node is a real vertex of the graph, then executing pgr_dijkstra will give the total aggregate cost with the same value returned by the pgr_isochrones (if so applies)
    • if the reached node is a node within an edge of the graph, virtual vertex, (that gives the exact distance used on the call of pgr_isochrones, then executing pgr_dijkstraWithPoints from the start_vid to the virtual vertex will give the total aggregate cost with the same value distance used with the call to pgr_isochrones. (actually this same function can be used when the node is a real vertex on the graph).
    • see example of equivalence test.

About tests:

• Remember a test is independent from the code, so to design a test first make the graph, write down the expected results. Example:

  From this query:

  SELECT * FROM pgr_isochrones(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id > 20',
   1, 2.5::FLOAT, true);

empty results are expected, because the internally generated graph is G=(E={}, V={1}) so the pgtap test would be:

SELECT is_empty($$
  SELECT * FROM pgr_isochrones(
      'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id > 20',
     1, 2.5::FLOAT, true)
$$);

[krashish8]

Closing this.
Refer pgRouting/pgrouting#1348