PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages

Introduction

Note
This documentation is focused on the developer of pgr_contraction.
This documentation might include documentation used for the user.
The developer should also read the documentation for the user.

Contracting a graph becomes a crucial operation when talking about big graphs like the graphs involved in routing across cities, countries, continents or the whole world.

The contraction level and contraction operations can become very complex, as the complexity of the graphs grows.

For this proposal, we are making our contraction algorithm simple as possible so that more contraction operations can be added in the future.

We are not aiming with this work to implement all the possible contraction operations but to give a framework such that adding a contraction operation can be easily achieved.

For this contraction implementation, there are two operations:

  1. dead end contraction: vertices have one incoming edge
  2. linear contraction: vertices have one incoming and one outgoing edge

And with the additional characteristics:

  • The user can forbid to contract a particular set of nodes or edges.
  • The user can decide how many times the cycle can be done.
  • If possible, the user can decide the order of the operations on a cycle.

The contraction skeleton

In general we have an initial set up that may involve analizing the graph given as input and setting the non contractable nodes or edges. We have a cycle that will go and perform a contraction operation until while possible, and then move to the next contraction operation. Adding a new operation then becomes an "easy" task but more things might be involved, because the charachteristics of the graph change each time its contracted, so some interaction between contractions has to be implemented also.

Procedure

For contracting, we are going to cycle as follows

input: G(V,E)
removed_vertices = {}
<initial set up>
do N times {
while ( <conditions for 1> ) {
< contraction operation 1 >
}
while ( <conditions for 2> ) {
< contraction operation 2>
}
.....
}
output: G'(V',E'), removed_vertices

Notation for this documentation

  • V: is the set of vertices
  • E: is the set of edges
  • G: is the graph
  • V1: is the set of dead end vertices
  • V2: is the set of linear vertices
  • removed_vertices: is the set of removed vertices

The contracted graph will be represented with two parameters, the modified Graph, and the removed_vertices set.

removed_vertices = {(v,1):{2}, (e,-1):{3}}.

The above notation indicates:

  • Vertex 2 is removed, and belongs to vertex 1 subgraph
  • Vertex 3 is removed, and belongs to edge -1 subgraph

Dead End Contraction

Characteristics:

  • Contraction code: 1
  • V1: set of vertices with 1 incoming edge in increasing order of id:
  • Edges with the same identifier are considered the same edge and if it has the reverse_cost valid the outgoing edge is ignored
while ( V1 is not empty ) {
delete vertex of V1
the deleted vertex add it to removed_vertices
vertex that leads to removed vertex, inherits the removed vertex
<adjust any conditions that might affect other contraction operation>
}

Linear Contraction

Characteristics:

  • Contraction code: 2
  • V2: vertex with 1 incoming edge and 1 outgoing edge:
  • The outgoing edge must have different identifier of the incoming edge
while ( V2 is not empty ) {
delete vertex of V2
create edge (shortcut)
the deleted vertex add it to removed_vertices
newly created edge, inherits the removed vertex
<adjust any conditions that might affect other contraction operations>
}

Contraction examples

Dead End Contraction

  • For simplicity all the edges in the examples have unit weight.
  • Perform dead end contraction
  • One cycle of contractions.

Input:

G = {E:{1(1, 2)}, V:{1, 2} }

Visually the graph is

Todo:
(Rohith) practice a little graphviz :)
twoNodesoneEdge_a.png
dot_inline_dotgraph_1.png

Initial set up:

removed_vertices={}
V1 = {2}
V2 = {}

Procedure:

V1 = {2} is not empty
V1 = {}
V2 = {}
G = {V:{1}, E:{}}
removed_vertices = {(v, 1):{2}}.
V1 is empty

Results:

G = {V:{1}, E:{}}
removed_vertices = {(v, 1):{2}}
~~~~{.c}
Visually the graph is
@image html ../doc/images/twoNodesoneEdge_b.png
@subsection contraction_examples_linear Linear Contraction
@subsection contraction_examples_linear_dead_end Linear and Dead End Contraction
- For simplicity all the edges in the example have unit weight.
- A weight different than 1 will be expressed explicitly.
Perform linear contraction operation followed by a dead end operation.
1 cycle of contraction.
1. Input: G = {V:{1, 2, 3}, E:{(1, 2), (2, 3)}}
Visually the graph is
@image html ../doc/images/threeNodestwoEdges_a.png
2. initial set up
~~~~{.c}
removed_vertices={}
V1 = {3}
V2 = {2}
  1. Procedure
    V2 = {2} is not empty
    V1 = {3}
    removed_vertices = {(e, -1):{2}}
    V2 = {}
    G = {V:{1, 3}, E:{-1(1,3,c=2)}}
    V2 is empty

Visually the graph is

threeNodestwoEdges_b.png
  1. Since V2 is empty we go on to the next contraction operation
    V1 = {3} is not empty
    V1 = {}
    V2 = {}
    removed_vertices = {(v, 1):{3, 2}}.
    G = {V:{1}, E:{}}
    V1 is empty
  2. Results
    removed_vertices = {(v, 1):{3, 2}}.
    G = {V:{1}, E:{}}

Visually the graph is

threeNodestwoEdges_c.png

Contraction of Sample Data

  • A weight different than 1 will be expressed explicitly. Perform dead end operation follwed with a linear operation. 1 cycle of contraction.
  1. initial set up
    G = { V:{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17},
    E:{ 1(1, 2), 2(2,3), 3(3,4), 4(2,5),
    5(3,6), 6(7,8), 7(8,5), 8(5,6),
    9(6,9), 10(5,10), 11(6,11), 12(10,11),
    13(11,12), 14(10,13), 15(9,12), 16(4,9),
    17(14,15), 18(16,17) }
Todo:
(Rohith) add the id of each edge to the image

Visually the graph is

undirected_sampledata_a.png
  1. Initial set up:
    removed_vertices={}
    V1 = {1,7,13,14,15,16,17}
    V2 = {4,8,12}
  2. Dead end Contraction

The dead end vertices can visually be seen in the next graph.

  • The contraction is done in ascending order of the elements of V1
Todo:
(Rohith): add the id of each edge to the image, put a color to the dead end vertices
undirected_sampledata_a.png
V1 = {1,7,13,14,15,16,17} // is not empty
// Contracting Vertex 1
V1 = {7,13,14,15,16,17}
V2 = {2,4,8,12}
G = {V:{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17},
E:{2(2,3), 3(3,4), 4(2,5), 5(3,6), 6(7,8), 7(8,5), 8(5,6), 9(6,9),
10(5,10), 11(6,11), 12(10,11), 13(11,12), 14(10,13), 15(9,12), 16(4,9), 17(14,15), 18(16,17)}}
removed_vertices = {(v, 2):{1}}.
V1 = {7,13,14,15,16,17} // is not empty
// Contracting Vertex 7
V1 = {8,13,14,15,16,17}
V2 = {2,4,12}
G = {V:{2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17},
E:{2(2,3), 3(3,4), 4(2,5), 5(3,6), 7(8,5), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 14(10,13), 15(9,12), 16(4,9), 17(14,15), 18(16,17)}}
removed_vertices = {(v, 2):{1}, (v,8):{7}}.
V1 = {8,13,14,15,16,17} // is not empty
// Contracting Vertex 8
V1 = {13,14,15,16,17}
V2 = {2,4,12}
G = {V:{2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15, 16, 17},
E:{2(2,3), 3(3,4), 4(2,5), 5(3,6), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 14(10,13), 15(9,12), 16(4,9), 17(14,15), 18(16,17)}}
removed_vertices = {(v, 2):{1}, (v,5):{8,7}}.
V1 = {13,14,15,16,17} // is not empty
// Contracting Vertex 13
V1 = {14,15,16,17}
V2 = {2,4,10,12}
G = {V:{2, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 16, 17},
E:{2(2,3), 3(3,4), 4(2,5), 5(3,6), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 15(9,12), 16(4,9), 17(14,15), 18(16,17)}}
removed_vertices = {(v, 2):{1}, (v,5):{8,7}, (v,10):{13}}.
V1 = {14,15,16,17} // is not empty
// Contracting Vertex 14
V1 = {16,17} // vertex 15 now is not a Dead End vertex
V2 = {2,4,10,12}
G = {V:{2, 3, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17},
E:{2(2,3), 3(3,4), 4(2,5), 5(3,6), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 15(9,12), 16(4,9)}, 18(16,17)}
removed_vertices = {(v, 2):{1}, (v,5):{8,7}, (v,10):{13}, (v,15):{14}}.
V1 = {16,17} // is not empty
// Contracting Vertex 14
V1 = {} // vertex 17 now is not a Dead End vertex
V2 = {2,4,10,12}
G = {V:{2, 3, 4, 5, 6, 9, 10, 11, 12, 15, 17},
E:{2(2,3), 3(3,4), 4(2,5), 5(3,6), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 15(9,12), 16(4,9)}}
removed_vertices = {(v, 2):{1}, (v,5):{8,7}, (v,10):{13}, (v,15):{14}, (v,17):{16}}.

3- Since V1 is empty, linear contraction is performed

The linear vertices can visually be seen in the next graph.

  • The contraction is done in ascending order of the elements of V2
Todo:
(Rohith) add the id of each edge to the image, put a color to the linear vertices
undirected_sampledata_b.png
V2 = {2,4,10,12} // is not empty
// Contracting Vertex 2
V1 = {}
V2 = {4,10,12}
G = {V:{3, 4, 5, 6, 9, 10, 11, 12, 15, 17},
E:{-1(3,5), 3(3,4), 5(3,6), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 15(9,12), 16(4,9)}}
removed_vertices = {(e, -1):{1,2}, (v, 2):{1}, (v,5):{8,7}, (v,10):{13}, (v,15):{14}, (v,17):{16}}.
V2 = {4,10,12} // is not empty
// Contracting Vertex 4
V1 = {}
V2 = {10,12}
G = {V:{3, 5, 6, 9, 10, 11, 12, 15, 17},
E:{-1(3,5),-2(3,9), 5(3,6), 8(5,6), 9(6,9), 10(5,10),
11(6,11), 12(10,11), 13(11,12), 15(9,12)}}
removed_vertices = {(e, -1):{1,2}, (e, -2):{4}, (v, 2):{1}, (v,5):{8,7}, (v,10):{13}, (v,15):{14}, (v,17):{16}}.
V2 = {10,12} // is not empty
// Contracting Vertex 10
V1 = {}
V2 = {12}
G = {V:{3, 5, 6, 9, 11, 12, 15, 17},
E:{-1(3,5),-2(3,9), -3(5,11), 5(3,6), 8(5,6), 9(6,9),
11(6,11), 13(11,12), 15(9,12)}}
removed_vertices = {(e, -1):{1,2}, (e, -2):{4}, (e,-3):{10,13}, (v, 2):{1}, (v,5):{8,7}, (v,15):{14}, (v,17):{16}}.
V2 = {12} // is not empty
// Contracting Vertex 12
V1 = {}
V2 = {}
G = {V:{3, 5, 6, 9, 11, 15, 17},
E:{-1(3,5),-2(3,9), -3(5,11), -4(9,11), 5(3,6), 8(5,6), 9(6,9), 11(6,11)}}
removed_vertices = {(e, -1):{1,2}, (e, -2):{4}, (e,-3):{10,13}, (e, -4):{12},
(v, 2):{1}, (v,5):{8,7}, (v,15):{14}, (v,17):{16}}.
  1. Results:
    G = {V:{3, 5, 6, 9, 11, 15, 17},
    E:{-1(3,5),-2(3,9), -3(5,11), -4(9,11), 5(3,6), 8(5,6), 9(6,9), 11(6,11)}}
    removed_vertices = {(e, -1):{1,2}, (e, -2):{4}, (e,-3):{10,13}, (e, -4):{12},
    (v, 2):{1}, (v,5):{8,7}, (v,15):{14}, (v,17):{16}}.
    Visually the graph is
    undirected_sampledata_b.png

Generating the contracted graph

Original Data:

.. literalinclude:: doc-contraction.queries :start-after: – q1 :end-before: – q2

:Addition of new columns:

.. code-block:: sql

ALTER TABLE edge_table ADD is_contracted BOOLEAN DEFAULT false
ALTER TABLE edge_table ADD contracted_vertices BIGINT[]

Data After Adding Columns:

.. literalinclude:: doc-contraction.queries
:start-after: -- q4
:end-before: -- q5

Addition of new edges by the algorithm:

.. code-block:: sql

INSERT INTO edge_table(id, source, target, cost, reverse_cost, is_contracted, contracted_vertices) VALUES (-1, 3, 5, 2, 2, true, ARRAY[1, 2])
INSERT INTO edge_table(id, source, target, cost, reverse_cost, is_contracted, contracted_vertices) VALUES (-2, 3, 9, 2, 2, true, ARRAY[4])
INSERT INTO edge_table(id, source, target, cost, reverse_cost, is_contracted, contracted_vertices) VALUES (-3, 5, 11, 2, 2, true, ARRAY[10, 13])
INSERT INTO edge_table(id, source, target, cost, reverse_cost, is_contracted, contracted_vertices) VALUES (-4, 9, 11, 2, 2, true, ARRAY[12])

Data after addition of new edges:

.. literalinclude:: doc-contraction.queries :start-after: – q9 :end-before: – q10

Contracted Graph Data:

.. literalinclude:: doc-contraction.queries :start-after: – q10 :end-before: – q11

Dijkstra on contracted graph

There are five cases which arise when calculating the shortest path between a given source and target,

Case 1**: Both source and target belong to the contracted graph.

Case 2**: Source belongs to a contracted graph, while target belongs to a vertex subgraph.

Case 3**: Source belongs to a contracted graph, while target belongs to an edge subgraph.

Case 4**: Source belongs to a vertex subgraph, while target belongs to an edge subgraph.

Case 5**: The path contains a new edge added by the contraction algorithm.

source and target belong to the contracted graph

Routing from 3 to 11. Since 3 and 11 both are in the contracted graph it is not necessary expand the graph.

.. literalinclude:: doc-contraction.queries :start-after: – q11 :end-before: – q12

Source belongs to a contracted graph, while target belongs to a vertex subgraph.

Routing from 3 to 7. Since 7 is in the contracted subgraph of vertex 5, it is necessary to expand that vertex by adding {7, 8} to the vertex set, so the vertex set becomes {3, 5, 6, 9, 11, 15, 17 , 7, 8}

.. literalinclude:: doc-contraction.queries :start-after: – q12 :end-before: – q13

Source belongs to a contracted graph, while target belongs to an edge subgraph.

Routing from 3 to 13. Since 13 is in the contracted subgraph of edge (5, 11), it is necessary to expand that edge by adding {10, 13} to the vertex set, so the vertex set becomes {3, 5, 6, 9, 10, 11, 13, 15, 17}.

.. literalinclude:: doc-contraction.queries :start-after: – q13 :end-before: – q14

Source belongs to a vertex subgraph, while target belongs to an edge subgraph.

Routing from 7 to 13.i

  • Since 13 is in the contracted subgraph of edge (5, 11), it is necessary to expand that edge by adding {10, 13} to the vertex set,
  • and since 7 is in the contracted subgraph of vertex 5, it is necessary to expand that vertex by adding {7, 8} vertex set,
  • so the vertex set becomes {3, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17}

.. literalinclude:: doc-contraction.queries :start-after: – q14 :end-before: – q15

The path contains a new edge added by the contraction algorithm.

Routing from 3 to 9. Since 3 and 9 both are in the contracted graph it is not necessary expand the graph.

.. literalinclude:: doc-contraction.queries :start-after: – q15 :end-before: – q16

.. literalinclude:: doc-contraction.queries :start-after: – q16 :end-before: – q17

  • This implies that it is a shortcut and should be expanded.
  • The contracted subgraph of edge 20(3, 9, c=2) is {4}.
  • It is necessary to expand the edge by adding {4} to the vertex set,
  • so the vertex set becomes {3, 4, 5, 6, 9, 11, 15, 17}.

.. literalinclude:: doc-contraction.queries :start-after: – q17 :end-before: – q18

References

http://www.cs.cmu.edu/afs/cs/academic/class/15210-f12/www/lectures/lecture16.pdf

http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf