Skip to content

GSoC 2017 Connected Components

Jump to bottom Edit New page
Maoguang Wang edited this page Aug 20, 2017 · 45 revisions

Table of Contents

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

Project proposal

Slides

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 to 2.3.3
  • merged upstream/develop
  • changed PG_VERSION to 2.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 and proposed.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 extended Pgr_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 of node and edge
  • 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 and stable_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 by algorithm-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

Get familiar with C++

Watch videos about C++:

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.

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.

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 and reverse_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 &)

using auto

more

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

References

  1. "Boost Graph Library: Connected Components - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/connected_components.html

  2. "Boost Graph Library: Strongly Connected Components - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/strong_components.html

  3. "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

  4. "Boost Graph Library: Incremental Connected Components - 1.46.0", http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/incremental_components.html

  5. "Tarjan's strongly connected components algorithm - Wikipedia", https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

  6. "Disjoint sets - Wikipedia", https://en.wikipedia.org/wiki/Disjoint_sets

  7. "Bridge (graph theory) - Wikipedia", https://en.wikipedia.org/wiki/Bridge_(graph_theory)

  8. "Biconnected component - Wikipedia", https://en.wikipedia.org/wiki/Biconnected_component

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally