# pgRouting Manual (3.6)

## pgr_hawickCircuits - Experimental

# `pgr_hawickCircuits - Experimental`

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

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`

## Result 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

- Sample Data

- Boost: Hawick Circuit Algorithm

Indices and tables

- Index

- Search Page