Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Eclipse Projects » GEF » How the ShortestPathRouter works?
How the ShortestPathRouter works? [message #202960] Tue, 15 November 2005 16:06 Go to next message
Eclipse UserFriend
Originally posted by: bashar.infromatik.uni-bonn.de

Is there any description somewhere (may be some external papers) about the
shortest path routing algorithm implemented in GEF?

Thanks
Re: How the ShortestPathRouter works? [message #202968 is a reply to message #202960] Tue, 15 November 2005 18:24 Go to previous messageGo to next message
Eclipse UserFriend
Originally posted by: none.us.ibm.com

Part of it is Dijkstra's algorithm. This part is very well documented. There
is another document that should be available online some time soon,
depending on how slow a particular government website is at posting it. It
was also briefly discussed at the EclipseCon 2005 presentation.

"Abul Bashar" <bashar@infromatik.uni-bonn.de> wrote in message
news:dld125$ljv$1@news.eclipse.org...
> Is there any description somewhere (may be some external papers) about the
> shortest path routing algorithm implemented in GEF?
>
> Thanks
Re: How the ShortestPathRouter works? [message #203197 is a reply to message #202968] Sat, 19 November 2005 02:02 Go to previous messageGo to next message
Eclipse UserFriend
Originally posted by: bashar.infromatik.uni-bonn.de

Thanks Randy, your presentation in EclipseCon2005 has nicely demonstrated
the algorithm.

From the presentation, the "incremental updating" (page-21) is not clear to
me. Does it mean - the router follows node movements and does any
update/re-route as necessary?

I need a router which avoids crossing through nodes, bends the edges
orthogonally with as less bend points and as less edge-crossing as possible
(no matter how long the paths are). Is implementing any similar router
already in progress or planned to develop in near future?




"Randy Hudson" <none@us.ibm.com> wrote in message
news:dld94q$27s$1@news.eclipse.org...
> Part of it is Dijkstra's algorithm. This part is very well documented.
> There is another document that should be available online some time soon,
> depending on how slow a particular government website is at posting it. It
> was also briefly discussed at the EclipseCon 2005 presentation.
>
> "Abul Bashar" <bashar@infromatik.uni-bonn.de> wrote in message
> news:dld125$ljv$1@news.eclipse.org...
>> Is there any description somewhere (may be some external papers) about
>> the shortest path routing algorithm implemented in GEF?
>>
>> Thanks
>
>
Re: How the ShortestPathRouter works? [message #203685 is a reply to message #203197] Wed, 23 November 2005 21:15 Go to previous messageGo to next message
Eclipse UserFriend
Originally posted by: none.us.ibm.com

"Abul Bashar" <bashar@infromatik.uni-bonn.de> wrote in message
news:dlm135$556$1@news.eclipse.org...
> Thanks Randy, your presentation in EclipseCon2005 has nicely demonstrated
> the algorithm.
>
> From the presentation, the "incremental updating" (page-21) is not clear
> to me. Does it mean - the router follows node movements and does any
> update/re-route as necessary?

Yes, it tracks changes, and when you call solve() it tries to do as few
calculations as possible.

> I need a router which avoids crossing through nodes, bends the edges
> orthogonally with as less bend points and as less edge-crossing as
> possible (no matter how long the paths are). Is implementing any similar
> router already in progress or planned to develop in near future?

Sorry, the orthogonal version seems to be much more difficult to implement.
The interesting thing about our SPR, is that we did it right for the
multiple path case. It's easy to route a single connection using shortest
path (even w/ orthogonal constraints).
Re: How the ShortestPathRouter works? [message #205539 is a reply to message #203685] Mon, 19 December 2005 13:32 Go to previous message
Eclipse UserFriend
Originally posted by: cricard.businessobjects.com

By the way, algorith.solve() returns a strange List of paths when the zoom
factor is not 1.0 (attached snapshot there:
http://img480.imageshack.us/img480/3008/zoombug6lg.png. Look at the dotted
dummy connection that's being routed while the mouse moves. Two bendpoints
are computed that are really far far away from the cursor's actual
location).
I wondered if this might be a GEF bug, or if some special code has to be
written.

Thanks for any hint,

Christophe.

"Randy Hudson" <none@us.ibm.com> wrote in message
news:dm2m5s$srp$1@news.eclipse.org...
>
> "Abul Bashar" <bashar@infromatik.uni-bonn.de> wrote in message
> news:dlm135$556$1@news.eclipse.org...
> > Thanks Randy, your presentation in EclipseCon2005 has nicely
demonstrated
> > the algorithm.
> >
> > From the presentation, the "incremental updating" (page-21) is not clear
> > to me. Does it mean - the router follows node movements and does any
> > update/re-route as necessary?
>
> Yes, it tracks changes, and when you call solve() it tries to do as few
> calculations as possible.
>
> > I need a router which avoids crossing through nodes, bends the edges
> > orthogonally with as less bend points and as less edge-crossing as
> > possible (no matter how long the paths are). Is implementing any similar
> > router already in progress or planned to develop in near future?
>
> Sorry, the orthogonal version seems to be much more difficult to
implement.
> The interesting thing about our SPR, is that we did it right for the
> multiple path case. It's easy to route a single connection using shortest
> path (even w/ orthogonal constraints).
>
>
Previous Topic:GMF Features
Next Topic:Newbie Polygon Question
Goto Forum:
  


Current Time: Thu Mar 28 17:14:32 GMT 2024

Powered by FUDForum. Page generated in 0.03126 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top