# pgr_chinesePostman - Experimental¶

pgr_chinesePostman — Calculates the shortest circuit path which contains every edge in a directed graph and starts and ends on the same vertex.

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.0.0

• New experimental function

## Description¶

The main characteristics are:

• Process is done only on edges with positive costs.

• Running time: $$O(E * (E + V * logV))$$

• Graph must be connected.

• Returns EMPTY SET on a disconnected graph

## Signatures¶

pgr_chinesePostman(edges_sql)
RETURNS SET OF (seq, node, edge, cost, agg_cost)
OR EMPTY SET

Example

SELECT * FROM pgr_chinesePostman(
'SELECT id,
source, target,
cost, reverse_cost FROM edge_table where id < 17'
);
seq | node | edge | cost | agg_cost
-----+------+------+------+----------
1 |    1 |    1 |    1 |        0
2 |    2 |    4 |    1 |        1
3 |    5 |    4 |    1 |        2
4 |    2 |    4 |    1 |        3
5 |    5 |    7 |    1 |        4
6 |    8 |    6 |    1 |        5
7 |    7 |    6 |    1 |        6
8 |    8 |    7 |    1 |        7
9 |    5 |    8 |    1 |        8
10 |    6 |    8 |    1 |        9
11 |    5 |   10 |    1 |       10
12 |   10 |   10 |    1 |       11
13 |    5 |   10 |    1 |       12
14 |   10 |   14 |    1 |       13
15 |   13 |   14 |    1 |       14
16 |   10 |   12 |    1 |       15
17 |   11 |   13 |    1 |       16
18 |   12 |   15 |    1 |       17
19 |    9 |    9 |    1 |       18
20 |    6 |    9 |    1 |       19
21 |    9 |   15 |    1 |       20
22 |   12 |   15 |    1 |       21
23 |    9 |   16 |    1 |       22
24 |    4 |    3 |    1 |       23
25 |    3 |    5 |    1 |       24
26 |    6 |   11 |    1 |       25
27 |   11 |   13 |    1 |       26
28 |   12 |   15 |    1 |       27
29 |    9 |   16 |    1 |       28
30 |    4 |   16 |    1 |       29
31 |    9 |   16 |    1 |       30
32 |    4 |    3 |    1 |       31
33 |    3 |    2 |    1 |       32
34 |    2 |    1 |    1 |       33
35 |    1 |   -1 |    0 |       34
(35 rows)



## Parameters¶

Column

Type

Default

Description

edges_sql

TEXT

The edges SQL query as described in Inner query.

## Inner query¶

An Edges SQL that represents a directed graph with the following columns

Column

Type

Default

Description

id

ANY-INTEGER

Identifier of the edge.

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)

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

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¶

Returns set of (seq, node, edge, cost, agg_cost)

Column

Type

Description

seq

INT

Sequential value starting from 1.

node

BIGINT

Identifier of the node in the path from start_vid to end_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.