Eclipse Community Forums: GEF » How the ShortestPathRouter works?

Home » Eclipse Projects » GEF » How the ShortestPathRouter works?

How the ShortestPathRouter works? [message #202960]

Tue, 15 November 2005 11:06

Eclipse User

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 13:24

Eclipse User

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]

Fri, 18 November 2005 21:02

Eclipse User

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 16:15

Eclipse User

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 08:32

Eclipse User

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:

-=] Back to Top [=-

Current Time: Sat Jul 12 16:13:57 EDT 2025

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter