<html dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" id="owaParaStyle"></style>
</head>
<body fpstyle="1" ocsi="0">
<div style="direction: ltr;font-family: Tahoma;color: #000000;font-size: 10pt;">
<div style="direction:ltr; font-family:Tahoma; color:#000000; font-size:10pt">
<div style="direction:ltr; font-family:Tahoma; color:#000000; font-size:10pt">Hi Vicky,
<div><br>
</div>
<div>thank you for dealing with that problem. Those two options seem to be the feasible way. Adding the algorithm as a contribution myself sounds quite compelling - I appreciate your offer to guide me through the process.</div>
<div><br>
</div>
<div><span style="font-size: 10pt;">We are already heading towards the end of the project, so we decided to choose the first option and implemented the algorithm in an external program using rust.</span></div>
<div><br>
</div>
<div>Off-topic: As a contribution I could offer a simple script/tool which implements the "osm2pgrouting"-conversion-tool in Model Builder of ArcGIS using subprocess in python (e.g. if a user wants to calculate the cost value by himself). It's actually anything
but a big deal, however it might be quite helpful.</div>
<div><br>
</div>
<div>Nevertheless, it would be great if Bellman-Ford is going to be part of an updated version of pgrouting.</div>
<div><br>
</div>
<div>Best regards,</div>
<div>Simon</div>
<div>
<div>
<div style="font-family:Times New Roman; color:#000000; font-size:16px">
<hr tabindex="-1">
<div id="divRpF388206" style="direction:ltr"><font face="Tahoma" size="2" color="#000000"><b>Von:</b> pgrouting-dev [pgrouting-dev-bounces@lists.osgeo.org]" im Auftrag von "Vicky Vergara [vicky@georepublic.de]<br>
<b>Gesendet:</b> Donnerstag, 1. Dezember 2016 17:34<br>
<b>An:</b> pgRouting developers mailing list<br>
<b>Betreff:</b> Re: [pgrouting-dev] algorithm allowing negative edge costs<br>
</font><br>
</div>
<div></div>
<div>
<div dir="ltr">
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">Hello,<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">Currently we don't have Bellman-Ford.<br>
<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">We are trying to add as many graph functionality from boost::graph, that function is certainly one of the goals.<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">It is not planned for the 2.4 version of pgRouting due to release on march next year, and I guess that
<br>
waiting is not an option.<br>
<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">from my point of view, is see 2 possible approaches:<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">option 1)<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">Use the
</span><span style="font-family:arial,helvetica,sans-serif"><a href="http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/bellman_ford_shortest.html" target="_blank">http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/bellman_ford_shortest.html</a> on an independent
program.<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">option 2)<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">Add the
</span><span style="font-family:arial,helvetica,sans-serif"><span style="font-family:arial,helvetica,sans-serif"></span><span style="font-family:arial,helvetica,sans-serif"><a href="http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/bellman_ford_shortest.html" target="_blank">http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/bellman_ford_shortest.html</a>
in</span>to pgRouting, and the use it from the database.<br>
<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">Of course, as pgRouting developer, I see that option 2 has its advantages:<br>
</span><span style="font-family:arial,helvetica,sans-serif"><span style="font-family:arial,helvetica,sans-serif">we can guide you on how to add it to pgRouting,<br>
</span></span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">part of your theses work would be open source,<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">let the world use your work!!!<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">you can have the contribution as part of your resume.<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"></span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"><br>
On any option, how long would it take it to do it?, might depend on your C++ coding skills.<br>
<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">please, keep me posted on tour decision.<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"><br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif">Vicky<br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"><br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"><br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"><br>
</span></div>
<div class="gmail_default" style="font-family:comic sans ms,sans-serif"><span style="font-family:arial,helvetica,sans-serif"><br>
</span></div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Dec 1, 2016 at 7:56 AM, Haumann Simon <span dir="ltr">
<<a href="mailto:haumanns@student.ethz.ch" target="_blank">haumanns@student.ethz.ch</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex; border-left:1px #ccc solid; padding-left:1ex">
<div>
<div style="direction:ltr; font-family:Tahoma; color:#000000; font-size:10pt">
<div style="font-family:Times New Roman; color:#000000; font-size:16px">
<div id="m_-8302592480552486306divRpF546076" style="direction:ltr"><span style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small">Hello,</span></div>
<div>
<div style="direction:ltr; font-family:Tahoma; color:#000000; font-size:10pt">
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
<br>
</div>
<div style="line-height:normal"><font size="2" color="#222222" face="arial, sans-serif">for a project in the course of my master thesis, I use pgRouting to find the route with least energy consumption for e-bikes. Accordingly, my model calculates the energy
consumption (Wh) which is implemented as cost factor. Due to recuperation, I have several negative edge costs. </font><span style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; background-color:rgb(255,255,255)">Therefore, I need an algorithm
which takes this circumstance into concideration. Unfortunetly, the appropriate single source shortest path (SSSP) algorithm (Bellman-Ford) is not yet part of pgRouting ( </span><a href="http://www.boost.org/doc/libs/master/libs/graph/doc/bellman_ford_shortest.html" style="font-size:10pt" target="_blank">http://www.boost.org/doc/<wbr>libs/master/libs/graph/doc/<wbr>bellman_ford_shortest.html</a> ).<span style="font-size:10pt"> <wbr>Previous
enquiries ( </span><a href="http://lists.osgeo.org/pipermail/pgrouting-users/2013-July/001589.html" style="font-size:10pt" target="_blank">http://lists.osgeo.org/<wbr>pipermail/pgrouting-users/<wbr>2013-July/001589.html</a><span style="font-size:10pt"> ) did
not solve that problem.</span></div>
<div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
<br>
</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
<span style="background-color:rgb(255,255,255)">Do you have any recommendation how to deal with this kind of matter?</span></div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
<br>
</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
Possible approaches:</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
<br>
</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
- Anyone who created a beta version / pgRouting-command of the above mentioned Bellman-Ford?</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
- altering existing all pairs algorithms (johnson's, floyd warshall) which theoretically allow scattered negative edge costs (in pgRouting too?) to SSSP like dijkstra</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
- idea for a workaround (e.g. adapting the cost calculating model so there are no negative edges no more)</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
- another develompment tool / framework that runs Belman Ford?</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
<br>
</div>
<div style="color:rgb(34,34,34); font-family:arial,sans-serif; font-size:small; line-height:normal">
Thanks for your help!</div>
</div>
</div>
</div>
</div>
</div>
</div>
<br>
______________________________<wbr>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" rel="noreferrer" target="_blank">http://lists.osgeo.org/<wbr>mailman/listinfo/pgrouting-dev</a><br>
</blockquote>
</div>
<br>
<br clear="all">
<br>
-- <br>
<div class="gmail_signature">
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<pre>Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky@<a href="http://georepublic.de" target="_blank">georepublic.de</a>
Web: <a href="https://georepublic.info" target="_blank">https://georepublic.info</a>
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
<span></span></pre>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>