Quantcast

pathfinding: edge weight dependent on path-taken-so-far

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

pathfinding: edge weight dependent on path-taken-so-far

Robert Fleming
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

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: pathfinding: edge weight dependent on path-taken-so-far

Robert Fleming
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 12:15 PM
To: [hidden email]
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



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: pathfinding: edge weight dependent on path-taken-so-far

Rushang Karia

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.

cid:image001.png@01D0C621.7A212F80

 

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:[hidden email]]
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 12:15 PM
To: [hidden email]
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

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: pathfinding: edge weight dependent on path-taken-so-far

Robert Fleming
In reply to this post by Robert Fleming
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 12:15 PM
To: [hidden email]
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

 



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: pathfinding: edge weight dependent on path-taken-so-far

Rushang Karia

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:[hidden email]]
Sent: Friday, July 24, 2015 3:10 PM
To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 12:15 PM
To: [hidden email]
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

 

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: pathfinding: edge weight dependent on path-taken-so-far

Robert Fleming
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 3:10 PM


To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 12:15 PM
To: [hidden email]
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

 

 



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: pathfinding: edge weight dependent on path-taken-so-far

Rushang Karia
Thanks for the paper. I also did not know about such objects.
 
Yeah, I think you might need to implement the method on your own. If memory serves me right,  the shortest path implementation uses an iterator which cannot be modified. So changing the shortest path method to use this might be difficult.

Date: Fri, 24 Jul 2015 16:31:48 -0700
From: [hidden email]
To: [hidden email]
CC: [hidden email]
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 3:10 PM


To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: [hidden email]
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 <[hidden email]> 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:[hidden email]]
Sent: Friday, July 24, 2015 12:15 PM
To: [hidden email]
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

 

 



------------------------------------------------------------------------------
_______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...