Skip to content

GSoC 2016 Contraction

Jump to bottom Edit New page
Vicky Vergara edited this page May 4, 2017 · 37 revisions

Tag: https://github.com/pgRouting/pgrouting/releases/tag/gsoc%2Fcontraction-lw

Report List

Welcome to the pgrouting wiki for contraction!

Brief Description

In big graphs, like the road graphs, or electric networks, graph contraction can be used to speed up some graph algorithms. Contraction reduces the size of the graph by removing some of the vertices and edges and, for example, might add edges that represent a sequence of original edges decreasing the total time and space used in graph algorithms.

This implementation gives a flexible framework for adding contraction algorithms in the future, currently, it supports two algorithms:

  • Dead end contraction
  • Linear contraction

Allowing the user to:

  • Forbid contraction on a set of nodes.
  • Decide the order of the contraction algorithms and set the maximum number of times they are to be executed.

State of the project before GSoC

Previously there is no contraction functionality in the library.

Addition that my project brought to the software

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

Slides

https://docs.google.com/presentation/d/1CJ6edrKdvKh-daV7fZdxgOkeJUO-_p1N20-rEIq6uU4/pub?start=false&loop=true&delayms=3000&slide=id.g163d2119d3_0_85

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

Please test my code on the pgrouting 2.3.0 release by 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

Report 13

Report 12

##My initial plan

  • Update the user and developer documentation of contraction class.

##What did I do this week?

  • Discussion with the mentor regarding user documentation of contraction function on 10/07/2016.
  • Getting familiar with graphviz to generate visual examples.
  • Add description for dead end contraction, linear contraction and contraction cycle along with visual examples to the user documentation.

##What will I be working on next week?

  • Preparing the final report.

##Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 11

##My initial plan

  • Update the user and developer documentation of contraction class.

##What did I do this week?

  • Discussion with the mentor regarding user documentation of contraction function on 04/07/2016.
  • Discussion with the mentor regarding developer documentation of contraction function on 05/07/2016.
  • Removed unwanted code and unused files.
  • Worked on pgRouting workshop.
  • Updated the user documentation.
  • Updated the developer documentation.

##What will I be working on next week?

  • Update the developers and users documentation.

##Did I meet with any stumbling blocks?

  • At the moment I’m not blocked.

Report 10

##My initial plan

  • Update the user and developer documentation of contraction class.

##What did I do this week?

  • Discussion with the mentor regarding change in the output of contraction function on 27/07/2016.
  • Discussion with the mentor regarding signature change of contraction function on 29/07/2016.
  • Changed the output of contraction function.
  • Signature change of contraction function.
  • Modify the result files according to the latest signature.
  • Modify the pgTap tests according to the latest signature.
  • Fixed memory leak.
  • Linting the code according to the standard code guideline.

##What will I be working on next week?

  • Write the developers and users documentation.

##Did I meet with any stumbling blocks?

  • I faced a difficulty in identifying the memory leak. My mentor Vicky Vergara helped me solve it.
  • At the moment I’m not blocked.

Report 9

##My initial plan

  • Update the user and developer documentation of contraction class.

##What did I do this week?

  • Discussion with the mentor regarding bugs in appveyor build on 20/07/2016.
  • Solved bugs due to data types.
  • Updated the user documentation of contraction.
  • Updated code files to ensure a successful build in
    • Travis
    • Appveyor
    • Jenkins
    • Ubuntu(precise and trusty)

##What will I be working on next week?

  • Write the developers and users documentation.

##Did I meet with any stumbling blocks?

  • I faced a difficulty in identifying the bug due to data types which caused the appveor build to crash. My mentor Vicky Vergara helped me solve it.
  • At the moment I’m not blocked.

Report 8

#My initial plan

  • Write the user documentation of contraction class.

##What did I do this week?

  • Discussion with the mentor regarding documentation on 13/07/2016.
  • Update the pgTap tests using sample graph
  • Getting familiar with how query results can be used in documentation.
  • Updated the documentation and eliminated doxygen errors of the following classes
    • Identifiers class
    • Contraction class
    • Contraction Graph class
  • Wrote user documentation of contraction class.

##What will I be working on next week?

  • Write the developers and users documentation.

##Did I meet with any stumbling blocks?

  • No.
  • At the moment I’m not blocked.

Report 7

##My initial plan

  • Design and implement a function to expand the contracted graph, for testing purpose.

##What did I do this week?

  • Discussion with the mentor about graph expansion on 05/07/2016.
  • Discussion with the mentor about updating the pgTap test on 08/07/2016.
  • Getting familiar with pl/pgsql.
  • Signature change of the contraction function.
    • Storing contracted vertices in an array instead of a string.
    • Addition of cost column to the output of the contraction query.
  • Wrote a pl/pgsql script which expands the contracted graph.
  • Update the pgTap tests due to change in the function signature.

##What will I be working on next week?

  • Write the user documentation of the classes implemented so far.

##Did I meet with any stumbling blocks?

  • I faced an issue in comparing arrays while adjusting the pgTap tests to the latest signature. My mentor Vicky Vergara helped me resolve the issue.
  • At the moment I’m not blocked.

Report 6

##My initial plan

  • Testing the contraction cycle.
  • Documenting the classes implemented so far.

##What did I do this week?

  • Discussion with the mentor about the contraction cycle on 28/06/2016.
  • Wrote unit tests for contraction cycle for directed and undirected graphs.
  • Analyse the contraction graph class and remove unwanted functions.
  • Documented the contraction graph class.
  • Documented the Identifiers class.

##What will I be working on next week?

  • Design and implement a function to expand the contracted graph.

##Did I meet with any stumbling blocks?

  • No
  • At the moment I’m not blocked.

Report 5

My initial plan

  • Implement and test dead end contraction for undirected graphs.
  • Implement and test linear contraction for undirected graphs.

What did I do this week?

  • Discussion with the mentor about the dead end and linear contraction for undirected graphs on 21/06/2016.
  • Designed conditions for dead end contraction in undirected graphs.
  • Designed conditions for linear contraction in undirected graphs.
  • Implemented dead end contraction for undirected graphs.
  • Implemented linear contraction for undirected graphs.
  • Generated sample graph data for testing dead end and linear contraction.
  • Wrote unit tests for dead end contraction for directed and undirected graphs.
  • Wrote unit tests for linear contraction for directed and undirected graphs.

What will I be working on next week?

  • Further analysis on dead end and linear contraction.
  • Design the structures and functions based on analysis for the framework.

Did I meet with any stumbling blocks?

  • I had a problem in figuring out a bug while implementing linear contraction for undirected graph. My mentor Vicky Vergara helped me solve it.
  • I also had an issue in writing pgtap tests. My mentor guided me on how to write pgtap tests.
  • At the moment I’m not blocked.

Report 4

##My initial plan

  • Analysis of dead end contraction.
  • Analysis of linear contraction.

##What did I do this week?

  • Discussion with the mentor about the dead end and linear contraction on 16/06/2016 and 14/06/2016.
  • Added more functionality to the identifiers class
    • Implemented index operator.
  • Added more functionality to the contraction graph class.
  • Implemented function which returns out degree to a vertex.
  • Implemented function which returns in degree from a vertex.
  • Identified that the dead end and linear contraction conditions are different for directed and undirected graphs with the help of hand drawings.
  • Modification and addition of conditions for dead end contraction.
  • Modification and addition of conditions for linear contraction.
  • Wrote demo sql file to display the contraction results of dead end contraction.
  • Wrote demo sql file to display the contraction results of linear contraction.
  • Modified the output of contraction query by only returning the changes due to contraction.
  • Completed reading a paper on graph contraction given by mentor Vicky Vergara.

##What will I be working on next week?

  • Adding extra conditions of dead end and linear contraction for an undirected graph.
  • Writing tests for dead end and linear contraction for an undirected graph.
  • Design the structures and functions for the framework.

##Did I meet with any stumbling blocks?

  • I had a problem in figuring out some conditions for dead end and linear contraction. After discussion with my mentor, my issue was resolved.
  • At the moment I’m not blocked.

Report 3

##My initial plan

  • Analysis of dead end contraction.
  • Implementing Linear contraction to analyse and design structures required for the framework.

##What did I do this week?

  • Discussion with the mentor about the implementation of the contraction framework.
  • Implement a new function pgr_get_bigIntArray_allowEmpty() which can read an empty array.
  • Added more functionality to the Edge class
    • Implemented constructors.
  • Added more functionality to the contraction graph class.
  • Implemented function which returns added edges during contraction.
  • Updated the function that inserts data into the graph.
  • Implemented a class for linear contraction to understand and design the contraction framework.
  • Wrote unit tests for linear contraction.
  • Wrote unit tests for proper functioning of the cycle of contraction operations.

##What will I be working on next week?

  • Analyse the linear contraction class to implement the contraction framework.
  • Design and implement the structures and functions for the framework.

##Did I meet with any stumbling blocks?

  • No
  • At the moment I’m not blocked.

Report 2

##My initial plan

  • Design a generic template model for contraction, which supports the addition of new contraction techniques.

##What did I do this week?

  • Discussion with the mentor about the implementation of the contraction framework.
  • Implemented a contraction graph class which inherits the base graph class.
  • Added functions and attributes to this class which are used in contraction.
  • This class represents the contracted graph.
  • Formulated the inputs and outputs of the contraction query.
  • Implemented functions which validate the inputs and notify the user about the invalid inputs.
  • Added more functionality to the Identifiers class
    • Implemented iterators.
    • Implemented size() function.
  • Implemented a class for dead end contraction to understand and design the contraction framework.
  • Wrote unit tests for dead end contraction.

##What will I be working on next week?

  • Analyse the dead end contraction class to implement the contraction framework.
  • Design and implement the structures and functions for the framework.

##Did I meet with any stumbling blocks?

  • I had a problem in identifying the code that lead to server crash. After discussion with my mentor Vicky Vergara, I learned to identify the code responsible for server crash.
  • I had a problem in testing the functionality of dead end contraction which was solved my making unit tests as suggested by my mentor Vicky Vergara.
  • At the moment I’m not blocked.

Report 1

##My initial plan

  • Analyse and design the structures used for contraction
  • Design of the query result for contraction

##What did I do this week?

  • Setup a personal wiki or blog for weekly updates, TODO lists and project discussions.
  • Read about different storage types in postgresql.
  • Read and understood the changes done to the base graph class.
  • Identified a bug in the base graph class implementation.
  • Designed the vertex structure for contraction.
  • Designed the edge structure for contraction.
  • Designed a structure for performing set operations(Identifers class) which is used for contraction.
  • Wrote unit tests for the Identifiers class .
  • Implemented a pl/pgsql function to return results of contraction query.

##What will I be working on next week?

  • Design a generic template model for contraction, which supports the addition of new contraction techniques.

##Did I meet with any stumbling blocks?

  • I had a problem in writing functions for the vertex class which had to be passed to the base graph as a template. My mentor Vicky Vergara helped me to solve it.
  • At the moment I’m not blocked.

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally