GSoC 2016 Contraction
Tag: https://github.com/pgRouting/pgrouting/releases/tag/gsoc%2Fcontraction-lw
- Report 13
- Report 12
- Report 11
- Report 10
- Report 9
- Report 8
- Report 7
- Report 6
- Report 5
- Report 4
- Report 3
- Report 2
- Report 1
Welcome to the pgrouting wiki for contraction!
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.
Previously there is no contraction functionality in the library.
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.
-
Link to the branch working branch and directory:
https://github.com/pgRouting/pgrouting/tree/gsoc-ch/src/contraction
-
Links to the documentation
http://docs.pgrouting.org/dev/en/src/contraction/doc/contraction.html http://docs.pgrouting.org/dev/en/src/contraction/doc/pgr_contractGraph.html
-
Link that shows all of my commits
https://github.com/pgRouting/pgrouting/commits/gsoc-ch?author=sankepallyrohithreddy
-
Link that shows all of my pull requests to the main repository
https://github.com/pgRouting/pgrouting/pulls?q=is%3Apr+author%3Asankepallyrohithreddy+is%3Aclosed4
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
- Name: Rohith Reddy
- Country: India
- School: International Institute Of Information Technology, Hyderabad
- Degree: B.Tech in CSE and MS by Research in CSE
- Email: [email protected]
- Weekly Report-12
- Weekly Report-11
- Weekly Report-10
- Weekly Report-9
- Weekly Report-8
- Weekly Report-7
- Weekly Report-6
- Weekly Report-5
- Weekly Report-4
- Weekly Report-3
- Weekly Report-2
- Weekly Report-1
- 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
- CppCon 2015: Michael VanLoon “STL Algorithms in Action” https://www.youtube.com/watch?v=eidEEmGLQcU
- Bjarne Stroustrup - The Essence of C++ https://www.youtube.com/watch?v=86xWVb4XIyE
- Bjarne Stroustrup - C++11 Style https://www.youtube.com/watch?v=0iWb_qi2-uI
- Google C++ Styleguide - https://google.github.io/styleguide/cppguide.html
- 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 |
- 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 |
- 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 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
- 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 |
- 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 |
- 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 |
- Read the discussion in the link.
- Follow the discussion with the mentor in gitter on 06/07/2016.
- 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.
- 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 |
- 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.
- 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 |
- 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 |
- 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 |
- 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 |
- 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 |
- 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 |
- 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.
- 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) |
- 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 |
- 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 |
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 = {} }
- 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 |
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));
- 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 |
-
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
- 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 |
- 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++
- 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 |
##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.
##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.
##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.
##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.
#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.
##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.
##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.
- Implement and test dead end contraction for undirected graphs.
- Implement and test linear contraction for undirected graphs.
- 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.
- Further analysis on dead end and linear contraction.
- Design the structures and functions based on analysis for the framework.
- 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.
##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.
##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.
##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.
##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.
