<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Hi Peter, <br>
<br>
yes, this is related to the principle of CH, which I understand. <br>
I was focusing on the conditions actually tested by the class
LevelEdgeFilterCH . <br>
<br>
I do not understand the inheritance to LevelEdgeFilter and the
call to the super the the accept method, <br>
but since it is very deep into the code, I wanted to know if there
is something I do not understand wrt the invariants of the
PrepareContraction algorithm: eg: can the level of a node be
negative?<br>
<br>
Here is the accept method of LevelEdgeFilterCH. <br>
I've put some comments with //// to point the lines related to my
question. <br>
<br>
public final boolean accept( EdgeIterator iter )<br>
{<br>
if (!super.accept(iter)) ////here we check the accept
condition of LevelEdgeFilter <br>
{<br>
return false;<br>
}<br>
////at this point, we can go up or equal in the
hierarchy, not strictly down<br>
// ignore if it is skipNode or a endNode already
contracted<br>
int node = iter.getAdjNode();<br>
////in the test below, we ensure that we will stay at
level zero in the hierarchy, <br>
////meaning that we can only go to non-contracted
nodes, so what's the point of the call to super here above?<br>
return avoidNode != node &&
graph.getLevel(node) == 0;<br>
}<br>
<br>
<br>
regards<br>
--<br>
Renaud<br>
<br>
<br>
Le 2/10/2013 13:23, Peter K a écrit :<br>
</div>
<blockquote cite="mid:524C0236.6080805@yahoo.de" type="cite">
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<div class="moz-cite-prefix">Hi Renaud,<br>
<br>
the LevelEdgeFilterCH (additionally to the hierarchy filtering)
just makes sure that the specified node is excluded from the
dijkstra. If the dijkstra finds a shorter path (without that
node) we do not need the shortcut. E.g.:<br>
<pre> | |
..-A--B--C
| |
\-D-E-/
</pre>
To contract B we introduce several shortcuts. One of them is the
shortcut from A to C. But we can avoid that if we find a shorter
way from A to C without B.<br>
<br>
Regards,<br>
Peter.<br>
<br>
</div>
<blockquote cite="mid:524BF321.50003@cetic.be" type="cite">
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
Dear Peter, <br>
<br>
I have a question on the PrepareContractionHierarchies algo. <br>
<br>
There is a class LevelEdgeFilterCH, which is used in the
Dijkstra to check if the shortest path between two
non-contracted nodes pass through a node that we want to
contract. <br>
<br>
My point is that this class inherits from LevelEdgeFilter, and
uses its check, <br>
and I do not understand why; I fear that there is something I do
not understand. <br>
<br>
LevelEdgeFilter prevents us from strictly going down in the
hierarchy. <br>
and LevelEdgeFilterCH check this condition first. <br>
If it is OK, it further check that the neighbour node is not
contracted, that is: of level zero. <br>
Knowing that the source node is also non-contracted, this second
check seems stronger than the first check inherited from the
LevelEdgeFilter class. <br>
<br>
Thank you for your help. <br>
<br>
<div class="moz-signature">-- <br>
<table width="400" cellspacing="0">
<tbody>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0,
102, 0); background-color: rgb(255, 255, 255);
font-family: arial; font-style: normal; font-variant:
normal; font-weight: normal; font-size: 14px;
line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;"> <b>Renaud
De Landtsheer, Ir, Phd</b> </td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0,
102, 0); background-color: rgb(255, 255, 255);
font-family: arial; font-style: italic; font-variant:
normal; font-weight: normal; font-size: 14px;
line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;">Sr R&D
Engineer</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0,
102, 0); background-color: rgb(255, 255, 255);
font-family: arial; font-style: normal; font-variant:
small-caps; font-weight: normal; font-size: 14px;
line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;"> CETIC <br>
Rue des Frères Wright, 29/3 <br>
B-6041 Charleroi <br>
Phone: +32 71 490 754 </td>
</tr>
<tr>
<td colspan="2" style="border-top: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: italic; font-variant: normal;
font-weight: normal; font-size: 12px; line-height:
normal; font-size-adjust: none; font-stretch: normal;
vertical-align: top;" align="top">
<p><br>
</p>
</td>
</tr>
</tbody>
</table>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
GraphHopper mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:GraphHopper@openstreetmap.org">GraphHopper@openstreetmap.org</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="https://lists.openstreetmap.org/listinfo/graphhopper">https://lists.openstreetmap.org/listinfo/graphhopper</a>
</pre>
</blockquote>
<br>
<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>
<div class="moz-signature">-- <br>
<table width="400" cellspacing="0">
<tbody>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: normal; font-variant: normal;
font-weight: normal; font-size: 14px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;"> <b>Renaud De Landtsheer, Ir, Phd</b>
</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: italic; font-variant: normal;
font-weight: normal; font-size: 14px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;">Sr R&D Engineer</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: normal; font-variant: small-caps;
font-weight: normal; font-size: 14px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;">
CETIC <br>
Rue des Frères Wright, 29/3 <br>
B-6041 Charleroi <br>
Phone: +32 71 490 754 </td>
</tr>
<tr>
<td colspan="2" style="border-top: 1px solid rgb(0, 102, 0);
background-color: rgb(255, 255, 255); font-family: arial;
font-style: italic; font-variant: normal; font-weight:
normal; font-size: 12px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;" align="top">
<p><br>
</p>
</td>
</tr>
</tbody>
</table>
</div>
</body>
</html>