Skip to content

GSoC 2016 Contraction

Jump to bottom Edit New page
Rohith Reddy edited this page Aug 15, 2016 · 37 revisions

Welcome to the pgrouting wiki for contraction!

##Brief Description

Graph Contraction, when talking about big graphs, like the road graphs, or electric networks, can be used to speed up, some graph algorithms.

The contraction level and contraction operations can become very complex, as the complexity of the graphs grows. In this implementation, we are making our contraction algorithm simple as possible so that more contraction operations can be added in the future.

In this project two contraction operations are implemented namely:

  • Dead end contraction
  • Linear contraction

##State of the project before GSoC Previously there is no contraction functionality in the library.

##Implementation I implemented the following during the GSoC program

  • A framework which supports the addition of new contraction algorithms.
  • Implementation of Dead end contraction.
  • Implementation of Linear contraction which will be used to refine the framework.
  • Additional characteristics where:
    • 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.
    • The user can decide the order of the operations on a cycle.
  • Proper documentation and tests for the above ­mentioned components.

##Links

My work is part of the 2.3.0 release of pgrouting. (programmed for september)

If you want to test my code, you can build the library for yourself following the guidelines here: http://docs.pgrouting.org/dev/en/doc/src/installation/build.html

#Table of Contents

##Biography

  • Name:​ Rohith Reddy
  • Country: ​India
  • School: International Institute Of Information Technology, Hyderabad
  • Degree: B.Tech in CSE and MS by Research in CSE
  • Email: ​rohithreddy2219@gmail.com

##Project

##Plans ###Period-2

###Period-1

###Community Bonding

###Before Community Bonding

##Status Reports

##Related Work

  • I studied the algorithms explained in the video and also implemented some of the algorithms explained in the video with the help of code samples in a repository

##References

##Detailed Plans

###August-9

  • Plan date: 09/08/2016
  • overall STATUS: COMPLETED
  • Completed Date: 14/08/2016
TODO status
Add description for dead end contraction with visual examples to the user documentation DONE
Add description for linear contraction with visual examples to the user documentation DONE
Getting familiar with graphviz to generate visual examples DONE
Add description about the contraction cycle to the user documentation DONE

###August-2

  • Plan date: 02/08/2016
  • overall STATUS: COMPLETED
  • Completed Date: 07/08/2016
TODO status
Remove unwanted code and unused files DONE
Updating the user documentation DONE
Updating the developer documentation DONE

###July-26

  • Plan date: 26/07/2016
  • overall STATUS: COMPLETED
  • Completed Date: 31/07/2016
TODO status
Signature change DONE
Change the number that represent dead end and linear contraction in the contraction order DONE
Modify the result files according to the latest signature DONE
Modify the pgTap tests according to the latest signature DONE
Fixed memory leak by freeing the memory of contracted vertices DONE
Linting the code according to the standard code guideline DONE

Message posted from the mentor on July 26

Message from Virginia Vergara:

Documentation can be updated after I make the alpha, but signature can not, so this is urgent:

  • put the underscore to _pgr_contractGraph
  • write the pgr_contractGaph (whith out the underscore) with the different order but all the columns
    • So the only pgtap tests that will fail are the ones that test the types of the results, all the documentation tests will fail and the generated documentation will change
tools/testers/algorithm-tester.pl -documentation -alg contraction
  • vi test.conf and put all tests in the nontested section and except "sampleData"
  • vi sampleData.result and delete everything
tools/testers/algorithm-tester.pl -alg contraction
  • copy/paste the results into sampleData.result and :s%/> // to remove the "> "
  • then you put another test in the tests section and do the same until you finish all tests

please before you work on the documentation stuff, make the changes of the signature & the changes of the tests & the documentation queries

###July-19

  • Plan date: 19/07/2016
  • overall STATUS: COMPLETED
  • Completed Date: 24/07/2016
TODO status
Added documentation for the proof of concept in the proposal DONE
Added a test sql file which contains the queries used by the documentation for proof of concept DONE
Debug appveyor error DONE
Perform contraction on very large vertex and edge ids to check types DONE
Update the user documentation DONE

###July-11

  • Plan date: 11/07/2016
  • overall STATUS: COMPLETED
  • Completed Date: 17/07/2016
TODO status
Update the pgTap tests using sample graph DONE
Updated the documentation of Identifiers class and eliminated doxygen errors DONE
Updated the documentation of contraction class and eliminated doxygen errors DONE
Updated the documentation of contraction graph class and eliminated doxygen errors DONE
Getting familiar with how query results can be used in documentation DONE
Wrote user documentation of contraction class DONE

###July-05

  • Plan date: 05/07/2016
  • overall STATUS: COMPLETED
  • Completed Date: 09/07/2016
TODO status
Update the pgTap tests due to change in the function signature DONE
Implement a function which expands the contracted graph DONE
Create a new edge and a vertex table which represent the contracted graph DONE
Update the C/C++ code to store contracted vertices in an array instead of a string DONE
Update the C/C++ code to add the cost column to the output of the contraction query DONE
Implement functions in contraction graph class that return the array of contracted vertices of a vertex or edge DONE
Getting familiar with pl/pgsql DONE
Add is_contracted column and contracted vertices column to the edge and vertex tables DONE
Add shortcuts to the edge table along with contracted_vertices and is_contracted flag DONE
Update the vertex table with contracted vertices of each vertex DONE

STEPS

####Returning contracted vertices as an array:

  • Read the discussion in the link.
  • Follow the discussion with the mentor in gitter on 06/07/2016.

####Updating pgTap tests:

  • Adjust pgtap tests of dead end contraction in directed graph to latest signature.
  • Adjust pgtap tests of dead end contraction in undirected graph to latest signature.
  • Adjust pgtap tests of linear contraction in directed graph to latest signature.
  • Adjust pgtap tests of linear contraction in undirected graph to latest signature.

###June-28

  • Plan date: 28/06/2016
  • overall STATUS: COMPLETED
  • Completed Date: 02/07/2016
TODO status
Documentation for Identifiers class DONE
Documentation for contraction graph class DONE
Analyse the contraction graph class and remove unwanted functions DONE
Write pgtap tests to test contraction cycle for directed graphs DONE
Write pgtap tests to test contraction cycle for undirected graphs DONE

STEPS

####Testing contraction cycle:

  • Run the contraction cycle twice on dead end contraction.
    • Assert that in the second cycle of dead end contraction there is no dead end vertex.
  • Run the contraction cycle twice on linear contraction.
    • Assert that in the second cycle of linear contraction there is no linear vertex.
  • Similarly run the contraction cycle for different combinations of dead end and linear contraction.

###June-21

  • Plan date: 21/06/2016
  • overall STATUS: COMPLETED
  • Completed Date: 25/06/2016
TODO status
Write pgtap tests for linear contraction for directed graph without forbidden vertices DONE
Write pgtap tests for linear contraction for directed graph with forbidden vertices DONE
Write pgtap tests for combination of dead end and linear contraction for directed graph without forbidden vertices DONE
Write pgtap tests for combination of dead end and linear contraction for directed graph with forbidden vertices DONE
Write pgtap tests for dead end contraction for undirected graph without forbidden vertices DONE
Write pgtap tests for dead end contraction for undirected graph with forbidden vertices DONE
Write pgtap tests for dead end contraction for directed graph without forbidden vertices DONE
Write pgtap tests for dead end contraction for directed graph with forbidden vertices DONE
Write pgtap tests for checking argument types for the function DONE
Meeting with mentor on 21/06/2016 DONE

###June-14

  • Plan date: 14/06/2016
  • overall STATUS: COMPLETED
  • Completed Date: 20/06/2016
TODO status
Read a paper on graph contraction DONE
Write demo sql file for linear contraction DONE
Clean up linear contraction class by removing unwanted functions DONE
Clean up contraction graph class by removing unwanted functions DONE
Give different ids to each of the added edge during linear contraction DONE
Modify the conditions for linear contraction DONE
Modify the conditions for dead end contraction DONE
Write demo sql file for dead end contraction DONE
Meeting with my mentor on 16/06/2016 DONE
Import sample OSM data into a database using osm2pgrouting tool DONE
Add source and target columns to the contraction output DONE
Write code to add the contracted vertices of the edge to the vertex during dead end contraction DONE
Write code to add the contracted vertices of the edge to the edge during linear contraction DONE
Write tests for combination of dead end and linear contraction on a square like graph DONE
Add only those edges and vertices that are changed to the contraction output DONE
Meeting with my mentor on 14/06/2016 DONE
Cleaning up unwanted files and directories DONE

###June-06

  • Plan date: 06/06/2016
  • overall STATUS: COMPLETED
  • Completed Date: 12/06/2016
TODO status
Check valid contraction condition in the c code DONE
Add a test for dead end contraction followed by linear contraction DONE
Make unit tests for the proper functioning of the linear contraction DONE
Add constructor to the ch_edge class DONE
Implement a class for linear contraction DONE
Added a structure for storing added edges in contraction graph DONE
Add functions to fetch added edges into the driver DONE
Update the result file of the test sql files so that all tests pass DONE
Add a unit test for dead end contraction with 4 nodes and 4 edges DONE
Implement a new function pgr_get_bigIntArray_allowEmpty() which can read an empty array DONE
Write unit tests for the above function DONE
Meeting with my mentor on 06/06/2016 DONE

###May-30

  • Plan date: 30/05/2016
  • overall STATUS: COMPLETED
  • Completed Date: 05/06/2016
TODO status
Return the values of the function as that of fake contraction DONE
Make unit tests for dead end contraction DONE
Add constructor to the identifiers class DONE
Convert forbidden_vertices array to a cpp container in the driver DONE
Implement a class for dead-end contraction DONE
Check max_cycles condition in the c code DONE
Implement a contraction graph class which inherits the base graph class DONE
Design Vertex Class DONE
Design Edge Class DONE
Implemented add_contracted_vertices() function in the Vertex class DONE
Make unit tests for the proper functioning of the Vertex class DONE
Add the edge class under the contraction namespace DONE
Implemented add_contracted_vertices() function in the Edge class DONE
Make unit tests for the proper functioning of the Edge class DONE

###May-24

  • Plan date: 24/05/2016
  • overall STATUS: COMPLETED
  • Completed Date: 30/05/2016
TODO status
Make use of the boost graph ids for the Identifiers class DONE
Make unit tests for the proper functioning of the Identifiers class DONE
Add default constructor to the vertex class DONE
Move Identifiers class into the common directory DONE
Change the name of the class Vertex_c to Vertex DONE
Remove the "m_deleted" from vertex class DONE
Remove the "contraction_type" from the vertex class DONE
Remove the "recover" function from the vertex class DONE
Use "Identifiers<int64_t> contracted_vertices" instead of "Removed_vertices removed_vertices" DONE
Write code in an sql file for the output of contraction in the convenience folder DONE
Make a new branch from the gsoc-ch branch DONE
Read about different ways of storage in postgresql DONE

###May-17

  • Plan date: 17/05/2016
  • overall STATUS: COMPLETED
  • Completed Date: 23/05/2016
TODO status
Experiment with the base graph and see how it works DONE
Read and understand the changes done to the base graph class DONE
Read and understand the new classes implemented namely xy_vertex, xy_edge DONE

STEPS

  • Experiment with the base graph:
    • Create a new branch named ch/newclasses.
    • Make new vertex and edge class.
    • Pass them as templates to the base graph class and see how it works.

###May-7

  • Plan date: 07/05/2016
  • overall STATUS: COMPLETED
  • Completed Date: 16/05/2016
TODO status
Lesson, how to propagate the changes in main repo to you fork's branch DONE
Learn how to use "git stash" command DONE
GITTER Discussion on Base Graph DONE
Working on Issue #555 TRANSFERRED BY REQUEST TO OTHER DEVELOPER (@cvvergara)

###April-24

  • Plan date: 24/04/2016
  • overall STATUS: COMPLETED
  • Completed Date: 06/05/2016
TODO status
Read the documentation of Base graph class DONE
Setting up the development environment DONE
Add links to the codes described in the videos DONE

###March-29

  • Plan date: 29/03/2016
  • overall STATUS: COMPLETED
  • Completed Date: 23/04/2016
TODO status
C++ Add a function that returns the set of adjacent vertices DONE
C++ Add a function to the contraction graph class which tells us the connectivity of a vertex DONE
C++ Change sql vertices to an array of forbidden vertices DONE
C++ Perform unit tests on dead end vertices DONE
C++ Change the vertex class and the edge class DONE
C++ Change std::map<int64_t, Edge> removed_edges_c to std::deque removed_edges_c DONE
C++ Add is_dead_end() function to the pgr_contract class DONE
C++ Add getDeadEndSet() function to the pgr_contract class DONE
C++ Add disconnectVertex(V v) function to the pgr_contract class DONE
C++ Add documentation to the Identifier class DONE
C++ Identifiers class +, -, *, == DONE
C++ Make the Contraction_types class DONE
C++ Change names of file with upper case to a name without uppercase DONE
C++ Change class and variables names according to google cpp style DONE
C++ Remove cpp lint errors on the Identifiers class DONE

STEPS

Pgr_contract::disconnectVertex(V v) { pgassert(is_connected(v)); pgassert(is_dead_end(v));

pgr_connectionGraph.disconnect_vertex ( v );

pgassert(!is_connected(v)); }

Pgr_contract::getDeadEndSet(mygraph g) { cycle the Vertices, and use is_dead_end(v); when true it add is to the Identifiers Set and return the set; }

bool is_dead_end(v) { return dead_end_vertices.has(v) }

Vertex_c { id,removed_vertices = {} }

Edge_c { id,removed_vertices = {} }

###March-3

  • Plan Date: 03/03/2016
  • overall STATUS: COMPLETED
  • Completed Date: 29/03/2016
TODO status
C++ Addition of "removed" flag to the Vertex_c class to assess its logical removal DONE
C++ Check that contraction_order elements are valid DONE
C++ Check that max_cycles is atleast one DONE
C++ Comment about the public functions used DONE
C++ Surround the functions used for linear contraction with #if 0 #endif DONE
C++ Implement "<<" operator for the base graph DONE

###STEPS contract(v1,v2): v2 is being contracted to v1

  • Preconditions of contraction:

    • assert( v1.isNotLogicallyDeleted());
    • assert( v2.isNotLogicallyDeleted());

  • Postconditions of contraction:

    • assert(v1.isLogicallyDeleted());
    • assert(v2.isNotLogicallyDeleted());
    • assert(v2.hasInRemovedVertices(v1));
    • debugVertex = v1.removedVertices;
    • assert(v2.hasAllRemovedVerticesof(debugVertex));

###Feb-9

  • overall STATUS:__________
  • Completed Date:
TODO status
Test contraction on sample data(graph #1,graph #2,graph #3,graph #4),starting from different points and verify the results DEFERRED
Make the call on directed graph DEFERRED
Make both calls at the same time DEFERRED
Check the style: pgr_contract.hpp DEFERRED
Wrapping the functions into pgr_contract class DONE
Add a new class which serves as a baseGraph for contraction DONE

###STEPS

  • Add a new class which serves as a baseGraph for contraction:

    • make a fresh copy of baseGraph into pgr_contractionGraph.hpp.
    • make a diff of the "baseGraph.hpp" you were using before tying to glue with pgr_contractionGraph.hpp
    • If you modified a function, then add the function with a different name in pgr_contractionGraph.hpp
    • and use the function with the modified name

  • Testing contraction on sample data

    • start with small graphs(from a graph size of one edge).
    • do it by hand and verify it with the output of the algorithm.
    • Do the same with the four graphs(graph #1,graph #2,graph #3,graph #4) of the sample data and verify the same

###Feb-4

  • Plan Date: 04/02/2016
  • overall STATUS: COMPLETED
  • Completed Date: 09/02/2016
TODO status
Make the call on directed graph DEFERRED
Make both calls at the same time DEFERRED
Cleanup includes DONE
Return ostream's DONE
Make the call on undirected graph DONE
Check the style: contractGraph.c DONE
Check the style: contractGraph_driver.h DONE
Check the style: contractGraph_driver.cpp DONE
https://github.com/pgRouting/pgrouting/pull/483/files DONE

###STEPS

  • Cleanup includes
    • delete unused includes in contractGraph_driver.cpp
    • add used includes in contractGraph_driver.cpp
  • Return ostream's
    • var << value
    • Do this whatever the function we are calling.
  • Check style
tools/cpplint.py src/contraction/src/contractGraph.c
  • Clean style do necessary steps to delete this kind of errors:
    • Line ends in whitespace.
    • Should have a space between // and comment
    • Lines should be <= 80 characters long
    • Missing space before (
  • the errors about include order, please ignore
  • th Using C-style cast error on C file ignore, but please fix on C++

###Feb-2

  • Plan Date: 02/02/2016
  • overall STATUS: COMPLETED
  • Completed Date: 03/02/2016
TODO status
revcost to reverse_cost DONE
remove has_rcost and add directed flag to the query DONE
Return setof record instead of returning pgr_contracted_blob DONE
Convert integer to int64_t in the C/C++ structures DONE
Convert integer to int64_t where applicable DONE
Typecheck for innersql of contraction query DONE
Return ostringstream to the contraction driver DONE
git commit -a -m 'saving before generating template' DONE
edit create.sh DONE
generate files DONE
git stash <--- that will revert the edition on funnyDijkstra DONE
generate files DONE
putting the correct names and putting them in the contraction directory DONE
add funnyDijkstra to the repo while we work DONE
but after all movements are finish you delete it from the repo DONE

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally