<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hey Pengzhan :),<br>
<br>
there are papers about contraction hierarchies but also some video
which I can recommend (see <a
href="http://en.wikipedia.org/wiki/Contraction_hierarchies">wikipedia</a>
for this).<br>
<br>
In GraphHopper you need to read/understand the classes
PrepareContractionHierarchies and Path4CH. Roughly speaking: you
create shortcuts (additionally edges which avoid most of the
nodes) recursivly. And on query time you run a bidirectional
Dijkstra where you afterwards have to 'unfold'/'extract' those
shortcuts into edges which is done in Path4CH.<br>
<br>
Regards,<br>
Peter.<br>
<br>
<br>
<br>
</div>
<blockquote cite="mid:006f01cf60fa$d19f4400$74ddcc00$@163.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:宋体;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"\@宋体";
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:微软雅黑;
panose-1:2 11 5 3 2 2 4 2 2 4;}
@font-face
{font-family:"\@微软雅黑";
panose-1:2 11 5 3 2 2 4 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
text-align:justify;
text-justify:inter-ideograph;
font-size:10.5pt;
font-family:"Calibri","sans-serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML 预设格式 Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin:0cm;
margin-bottom:.0001pt;
text-align:justify;
text-justify:inter-ideograph;
text-indent:21.0pt;
font-size:10.5pt;
font-family:"Calibri","sans-serif";
color:black;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.HTMLChar
{mso-style-name:"HTML 预设格式 Char";
mso-style-priority:99;
mso-style-link:"HTML 预设格式";
font-family:"Courier New";
color:black;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:512644593;
mso-list-type:hybrid;
mso-list-template-ids:675703310 -1253952392 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:\F06E;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:18.0pt;
text-indent:-18.0pt;
font-family:Wingdings;
mso-fareast-font-family:宋体;
mso-bidi-font-family:"Times New Roman";}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:\F06E;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:42.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F075;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:63.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F06C;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:84.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:\F06E;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:105.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F075;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:126.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F06C;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:147.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:\F06E;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:168.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F075;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:189.0pt;
text-indent:-21.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span style="color:#1F497D" lang="EN-US">Peter:<o:p></o:p></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span
style="color:#1F497D" lang="EN-US">If so, What basic
speed-up method are you using for GH ?<o:p></o:p></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span
style="color:#1F497D" lang="EN-US">Please show me both algo
and implement speed-up methods.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D" lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span
style="color:#1F497D" lang="EN-US">#P.s I can’t believe our
gov block github again… and pls just call me Pengzhan <o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D" lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D" lang="EN-US">Best
regards<o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1
1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="text-align:left" align="left"><b><span
style="font-size:11.0pt;font-family:"微软雅黑",&
quot;sans-serif";color:windowtext">发件人<span
lang="EN-US">:</span></span></b><span
style="font-size:11.0pt;font-family:"微软雅黑","sans-serif&
quot;;color:windowtext" lang="EN-US">
<a class="moz-txt-link-abbreviated" href="mailto:graphhopper-bounces@openstreetmap.org">graphhopper-bounces@openstreetmap.org</a>
[<a class="moz-txt-link-freetext" href="mailto:graphhopper-bounces@openstreetmap.org">mailto:graphhopper-bounces@openstreetmap.org</a>] </span><b><span
style="font-size:11.0pt;font-family:"微软雅黑",&
quot;sans-serif";color:windowtext">代表 </span></b><span
style="font-size:11.0pt;font-family:"微软雅黑",&
quot;sans-serif";color:windowtext" lang="EN-US">Peter
K<br>
</span><b><span
style="font-size:11.0pt;font-family:"微软雅黑","sans-serif&
quot;;color:windowtext">发送时间<span lang="EN-US">:</span></span></b><span
style="font-size:11.0pt;font-family:"微软雅黑",&
quot;sans-serif";color:windowtext" lang="EN-US">
2014</span><span
style="font-size:11.0pt;font-family:"微软雅黑","sans-serif&
quot;;color:windowtext">年<span lang="EN-US">4</span>月<span
lang="EN-US">25</span>日<span lang="EN-US"> 19:19<br>
</span><b>收件人<span lang="EN-US">:</span></b><span
lang="EN-US"> <a class="moz-txt-link-abbreviated" href="mailto:graphhopper@openstreetmap.org">graphhopper@openstreetmap.org</a><br>
</span><b>主题<span lang="EN-US">:</span></b><span
lang="EN-US"> Re: [GraphHopper] About Intermediate
Data<o:p></o:p></span></span></p>
</div>
</div>
<p class="MsoNormal" style="text-align:left" align="left"><span
lang="EN-US"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"
style="margin-bottom:12.0pt;text-align:left" align="left"><span
lang="EN-US">Hey </span><span
style="font-family:Wingdings" lang="EN-US">n</span><span
style="font-size:7.0pt" lang="EN-US"> </span><span
lang="EN-US">Pengzhan Hao,<br>
<br>
the graph files are (mostly) independent from the
algorithm, they are just used to avoid the costly
reparsing of the OSM file everytime you restart
GraphHopper. The only difference is that CH creates some
additional edges, so called shortcuts.<br>
<br>
The graph is organized as described here:<br>
<a moz-do-not-send="true"
href="https://github.com/graphhopper/graphhopper/blob/master/docs/core/quickstart-from-source.md#2-the-graph">https://github.com/graphhopper/graphhopper/blob/master/docs/core/quickstart-from-source.md#2-the-graph</a><br>
<br>
Regards,<br>
Peter.<br>
<br>
</span><span style="font-size:12.0pt" lang="EN-US"><o:p></o:p></span></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span lang="EN-US">Just focus on GH
project , and interested in few questions:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">It occurs to me that
by using CHs algorithm ,several intermediate data binary
files appeared.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">So what these files
used for and how them organized in a data structure?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoListParagraph"
style="margin-left:18.0pt;text-indent:-18.0pt;mso-list:l0
level1 lfo2"><!--[if !supportLists]--><span
style="font-family:Wingdings" lang="EN-US"><span
style="mso-list:Ignore">n<span style="font:7.0pt
"Times New Roman""> </span></span></span><!--[endif]--><span
lang="EN-US">Pengzhan Hao<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal" style="text-align:left" align="left"><span
style="font-size:12.0pt;font-family:"Times New
Roman","serif"" lang="EN-US"><br>
<br>
<br>
<o:p></o:p></span></p>
<pre><span lang="EN-US">_______________________________________________<o:p></o:p></span></pre>
<pre><span lang="EN-US">GraphHopper mailing list<o:p></o:p></span></pre>
<pre><span lang="EN-US"><a moz-do-not-send="true" href="mailto:GraphHopper@openstreetmap.org">GraphHopper@openstreetmap.org</a><o:p></o:p></span></pre>
<pre><span lang="EN-US"><a moz-do-not-send="true" href="https://lists.openstreetmap.org/listinfo/graphhopper">https://lists.openstreetmap.org/listinfo/graphhopper</a><o:p></o:p></span></pre>
</blockquote>
<p class="MsoNormal" style="text-align:left" align="left"><span
style="font-size:12.0pt;font-family:"Times New
Roman","serif"" lang="EN-US"><br>
<br>
<br>
<o:p></o:p></span></p>
<pre><span lang="EN-US">-- <o:p></o:p></span></pre>
<pre><span lang="EN-US">GraphHopper.com - Fast & Flexible Road Routing<o:p></o:p></span></pre>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
GraphHopper mailing list
<a class="moz-txt-link-abbreviated" href="mailto:GraphHopper@openstreetmap.org">GraphHopper@openstreetmap.org</a>
<a class="moz-txt-link-freetext" href="https://lists.openstreetmap.org/listinfo/graphhopper">https://lists.openstreetmap.org/listinfo/graphhopper</a>
</pre>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
GraphHopper.com - Fast & Flexible Road Routing</pre>
</body>
</html>