pgr_hawickCircuits - Experimental

pgr_hawickCircuits — Returns the list of cirucits using hawick circuits algorithm.

_images/boost-inside.jpeg

Warning

Possible server crash

  • These functions might create a server crash

Warning

Experimental functions

  • They are not officially of the current release.

  • They likely will not be officially be part of the next release:

    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL

    • Name might change.

    • Signature might change.

    • Functionality might change.

    • pgTap tests might be missing.

    • Might need c/c++ coding.

    • May lack documentation.

    • Documentation if any might need to be rewritten.

    • Documentation examples might need to be automatically generated.

    • Might need a lot of feedback from the comunity.

    • Might depend on a proposed function of pgRouting

    • Might depend on a deprecated function of pgRouting

Availability

  • Version 3.4.0

    • New experimental signature:

      • pgr_hawickCircuits

Description

Hawick Circuit algorithm, is published in 2008 by Ken Hawick and Health A. James. This algorithm solves the problem of detecting and enumerating circuits in graphs. It is capable of circuit enumeration in graphs with directed-arcs, multiple-arcs and self-arcs with a memory efficient and high-performance im-plementation. It is an extension of Johnson’s Algorithm of finding all the elementary circuits of a directed graph.

There are 2 variations defined in the Boost Graph Library. Here, we have implemented only 2nd as it serves the most suitable and practical usecase. In this variation we get the circuits after filtering out the circuits caused by parallel edges. Parallel edge circuits have more use cases when you want to count the no. of circuits.Maybe in future, we will also implemenent this variation.

The main Characteristics are:

  • The algorithm implementation works only for directed graph

  • It is a variation of Johnson’s algorithm for circuit enumeration.

  • The algorithm outputs the distinct circuits present in the graph.

  • Time Complexity: \(O((V + E) (c + 1))\)

    • where \(|E|\) is the number of edges in the graph,

    • \(|V|\) is the number of vertices in the graph.

    • \(|c|\) is the number of circuts in the graph.

Signatures

Summary

pgr_hawickCircuits(Edges SQL)
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Example:

Circuits present in the pgRouting Sample Data

SELECT * FROM pgr_hawickCircuits(
    'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
   1 |       1 |        0 |         1 |       1 |    1 |    6 |    1 |        0
   2 |       1 |        1 |         1 |       1 |    3 |    6 |    1 |        1
   3 |       1 |        2 |         1 |       1 |    1 |   -1 |    0 |        2
   4 |       2 |        0 |         3 |       3 |    3 |    7 |    1 |        0
   5 |       2 |        1 |         3 |       3 |    7 |    7 |    1 |        1
   6 |       2 |        2 |         3 |       3 |    3 |   -1 |    0 |        2
   7 |       3 |        0 |         7 |       7 |    7 |    4 |    1 |        0
   8 |       3 |        1 |         7 |       7 |    6 |    4 |    1 |        1
   9 |       3 |        2 |         7 |       7 |    7 |   -1 |    0 |        2
  10 |       4 |        0 |         7 |       7 |    7 |    8 |    1 |        0
  11 |       4 |        1 |         7 |       7 |   11 |    8 |    1 |        1
  12 |       4 |        2 |         7 |       7 |    7 |   -1 |    0 |        2
  13 |       5 |        0 |         7 |       7 |    7 |    8 |    1 |        0
  14 |       5 |        1 |         7 |       7 |   11 |   11 |    1 |        1
  15 |       5 |        2 |         7 |       7 |   12 |   13 |    1 |        2
  16 |       5 |        3 |         7 |       7 |   17 |   15 |    1 |        3
  17 |       5 |        4 |         7 |       7 |   16 |   16 |    1 |        4
  18 |       5 |        5 |         7 |       7 |   15 |    3 |    1 |        5
  19 |       5 |        6 |         7 |       7 |   10 |    2 |    1 |        6
  20 |       5 |        7 |         7 |       7 |    6 |    4 |    1 |        7
  21 |       5 |        8 |         7 |       7 |    7 |   -1 |    0 |        8
  22 |       6 |        0 |         7 |       7 |    7 |    8 |    1 |        0
  23 |       6 |        1 |         7 |       7 |   11 |    9 |    1 |        1
  24 |       6 |        2 |         7 |       7 |   16 |   16 |    1 |        2
  25 |       6 |        3 |         7 |       7 |   15 |    3 |    1 |        3
  26 |       6 |        4 |         7 |       7 |   10 |    2 |    1 |        4
  27 |       6 |        5 |         7 |       7 |    6 |    4 |    1 |        5
  28 |       6 |        6 |         7 |       7 |    7 |   -1 |    0 |        6
  29 |       7 |        0 |         7 |       7 |    7 |   10 |    1 |        0
  30 |       7 |        1 |         7 |       7 |    8 |   10 |    1 |        1
  31 |       7 |        2 |         7 |       7 |    7 |   -1 |    0 |        2
  32 |       8 |        0 |         7 |       7 |    7 |   10 |    1 |        0
  33 |       8 |        1 |         7 |       7 |    8 |   12 |    1 |        1
  34 |       8 |        2 |         7 |       7 |   12 |   13 |    1 |        2
  35 |       8 |        3 |         7 |       7 |   17 |   15 |    1 |        3
  36 |       8 |        4 |         7 |       7 |   16 |    9 |    1 |        4
  37 |       8 |        5 |         7 |       7 |   11 |    8 |    1 |        5
  38 |       8 |        6 |         7 |       7 |    7 |   -1 |    0 |        6
  39 |       9 |        0 |         7 |       7 |    7 |   10 |    1 |        0
  40 |       9 |        1 |         7 |       7 |    8 |   12 |    1 |        1
  41 |       9 |        2 |         7 |       7 |   12 |   13 |    1 |        2
  42 |       9 |        3 |         7 |       7 |   17 |   15 |    1 |        3
  43 |       9 |        4 |         7 |       7 |   16 |   16 |    1 |        4
  44 |       9 |        5 |         7 |       7 |   15 |    3 |    1 |        5
  45 |       9 |        6 |         7 |       7 |   10 |    2 |    1 |        6
  46 |       9 |        7 |         7 |       7 |    6 |    4 |    1 |        7
  47 |       9 |        8 |         7 |       7 |    7 |   -1 |    0 |        8
  48 |      10 |        0 |         7 |       7 |    7 |   10 |    1 |        0
  49 |      10 |        1 |         7 |       7 |    8 |   12 |    1 |        1
  50 |      10 |        2 |         7 |       7 |   12 |   13 |    1 |        2
  51 |      10 |        3 |         7 |       7 |   17 |   15 |    1 |        3
  52 |      10 |        4 |         7 |       7 |   16 |   16 |    1 |        4
  53 |      10 |        5 |         7 |       7 |   15 |    3 |    1 |        5
  54 |      10 |        6 |         7 |       7 |   10 |    5 |    1 |        6
  55 |      10 |        7 |         7 |       7 |   11 |    8 |    1 |        7
  56 |      10 |        8 |         7 |       7 |    7 |   -1 |    0 |        8
  57 |      11 |        0 |         6 |       6 |    6 |    1 |    1 |        0
  58 |      11 |        1 |         6 |       6 |    5 |    1 |    1 |        1
  59 |      11 |        2 |         6 |       6 |    6 |   -1 |    0 |        2
  60 |      12 |        0 |        10 |      10 |   10 |    5 |    1 |        0
  61 |      12 |        1 |        10 |      10 |   11 |   11 |    1 |        1
  62 |      12 |        2 |        10 |      10 |   12 |   13 |    1 |        2
  63 |      12 |        3 |        10 |      10 |   17 |   15 |    1 |        3
  64 |      12 |        4 |        10 |      10 |   16 |   16 |    1 |        4
  65 |      12 |        5 |        10 |      10 |   15 |    3 |    1 |        5
  66 |      12 |        6 |        10 |      10 |   10 |   -1 |    0 |        6
  67 |      13 |        0 |        10 |      10 |   10 |    5 |    1 |        0
  68 |      13 |        1 |        10 |      10 |   11 |    9 |    1 |        1
  69 |      13 |        2 |        10 |      10 |   16 |   16 |    1 |        2
  70 |      13 |        3 |        10 |      10 |   15 |    3 |    1 |        3
  71 |      13 |        4 |        10 |      10 |   10 |   -1 |    0 |        4
  72 |      14 |        0 |        11 |      11 |   11 |   11 |    1 |        0
  73 |      14 |        1 |        11 |      11 |   12 |   13 |    1 |        1
  74 |      14 |        2 |        11 |      11 |   17 |   15 |    1 |        2
  75 |      14 |        3 |        11 |      11 |   16 |    9 |    1 |        3
  76 |      14 |        4 |        11 |      11 |   11 |   -1 |    0 |        4
  77 |      15 |        0 |        11 |      11 |   11 |    9 |    1 |        0
  78 |      15 |        1 |        11 |      11 |   16 |    9 |    1 |        1
  79 |      15 |        2 |        11 |      11 |   11 |   -1 |    0 |        2
  80 |      16 |        0 |         8 |       8 |    8 |   14 |    1 |        0
  81 |      16 |        1 |         8 |       8 |    9 |   14 |    1 |        1
  82 |      16 |        2 |         8 |       8 |    8 |   -1 |    0 |        2
  83 |      17 |        0 |         2 |       2 |    2 |   17 |    1 |        0
  84 |      17 |        1 |         2 |       2 |    4 |   17 |    1 |        1
  85 |      17 |        2 |         2 |       2 |    2 |   -1 |    0 |        2
  86 |      18 |        0 |        13 |      13 |   13 |   18 |    1 |        0
  87 |      18 |        1 |        13 |      13 |   14 |   18 |    1 |        1
  88 |      18 |        2 |        13 |      13 |   13 |   -1 |    0 |        2
  89 |      19 |        0 |        17 |      17 |   17 |   15 |    1 |        0
  90 |      19 |        1 |        17 |      17 |   16 |   15 |    1 |        1
  91 |      19 |        2 |        17 |      17 |   17 |   -1 |    0 |        2
  92 |      20 |        0 |        16 |      16 |   16 |   16 |    1 |        0
  93 |      20 |        1 |        16 |      16 |   15 |   16 |    1 |        1
  94 |      20 |        2 |        16 |      16 |   16 |   -1 |    0 |        2
(94 rows)

Parameters

Parameter

Type

Default

Description

Edges SQL

TEXT

Edges SQL as described below.

Optional parameters

Column

Type

Default

Description

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected.

Inner Queries

Edges SQL

Column

Type

Default

Description

source

ANY-INTEGER

Identifier of the first end point vertex of the edge.

target

ANY-INTEGER

Identifier of the second end point vertex of the edge.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Return columns

Column

Type

Description

seq

INTEGER

Sequential value starting from 1

path_id

INTEGER

Id of the circuit starting from 1

path_seq

INTEGER

Relative postion in the path. Has value 0 for beginning of the path

start_vid

BIGINT

Identifier of the starting vertex of the circuit.

end_vid

BIGINT

Identifier of the ending vertex of the circuit.

node

BIGINT

Identifier of the node in the path from a vid to next vid.

edge

BIGINT

Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.

cost

FLOAT

Cost to traverse from node using edge to the next node in the path sequence.

agg_cost

FLOAT

Aggregate cost from start_v to node.

See Also

Indices and tables