Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Robert F. <fle...@gm...>]

Just found this paper: http://www.win.tue.nl/~jfg/articles/CSR-08-28.pdf

It seems to describe the type of graph I need but surprisingly declares:
"switching graphs ... have hardly been studied"

I'll see about modifying the shortest-path algorithm. Thanks for that
suggestion.

On Fri, Jul 24, 2015 at 4:00 PM, Rushang Karia <rus...@ho...>
wrote:

> Yes. As I said it may allow for that situation. If you do not want it then
> you will need to modify the shortest path algorithm in Jgrapht and account
> for this. You can change the edge weights but when the already implemented
> algorithm is executed it will not account for something like what you are
> needing to achieve.
>
>
>
> It should be relatively easy to do. I hope somebody else can share some
> light in case my suggestion is not optimal.
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 3:10 PM
>
> *To:* Rushang Karia
> *Cc:* jgr...@li...
> *Subject:* Re: [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Hmm, does that Inf edge somehow prevent an algorithm from returning a path
> like L2->COM->L1? I can see that the Inf will discourage the algorithm from
> jumping straight from L2 to L1, but will it not still allow L2->COM->L1?
>
>
>
> On Fri, Jul 24, 2015 at 3:00 PM, Rushang Karia <rus...@ho...>
> wrote:
>
> Ah. This makes the mutually exclusive thing more clear.
>
>
>
> Well one solution might be to just form the complete graph adding infinity
> edges between terminals that cannot be connected. This will I guess ensure
> that you never take an invalid path.
>
>
>
> Lets consider your example below, By forming a complete graph it would
> look like the figure below.
>
>
>
> When you formed the graph you added an infinity edge between L1 and L2. So
> when the method executes it will never have a path of the form ABxxL1 L2 xx
> CD. It may however have a path that looks like
>
> AB L1xxCDxxL2xx
>
>
>
> Does this look like a solution. The  dotted lines represent the rest of
> the graph which we are not concerned about.
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 1:35 PM
> *To:* Rushang Karia
> *Cc:* jgr...@li...
> *Subject:* Re: [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Hi Rushang,
>
> Thanks for your quick response! Maybe the traffic analogy isn't the best
> one.
>
> More to the point: a SPCO/SPTT electrical switch such as
> https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg
>
> I'm representing this switch as two edges: one connecting L1 to COM and
> one connecting L2 to COM. Both of those edges are available for path
> traversal, but the switch can't be in both positions simultaneously. I.e.,
> the switch cannot not allow L1 to connect to L2.
>
> I was thinking of somehow using edge weights dynamically, such that if an
> algorithm uses the L1-COM edge, then the L2-COM edge would have a very high
> weight.
>
>
>
> What do you think?
>
>
>
> Thanks,
>
> Robert
>
>
>
> On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...>
> wrote:
>
> I guess this classifies as an online algorithm. As for mutually exclusive
> events, they mean independent events, I do not see how you are relating it
> to edge weights in a shortest path scenario? Could you please explain it so
> that I can be sure of my assumption?
>
>
>
> And to answer your question, you will need to implement an online
> algorithm for the shortest path that changes the graph as data of each
> vertex (stoplight) changes. Is this something what you wanted to achieve?
>
>
>
> Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1,
> A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets
> suppose that when you were inspecting distances at point B, a stoplight
> turned on and now B-C = 100 because of the stoplight. Then the new shortest
> path is A-C at that point in time? But this means you need to backtrack all
> the way back to the source node.
>
>
>
> Let me know if my assumption of your problem is correct?
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 12:15 PM
> *To:* jgr...@li...
> *Subject:* [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Sorry if this has already been asked/answered on the list.
>
>
>
> When finding the shortest path between two vertices in a directed graph,
> is there any way for the weight of an edge to be dependent on which other
> edges are in the path? E.g. as a way to implement mutually exclusive edges.
>
>
>
> Example: an intersection of two roads, controlled by stoplights. At any
> given moment, traffic is allowed through in one direction. *Because* of
> that, the other paths through that intersection are unavailable (i.e. very
> high weight).
>
>
>
> Thanks!
>
> Robert
>
>
>
>
>