Closed thisisashukla closed 7 years ago
the following images are graph representation for the proposed contraction hierarchies
Graphs for sample data
1
2
3
Graphs for sample data 2
4
5
Shortest path between two nodes on complete graph
6
Shortest path between two nodes on contracted graph
7
The same resultant route on the contracted graph is a visual proof of equivalence of hierarchical contraction
Image Number 2
13 -> many
take the path from 13 -> 4 as 13-10-5-6-9-4 for visual appeal
So, image 3, the yellow lines disappear and the 10-> 5, 5->6, 6->9 edges become red
the following images are graph representation for the proposed contraction hierarchies
Graphs for sample data
1![img_20170323_241008203](https://cloud.githubusercontent.com/assets/20864366/24215115/b78507ca-0f5d-11e7-8588-d01877066d1e.jpg)
2![img_20170323_241014461](https://cloud.githubusercontent.com/assets/20864366/24215116/b9787fe4-0f5d-11e7-9f7a-449b7ba716f7.jpg)
3![img_20170323_241018728](https://cloud.githubusercontent.com/assets/20864366/24215118/bbfbe6c0-0f5d-11e7-9e03-430a7628804f.jpg)
Graphs for sample data 2
4![img_20170323_241025683](https://cloud.githubusercontent.com/assets/20864366/24215132/d1a63aac-0f5d-11e7-95c5-5b50b78b7135.jpg)
5![img_20170323_003403](https://cloud.githubusercontent.com/assets/20864366/24216015/ae8a91aa-0f60-11e7-9eaa-fe36f7a0b27d.jpg)
Shortest path between two nodes on complete graph
6![img_20170323_241033386](https://cloud.githubusercontent.com/assets/20864366/24215137/d5176d78-0f5d-11e7-9465-ef08b8aeea90.jpg)
Shortest path between two nodes on contracted graph
7![img_20170323_241037920](https://cloud.githubusercontent.com/assets/20864366/24215164/e3c51f8c-0f5d-11e7-8c81-62e47af72bf3.jpg)
The same resultant route on the contracted graph is a visual proof of equivalence of hierarchical contraction