vicennial / gsoc-pgrouting

Semi-mirror repository for GSoC students work

pgRouting - Routing on PostgreSQL

STATUS

Branches

• The master branch has the release 2.6.1
• The release/2.5 branch has the next micro-release 2.5.4 (if needed)
• The develop branch has the development of the next release 3.0.0-dev

For the complete list of releases go to: https://github.com/pgRouting/pgrouting/releases

LINKS

• https://pgrouting.org/
• https://docs.pgrouting.org/
• https://workshop.pgrouting.org/
• https://github.com/pgRouting/pgrouting

Branch	Travis	Appveyor	Jenkins	Comments
master
develop
gh-pages				not enabled

• travis: Postgis 2.3.3 for Postgres 9.5 & 9.6

  • precise
  • developed with Postgres 9.3 and Postgis 2.3.3

• jenkins: g++ 4.8 on 32 & 64 bits for Postgis 2.4.0dev and Postgres 9.5, 9.6, 10

• appveyor: vs1013 Postgis 2.3.3 on Postgres 9.4

INTRODUCTION

pgRouting extends the PostGIS/PostgreSQL geospatial database to provide geospatial routing and other network analysis functionality.

This library contains following features:

• All Pairs Shortest Path, Johnson’s Algorithm
• All Pairs Shortest Path, Floyd-Warshall Algorithm
• Shortest Path A*
• Bi-directional Dijkstra Shortest Path
• Bi-directional A* Shortest Path
• Shortest Path Dijkstra Family of functions
• Shortest Path Dijkstra Cost Family of functions
• Driving Distance
• K-Shortest Path, Multiple Alternative Paths (Yen's algorithm)
• Traveling Sales Person (TSP)
• Turn Restriction Shortest Path (TRSP)

Additionally, ready for testing and to be part of 2.5 official version:

• Shortest Path Dijkstra With Points Family of functions
• Shortest Path Dijkstra Cost With Points Family of functions
• Driving Distance With Points
• K-Shortest Path With Points, Multiple Alternative Paths (Yen's algorithm)
• Dijkstra Via (Vertices)

and many more.

Family of functions include:

• one to one
• one to many
• many to one
• many to many

REQUIREMENTS

Building reqirements

• Perl
• C and C++ compilers
  • GNU >= 4.6
  • MSVC >= 18.0
• Postgresql >= 9.2
• The Boost Graph Library (BGL) >= 1.53
• CMake >= 3.2
• CGAL >= 4.4
• Sphinx >= 1.2

User's reqirements

• PostGIS >= 2.0

INSTALLATION

See online documentation: https://docs.pgrouting.org/

COMPILATION

For MinGW on Windows

mkdir build
cd build
cmake -G"MSYS Makefiles" ..
make
make install

Also pre-built Windows binaries can be downloaded from https://postgis.net/windows_downloads

For Linux

mkdir build
cd build
cmake  ..
make
sudo make install

Build with documentation (requires Sphinx)

cmake -DWITH_DOC=ON ..

Postgresql 9.2+

createdb mydatabase
psql mydatabase -c "CREATE EXTENSION postgis"
psql mydatabase -c "CREATE EXTENSION pgrouting"

USAGE

See online documentation: https://docs.pgrouting.org/dev/en/index.html

LICENSE

• Most features are available under GPLv2.
• Some Boost extensions are available under Boost license (see LICENSE_1_0.txt)
• Some code contributed by iMaptools.com is available under MIT-X license.

gsoc-pgrouting's Issues

Get familiar with C++

• https://www.youtube.com/watch?v=eidEEmGLQcU
  • Make Report as comment on this issue
• https://www.youtube.com/watch?v=u5senBJUkPc
  • Make Report as comment on this issue
• https://www.youtube.com/watch?v=YnWhqhNdYyk
  • Make Report as comment on this issue
• https://www.youtube.com/watch?v=1OEu9C51K2A
  • Make Report as comment on this issue
• https://www.youtube.com/watch?v=xnqTKD8uD64
  • Make Report as comment on this issue
• https://www.youtube.com/watch?v=86xWVb4XIyE
  • Make Report as comment on this issue

Follow the Workshop Up to Chapter 5

• Chapter 1
• Chapter 2
• Chapter 3
• Chapter 4
• Chapter 5

Get familiar with pgRouting on Github

• Start on develop branch
• Make up an issue (on GSoC-project)
• Propose the solution for the issue you made up
• Submit a pull request to develop.

Path-finding Animations of Proposed Algorithms

Algorithms

• Breadth First Search
• Binary Breadth First Search
• Edward Moore's Algorithm

Terminology

Node Color	Meaning
No color	Node has not been found yet.
Grey	Node found and added to queue but hasn’t been processed yet.
Blue	Node is currently being processed.
Red	Node has been processed (But might be processed again in the future).
Green	Node is part of optimal path.

Typo in pgr_extractVertices.rst

Expected behavior and actual behavior

Expected spelling: below
Actual spelling: bellow

Steps to reproduce the problem

Open the file pgr_extractVertices.rst located in GSoC-pgRouting/doc/topology/pgr_extractVertices.rst

Specifications like the version of pgRouting/PostGIS and PostgreSQL as well as Operating System

• PostgreSQL 10.7
• Ubuntu 5.4.0
• PostGIS 2.5.2
• pgRouting 3.0.0

Solution

Change the text bellow to below in file GSoC-pgRouting/doc/topology/pgr_extractVertices.rst.

Build locally pgRouting

• Install requirements
• build locally pgRouting v2.6
• build locally pgRouting v3.0-dev