{"action":"created","issue":{"url":"https://api.github.com/repos/pgRouting/pgrouting/issues/440","labels_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/440/labels{/name}","comments_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/440/comments","events_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/440/events","html_url":"https://github.com/pgRouting/pgrouting/issues/440","id":124651745,"number":440,"title":"Integration of Contraction Heirarchy code into pgrouting","user":{"login":"woodbri","id":805250,"avatar_url":"https://avatars.githubusercontent.com/u/805250?v=3","gravatar_id":"","url":"https://api.github.com/users/woodbri","html_url":"https://github.com/woodbri","followers_url":"https://api.github.com/users/woodbri/followers","following_url":"https://api.github.com/users/woodbri/following{/other_user}","gists_url":"https://api.github.com/users/woodbri/gists{/gist_id}","starred_url":"https://api.github.com/users/woodbri/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/woodbri/subscriptions","organizations_url":"https://api.github.com/users/woodbri/orgs","repos_url":"https://api.github.com/users/woodbri/repos","events_url":"https://api.github.com/users/woodbri/events{/privacy}","received_events_url":"https://api.github.com/users/woodbri/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/pgRouting/pgrouting/labels/Discussion","name":"Discussion","color":"000000"},{"url":"https://api.github.com/repos/pgRouting/pgrouting/labels/Feature%20Request","name":"Feature Request","color":"fbca04"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/pgRouting/pgrouting/milestones/9","html_url":"https://github.com/pgRouting/pgrouting/milestones/Release%202.3.0","labels_url":"https://api.github.com/repos/pgRouting/pgrouting/milestones/9/labels","id":1442264,"number":9,"title":"Release 2.3.0","description":"","creator":{"login":"cvvergara","id":5035290,"avatar_url":"https://avatars.githubusercontent.com/u/5035290?v=3","gravatar_id":"","url":"https://api.github.com/users/cvvergara","html_url":"https://github.com/cvvergara","followers_url":"https://api.github.com/users/cvvergara/followers","following_url":"https://api.github.com/users/cvvergara/following{/other_user}","gists_url":"https://api.github.com/users/cvvergara/gists{/gist_id}","starred_url":"https://api.github.com/users/cvvergara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cvvergara/subscriptions","organizations_url":"https://api.github.com/users/cvvergara/orgs","repos_url":"https://api.github.com/users/cvvergara/repos","events_url":"https://api.github.com/users/cvvergara/events{/privacy}","received_events_url":"https://api.github.com/users/cvvergara/received_events","type":"User","site_admin":false},"open_issues":13,"closed_issues":0,"state":"open","created_at":"2015-12-03T14:57:36Z","updated_at":"2016-01-08T02:50:13Z","due_on":"2016-09-01T05:00:00Z","closed_at":null},"comments":15,"created_at":"2016-01-03T14:49:16Z","updated_at":"2016-01-13T06:40:12Z","closed_at":null,"body":"On 1/3/2016 8:19 AM, rohith reddy wrote:\r\n> Hey Steve,\r\n>      As you know, me and Mukul are working on contraction hierarchies \r\n> for routing.I have been reading papers on contraction hierarchies for \r\n> road networks.\r\n> In most of them,the method of contraction is as follows,\r\n> \r\n> 1.Node ordering for contraction(based on some criterion).\r\n> 2.Contracting the node with the highest priority(more likely to be \r\n> contracted).\r\n> 3.Introducing(upon decision) shortcuts between the nodes adjacent to \r\n> this node.\r\n> \r\n> Some of the node ordering techniques I found are,\r\n> 1. Edge difference\r\n> 2.Uniformity\r\n> 3.Deleted Neighbors\r\n> 4.Voronoi Regions\r\n> \r\n>      During the last month we have worked on a contraction model,where \r\n> the nodes are ordered according to their degrees,and then contracted.We \r\n> have defined levels of contraction as follows:\r\n> Level 0: Removal of all one degree nodes.\r\n> Level 1:Removal of all two degree nodes.\r\n>      I implemented a cpp class which contracts the graph,given the level \r\n> of contraction.I also implemented cpp classes for dijkstra and \r\n> astar,which extend the above class,and run the algorithm on the \r\n> contracted graph.These classes can be integrated with pgrouting.The \r\n> process is as follows:\r\n> \r\n> 1.Contract the graph to the given level.\r\n> 2.Run dijkstra/astar on the contracted graph.\r\n> 3.Unpack the path,and derive the original path.\r\n> \r\n> I have tested it for some test cases and it works fine.We actualIy \r\n> are not sure of the exact contraction model,but inorder to test we have \r\n> taken up the above contraction model.I am also planning to implement a \r\n> query for the same in postgresql.Can you help me, how to proceed?\r\n> \r\n> Regards,\r\n> Rohith Reddy.\r\n\r\nHi Rohith,\r\n\r\nThis sounds like excellent work the you guys have been doing. Regarding integrating this into postgresql and want to bring Vicky into the discussion because she has reworked the C code that is need to some easy to use templates and she has done a lot of work in build reusable C++ classes for Dijkstra based on Boost Graph.\r\n\r\nThe integration into postgresql follows these steps:\r\n\r\n1. define a plpgsql function(s) that is callable from SQL. This is a little be more difficult on the case of contraction hierarchies because we need to a) contract the graph and store it, b) recall the contracted graph and run query(s) against it. So we have to consider how and where to store the contracted graph.\r\n2. given a plpgsql signature, we need to write a C function that processes the arguments of the function into a C structs and calls a C++ wrapper to your code.\r\n3. we need a C++ wrapper, that handles taking the C structs passed to it, create an instance of you solver or contractor, and loads the data into the solver or contractor from the C structs, runs the solver or contractor, and finally returns the results back to the C code which in turn returns it back to the SQL code.\r\n\r\nSo you might have some hypothetical commands like:\r\n```\r\ninsert into contracted_graphs\r\n  select 'my_contracted_graph_name'::text, contracted_blob::bytea\r\n    from pgr_contractgraph(\r\n        sql_for_edges::text,\r\n        sql_for_turn_restriction::text, -- if you support them\r\n        contraction_level::integer default 0, -- or whatever\r\n        ... -- other options or data you might need\r\n    );\r\n```\r\nwhere sql_for_edges might look like:\r\n```\r\n'select edge_id, nodeid_a, nodeid_b, weight_forward, weight_reversed, ...\r\n  from edge_table'\r\n```\r\nWe might store contracted blobs in a table like:\r\n```\r\ncreate table contracted_graphs (\r\n    name text,\r\n    blob bytea\r\n);\r\n```\r\nIssues to be sorted out:\r\n1. what is the best way to store large blobs of data?\r\n2. should we look at the contracted graph as a blob or is it better viewed as structured data for the purpose of storing it in the database.\r\n3. would it be faster to store the data in file(s) on disk and only remember the filenames in the database?\r\n4. if in files can multiple simultaneous queries access the files without issues?\r\n\r\nRemember, multiple user database means NO globals. postgresql is a long running server process so NO memory leaks. etc.\r\n\r\nThe use here is performance of serializing the contracted graph and store it in the database and then later retrieving it and unserializing it. Postgresql has some performance issues around fetching and storing large blob objects that we would need to look at. Also I have not ever done this in the past so some investigation will need to be done.\r\n\r\nFor the actual route query, you should model the SQL functions and code to act like the new code Vicky has done for pgr_dijkstra() and I will let her add links to that below. But this case, rather than passing the edges in you would pass in the contracted graph, and the route query parameters and you would want to return results structured as that code does. Please look at her new code NOT the 2.0 code."},"comment":{"url":"https://api.github.com/repos/pgRouting/pgrouting/issues/comments/171188302","html_url":"https://github.com/pgRouting/pgrouting/issues/440#issuecomment-171188302","issue_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/440","id":171188302,"user":{"login":"cvvergara","id":5035290,"avatar_url":"https://avatars.githubusercontent.com/u/5035290?v=3","gravatar_id":"","url":"https://api.github.com/users/cvvergara","html_url":"https://github.com/cvvergara","followers_url":"https://api.github.com/users/cvvergara/followers","following_url":"https://api.github.com/users/cvvergara/following{/other_user}","gists_url":"https://api.github.com/users/cvvergara/gists{/gist_id}","starred_url":"https://api.github.com/users/cvvergara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cvvergara/subscriptions","organizations_url":"https://api.github.com/users/cvvergara/orgs","repos_url":"https://api.github.com/users/cvvergara/repos","events_url":"https://api.github.com/users/cvvergara/events{/privacy}","received_events_url":"https://api.github.com/users/cvvergara/received_events","type":"User","site_admin":false},"created_at":"2016-01-13T06:40:12Z","updated_at":"2016-01-13T06:40:12Z","body":"@sankepallyrohithreddy \r\nHello,\r\nYou might want to look at any of the following files...  (.c & .h)\r\nedges_input\r\npoints_input\r\nrestrictions input\r\n\r\nbecause as I told you... the c part of the code of whatever you do will be rewritten when I integrate it into pgRouting.\r\nI would prefer that you focus on:\r\n  - a version that is executing, even as a stand by program non glued to the database.\r\n  - And write the documentation. \r\n\r\nAs a reminder I wrote in a previous comment:\r\n## create the documentation\r\n  I would think  that you have a clone of pgRouting somewhere so copy the documentation of a function that the signature \"looks like\" the signature you are using:\r\n```\r\n    mkdir doc\r\n    cp /path/to/src/func_name/doc/file.rst  doc/contraction.rst\r\n    git add doc/contraction.rst\r\n```\r\n\r\nmodify the file such that:\r\n- it describes your intended input & outputs of all the involved queries so that when I glue it to the database I can follow that description to create the appropriate code for the integration to pgrouting.\r\n\r\n\r\n\r\n\r\n\r\n\r\n"}}