GSoC 2017 Connected Components - pgRouting/pgrouting GitHub Wiki
Table of Contents
- Proposal
- Branch
- Reports
- References
Proposal
Brief Description
Connected components algorithms are used to analyze graph and solve problems (like 2-satisfiability problem). There are three parts of connected components algorithms in the Boost Graph Library (BGL),
- Connected components algorithm. A connected component of an undirected graph is a set of vertices that all reachable from each other.
- Strongly connected components algorithm. A strongly connected components of an directed graph is a set of vertices that all reachable from each other.
- Biconnected components algorithm. The biconnected components of a graph are the maximal subsets of vertices such that removal of a vertex from a particular component will not disconnect the component.
This project aims to add those functionalities to pgRouting.
State of the project before GSoC
Previously there is no functionality which analyzes connected components in the library.
Proposal pdf
Slides
- Connected components
- Strongly connected components
- Biconnected components
- Articulation Points
- Bridges
Branch
https://github.com/pgRouting/pgrouting/tree/gsoc-component
Reports
Week 12
Fix documentation and prepare for final evaluation
PR: https://github.com/pgRouting/pgrouting/pull/918
- added index in docs
- removed Minimal Use
- updated articulation points & bridges in repo ExampleCode
- updated images in repo ExampleCode
- wrote slides for articulation points & bridges
Week 11
Improve the code and docs
PR: https://github.com/pgRouting/pgrouting/pull/902
- fix links in docs
- lint the code
- fix AppVeyor warnings
- remove the V from the name of the functions
Week 10
Documentation and tests of pgr_bridges
PR: https://github.com/pgRouting/pgrouting/pull/892
- wrote documentation of
pgr_bridges
- create documentation tests of
pgr_bridges
- modified
CMakeLists.txt
- fixed documentation warnings
- created images for
pgr_bridges
Fix AppVoyer
PR: https://github.com/pgRouting/pgrouting/pull/892
- changed
PG_VERSION
to2.3.3
- merged
upstream/develop
- changed
PG_VERSION
to2.3.2
Week 9
Implement pgr_bridges
PR: https://github.com/pgRouting/pgrouting/pull/886
- created & modified
.c
&_driver.cpp
files - created
_driver.h
and.sql
files - modified
CMakeLists.txt
- implemented bridges
- fixed compile errors
Week 8
Report for three possible options for more functionality in pgRouting using the connected components functions.
Graph partition
A k-way partition divides the vertex set into k smaller components. A good partition is defined as one in which the number (capacity) of edges running between separated components is small. The graph partition problem finds the best partition of a graph.
Unfortunately, the graph partition problem is one of the NP-hard problems. And methods of this problem are complicated. In my opinion, this implementation would be very hard.
Connected-component labeling
Connected-component labeling divides vertices into connected subsets and labels each subset to one color. Connected-component labeling is widely used in computer vision (I think this application maybe is not suitable with pgRouting).
There are two algorithms: One component at a time, Two-pass. The first algorithm is similar with connected_components in Boost. And the second one only works on 2-dimensional (images).
The implementation of Two-pass algorithm would be hard.
Bridge
In graph theory, a bridge is an edge of a graph whose deletion increases its number of connected components.
Tarjan's Bridge-Finding algorithm is a linear time algorithm for finding bridges in a graph. Unfortunately I didn't find a function for bridge in Boost. But I'm familiar with this algorithm.
The difficulty of this implementation would be medium.
Week 7
Implement pgr_articulationPoints
PR: https://github.com/pgRouting/pgrouting/pull/877
- created & modified
.c
&_driver.cpp
files - created
_driver.h
and.sql
files - modified
CMakeLists.txt
- implemented articulation points by BGL
- fixed compile errors
- created documentation tests
- wrote documentation (including modified family page)
- fixed images
Week 6
Fix mapbender chinese images
PR: https://github.com/OSGeo/OSGeoLive-doc/pull/258
- fixed some of the images names of mapbender in the Chinese translation
Improve code and documentation
PR 1: https://github.com/pgRouting/pgrouting/pull/870)
PR 2: https://github.com/pgRouting/pgrouting/pull/875
- lint the code of components
- fix code warnings
- fix documentation warnings
- add examples to family page
- add images for examples in family page
Week 5
Write documentation for components functions
PR: https://github.com/pgRouting/pgrouting/pull/866
- added components functions to
release_notes.rst
andproposed.rst
- wrote Synopsis & Characteristics & Signatures & See also (cc)
- made family page
- wrote documentation of scc
- wrote documentation of bcc
Extend Pgr_base_graph to fix duplicates
PR: https://github.com/pgRouting/pgrouting/pull/865
- created
pgr_componentsGraph.hpp
file and extendedPgr_base_graph
in it - fixed duplicates
- modified
_driver.cpp
(connected and biconnected) - created documentation tests for biconnected components
Week 4
Implement pgr_biconnectedComponents
PR: https://github.com/pgRouting/pgrouting/pull/862
- generated
.c
&_driver.cpp
files - modified
.c
&_driver.cpp
files - created
_rt.h
file - created
_driver.h
and.sql
files - used
identifier
instead ofnode
andedge
- implemented biconnected components by BGL
Improve code of connected components and strongly connected components
PR: https://github.com/pgRouting/pgrouting/pull/858
- changed to
pgr_componentsV_rt
- removed
V_to_id
- removed
sort_cmp
& used lamda - changed to
sort
andstable_sort
- changed to range loop
- fixed appvoyer
Week 3
Create documentation tests for pgr_strongComponentsV
PR: https://github.com/pgRouting/pgrouting/pull/855
- created
.test.sql
file and.result
file - modified
test.conf
- generated
.queries
file byalgorithm-tester.pl
Implement pgr_strongComponentsV
PR: https://github.com/pgRouting/pgrouting/pull/853
- copied code from
pgr_connectedComponentsV
- modified C/C++ files (including header)
- changed undirected graph to directed graph
- added
pgr_strongComponentsV
to CMakeLists - created sql file
- fixed compile errors
Week 2
Implement pgr_connectedCompoentsV
PR: https://github.com/pgRouting/pgrouting/pull/815
- implemented
pgr_connectedComponentsV
by BGL - created
std::map
(V_to_id) for mapping - made node number be correct
- made component number be correct
- sorted results
- made
n_seq
number be correct - changed function names and variable names
- linted the code
Keep up-to-date with develop
PR: https://github.com/pgRouting/pgrouting/pull/812
- created new branch (test/merge), and worked on that branch
- moved documentation files to new location
- moved queies file to new location
- changed the name of this object to shorter name (connectedComponentsV -> components)
- fixed directory name
- fixed
CMakeLists.txt
Create new header file for components
PR: https://github.com/pgRouting/pgrouting/pull/812
- copied from dijkstra
- modified class names & author info
- modified C/C++ files to use
pgr_components.hpp
- wrapped the unused code
- deleted the unused code
Week 1
Create new structure named pgr_componentV_t
PR: https://github.com/pgRouting/pgrouting/pull/805
- created
pgr_componentV_t
- modified C & C++ files using the new structure
- deleted the line that compiler complains & added TODO
Create initial Template code
PR: https://github.com/pgRouting/pgrouting/pull/804
- Added initial code for
pgr_connectedComponentsV
- fixed parameters
- wrote comments & TODO
- fixed
fn_dijkstra.dijkstra
- modified
test.conf
to remove tests
Bonding
Fix the installation of PostGIS on AppVoyer
- AppVeyor: changed
PG_VERSION
to2.3.2
in the build because2.3.1
is no longer availabe. Here is the contents of the site where it gets the binaires http://winnie.postgis.net/download/windows/pg94/buildbot/ - updated to latest changes on develop
Get familiar with C++
Watch videos about C++:
- https://www.youtube.com/watch?v=1OEu9C51K2A
- https://www.youtube.com/watch?v=YnWhqhNdYyk
- https://www.youtube.com/watch?v=u5senBJUkPc
Practice teamwork
- use
create.sh
to create my dijkstra - make a PR to Vicky's fork
- fix appvoyer
Set up my wiki page
A wiki page contains
- A brief introduction about your project
- Plan for the week
- A detailed list of tasks you need to accomplish during the week
- Links to your weekly reports
Table of contents
Links, don't open a page, must be in the same page.
- Have a look at
Weekly reports
Send a report to the mailing list and copy it to wiki page weekly. Do mention about my meetings with the mentors in the weekly reports.
- Have a section which has the links to all the weekly report. For example,
GSoC practice linting
Learning the basics of linting code
depart from develop: (updated the fork)
git checkout develop
git checkout -b lint/trsp
git push
do the linting
git push
and make a pull request to main repo's develop
lint src/trsp/src/GraphDefinition.h
- update my fork
- depart from develop
- linting
- make a pull request
Pre Bonding
Get familiar with C++
Watch videos about C++:
Improve proposal
- write and commit sample sql code for demo slides to repo "ExampleCode".
- find more applications of connected components algorithms.
- reconsider timeline, try to make it better.
- complete references.
- recheck code.
- format text with a standard font size.
- remove references, add footnotes.
- remove 'link', add link to the text.
- enhance timeline to reflect these needs.
- fix a link error in 'Benefits to Community' ('Read more')
- fix grammer mistakes.
- add
cost
andreverse_cost
parameters to those three proposed functions. - add new reference ( pgRouting sample data )
- investigate
pgr_labelGraph
. If it can be replaced with one of those three proposed functions, write about it in proposal. - add a new line to 'Attention' which has descriptions of the proposed sql queries. (use dijkstra like inner queries ).
- analyze pgRouting Sample Data.
Study git branching model & commands
links to study:
Fix warning
for loops to range loops(dont forget the &)
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L116
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L160
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L317
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L506
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L600
using auto
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L107
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L114
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L119
more
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L135
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L349
- https://github.com/pgRouting/pgrouting/blob/develop/src/trsp/src/GraphDefinition.cpp#L635
example of a commit(with a meaningful message)
git commit -a -m 'fixing a for loop to range loop'
meaningful examples
for(ruleIndex = 0; ruleIndex < totalRule; ruleIndex++)
bool flag = true;
int total_edge = vecRules[ruleIndex].precedencelist.size();
to
for (const auto &rule : vecRules )
bool flag = true;
auto total_edge = rule.precedencelist.size();
Get familiar with pgRouting on Github
Currently trsp compilation has lots of problems:
- Files that start with /usr/include/postgresql/9.6/server/ are not pgRouting files so they can not be modified.
- Files that start with home/travis/build/pgRouting/pgrouting/ belong to pgRouting and they can be modified.
- Start on develop branch
- Choose a compilation warning on a file that belongs to pgRouting
- Propose a solution to remove the warning
- Submit a pull request to develop.
Initial tasks
- Install Ubuntu 16.04.2 LTS Desktop
- Dependencies Installation
- Compiling pgRouting
- Create an account on Travis and on AppVeyor
- Be familiar with git
- Read carefully pgRouting Developer's Documentation
- Read carefully https://summerofcode.withgoogle.com/terms/student
- Write a proposal
- Click “I agree to this Participant Agreement”
- Read carefully http://write.flossmanuals.net/gsocstudentguide/what-is-google-summer-of-code/
- Read carefully https://wiki.osgeo.org/wiki/Google_Summer_of_Code_Recommendations_for_Students
References
-
"Boost Graph Library: Connected Components - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/connected_components.html
-
"Boost Graph Library: Strongly Connected Components - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/strong_components.html
-
"Boost Graph Library: Biconnected Components and Articulation Points - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/biconnected_components.html
-
"Boost Graph Library: Incremental Connected Components - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/incremental_components.html
-
"Tarjan's strongly connected components algorithm - Wikipedia", https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
-
"Disjoint sets - Wikipedia", https://en.wikipedia.org/wiki/Disjoint_sets
-
"Bridge (graph theory) - Wikipedia", https://en.wikipedia.org/wiki/Bridge_(graph_theory)
-
"Biconnected component - Wikipedia", https://en.wikipedia.org/wiki/Biconnected_component