Animations of the Proposed Algorithms

[krashish8]

Algorithms

• Undirected Depth First Search
• Sequential Vertex Coloring
• Depth First Search (Directed)
• Maximum Adjacency Search

Terminology

For Undirected Depth First Search and Depth First Search (Directed)

Node / Edge Representation	Meaning
	Vertex is not visited
	Vertex is currently processing
	Vertex is visited
	Vertex is visited and processed
	Edge is not visited
	Edge is visited
	Edge is visited and processed (while backtracking)

For Sequential Vertex Coloring

Color Value	Meaning
0	Yellow
1	Blue

For Maximum Adjacency Search

Node / Edge Representation	Meaning
	Vertex is not visited
	Vertex is currently processing
	Vertex is visited and processed

[krashish8]

pgRouting Sample Data

Query

SELECT id, source, target, cost, reverse_cost FROM edge_table;

Output

 id | source | target | cost | reverse_cost 
----+--------+--------+------+--------------
  1 |      1 |      2 |    1 |            1
  2 |      2 |      3 |   -1 |            1
  3 |      3 |      4 |   -1 |            1
  4 |      2 |      5 |    1 |            1
  5 |      3 |      6 |    1 |           -1
  6 |      7 |      8 |    1 |            1
  7 |      8 |      5 |    1 |            1
  8 |      5 |      6 |    1 |            1
  9 |      6 |      9 |    1 |            1
 10 |      5 |     10 |    1 |            1
 11 |      6 |     11 |    1 |           -1
 12 |     10 |     11 |    1 |           -1
 13 |     11 |     12 |    1 |           -1
 14 |     10 |     13 |    1 |            1
 15 |      9 |     12 |    1 |            1
 16 |      4 |      9 |    1 |            1
 17 |     14 |     15 |    1 |            1
 18 |     16 |     17 |    1 |            1
(18 rows)

[krashish8]

Undirected Depth First Search

Query

SELECT * FROM pgr_depthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id',
    1, directed => false
);

Order of Traversal of Vertices

1 → 2 → 3 → 4 → 9 → 6 → 5 → 8 → 7 → 10 → 11 → 12 → 13

Animation

Output

 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         1 |    1 |   -1 |    0 |        0
   2 |     1 |         1 |    2 |    1 |    1 |        1
   3 |     2 |         1 |    3 |    2 |    1 |        2
   4 |     3 |         1 |    4 |    3 |    1 |        3
   5 |     4 |         1 |    9 |   16 |    1 |        4
   6 |     5 |         1 |    6 |    9 |    1 |        5
   7 |     6 |         1 |    5 |    8 |    1 |        6
   8 |     7 |         1 |    8 |    7 |    1 |        7
   9 |     8 |         1 |    7 |    6 |    1 |        8
  10 |     7 |         1 |   10 |   10 |    1 |        7
  11 |     8 |         1 |   11 |   12 |    1 |        8
  12 |     9 |         1 |   12 |   13 |    1 |        9
  13 |     8 |         1 |   13 |   14 |    1 |        8
(13 rows)

Note

In case two or more vertices are at the same depth, whichever vertex comes first in the edges_sql is visited first.

[krashish8]

Sequential Vertex Coloring

Query

SELECT * FROM pgr_sequentialVertexColoring(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id'
);

Animation

Output

 seq | node | color 
-----+------+-------
   1 |    1 |     0
   2 |    2 |     1
   3 |    3 |     0
   4 |    4 |     1
   5 |    5 |     0
   6 |    6 |     1
   7 |    7 |     0
   8 |    8 |     1
   9 |    9 |     0
  10 |   10 |     1
  11 |   11 |     0
  12 |   12 |     1
  13 |   13 |     0
  14 |   14 |     0
  15 |   15 |     1
  16 |   16 |     0
  17 |   17 |     1
(17 rows)

[krashish8]

Depth First Search (Directed)

Query

SELECT * FROM pgr_depthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
     ORDER BY id',
     1
);

Order of Traversal of Vertices

1 → 2 → 5 → 8 → 7 → 6 → 9 → 12 → 4 → 3 → 11 → 10 → 13

Animation

Output

 seq | depth | start_vid | node | edge | cost | agg_cost  
-----+-------+-----------+------+------+------+----------
   1 |     0 |         1 |    1 |   -1 |    0 |       0
   2 |     1 |         1 |    2 |    1 |    1 |       1
   3 |     2 |         1 |    5 |    4 |    1 |       2
   4 |     3 |         1 |    8 |    7 |    1 |       3
   5 |     4 |         1 |    7 |    6 |    1 |       4
   6 |     3 |         1 |    6 |    8 |    1 |       3
   7 |     4 |         1 |    9 |    9 |    1 |       4
   8 |     5 |         1 |   12 |   15 |    1 |       5
   9 |     5 |         1 |    4 |   16 |    1 |       5
  10 |     6 |         1 |    3 |    3 |    1 |       6  
  11 |     4 |         1 |   11 |   11 |    1 |       4  
  12 |     3 |         1 |   10 |   10 |    1 |       3  
  13 |     4 |         1 |   13 |   14 |    1 |       4  
(13 rows)

Note

If multiple vertices are adjacent to a given vertex, then in this implementation, that vertex is visited first, which comes first in the edge_table.

[krashish8]

Maximum Adjacency Search

Query

SELECT * FROM pgr_maximumAdjacencySeaerch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
     WHERE id < 17
     ORDER BY id',
     1
);

Order of Traversal of Vertices

1 → 2 → 5 → 10 → 13 → 11 → 6 → 3 → 12 → 9 → 4 → 8 → 7

Animation

Output

 seq | start_vid | node | edge | cost | agg_cost  
-----+-----------+------+------+------+----------
   1 |         1 |    1 |   -1 |    0 |       0
   2 |         1 |    2 |    1 |    1 |       1
   3 |         1 |    5 |    4 |    1 |       2
   4 |         1 |   10 |   10 |    1 |       3
   5 |         1 |   13 |   14 |    1 |       4
   6 |         1 |   11 |   12 |    1 |       5
   7 |         1 |    6 |   11 |    1 |       6
   8 |         1 |    3 |    5 |    1 |       7
   9 |         1 |   12 |   13 |    1 |       8
  10 |         1 |    9 |   15 |    1 |       9  
  11 |         1 |    4 |   16 |    1 |      10  
  12 |         1 |    8 |    7 |    1 |      11  
  13 |         1 |    7 |    6 |    1 |      12  
(13 rows)

Note

In case of clashes when several vertices are 'tightly connected' to the selected set of vertices, that vertex is visited next (in this implementation) which has a higher vertex_id as compared to other vertices.