Suggestions for "shortest path with conditional nodes"?

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

Suggestions for "shortest path with conditional nodes"?

org.jgrapht
Hello.

I'm modelling an abstract network. The network is represented by a
simple undirected graph (SimpleGraph, specifically). Vertices in the
graph represent networked devices, and the edges represent hardwired
network links.

I calculate routes in the network using DijkstraShortestPath. This
all works very well, but I'd now like to model nodes being optionally
on/off. If a node is "off", then it should be considered a dead end
when calculating routes. In other words, if a node is "off", then it
should be routed around if possible.

Does anyone have any suggestions as to how to get the shortest paths
when some nodes should conditionally be considered "invisible"?

In order to keep the code that deals with graphs simple, and because
the edges in the graph represent hardwired links, I don't really want
to remove vertices/edges when a node is switched off - the edges
carry a meaning beyond simply whether or not a packet can be routed
that way.

Right now, I'm leaning towards maintaining two graphs (one with the
physical links, the other with only the active nodes and links), but
I'd rather not do this as it obviously requires keeping two mutable
data structures synchronized.

M

------------------------------------------------------------------------------
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
Develop your own process in accordance with the BPMN 2 standard
Learn Process modeling best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
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: Suggestions for "shortest path with conditional nodes"?

Rushang Karia
The best way to do this acc to me is to modify the shortest path algorithm.
Keep a hashset of the nodes which are turned off and simply prune the
recursion tree.

You can copy paste the source code of the algorithm in a new class.

Let me know if you have questions or if you find a better solution.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]]
Sent: Sunday, April 12, 2015 6:23 AM
To: [hidden email]
Subject: [jgrapht-users] Suggestions for "shortest path with conditional
nodes"?

Hello.

I'm modelling an abstract network. The network is represented by a simple
undirected graph (SimpleGraph, specifically). Vertices in the graph
represent networked devices, and the edges represent hardwired network
links.

I calculate routes in the network using DijkstraShortestPath. This all works
very well, but I'd now like to model nodes being optionally on/off. If a
node is "off", then it should be considered a dead end when calculating
routes. In other words, if a node is "off", then it should be routed around
if possible.

Does anyone have any suggestions as to how to get the shortest paths when
some nodes should conditionally be considered "invisible"?

In order to keep the code that deals with graphs simple, and because the
edges in the graph represent hardwired links, I don't really want to remove
vertices/edges when a node is switched off - the edges carry a meaning
beyond simply whether or not a packet can be routed that way.

Right now, I'm leaning towards maintaining two graphs (one with the physical
links, the other with only the active nodes and links), but I'd rather not
do this as it obviously requires keeping two mutable data structures
synchronized.

M

----------------------------------------------------------------------------
--
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT Develop your
own process in accordance with the BPMN 2 standard Learn Process modeling
best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
Develop your own process in accordance with the BPMN 2 standard
Learn Process modeling best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
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: Suggestions for "shortest path with conditional nodes"?

John Sichi
Administrator

On Mon, Apr 13, 2015 at 8:00 AM, Rushang Karia <[hidden email]> wrote:
The best way to do this acc to me is to modify the shortest path algorithm.
Keep a hashset of the nodes which are turned off and simply prune the
recursion tree.

You can copy paste the source code of the algorithm in a new class.

Let me know if you have questions or if you find a better solution.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]]
Sent: Sunday, April 12, 2015 6:23 AM
To: [hidden email]
Subject: [jgrapht-users] Suggestions for "shortest path with conditional
nodes"?

Hello.

I'm modelling an abstract network. The network is represented by a simple
undirected graph (SimpleGraph, specifically). Vertices in the graph
represent networked devices, and the edges represent hardwired network
links.

I calculate routes in the network using DijkstraShortestPath. This all works
very well, but I'd now like to model nodes being optionally on/off. If a
node is "off", then it should be considered a dead end when calculating
routes. In other words, if a node is "off", then it should be routed around
if possible.

Does anyone have any suggestions as to how to get the shortest paths when
some nodes should conditionally be considered "invisible"?

In order to keep the code that deals with graphs simple, and because the
edges in the graph represent hardwired links, I don't really want to remove
vertices/edges when a node is switched off - the edges carry a meaning
beyond simply whether or not a packet can be routed that way.

Right now, I'm leaning towards maintaining two graphs (one with the physical
links, the other with only the active nodes and links), but I'd rather not
do this as it obviously requires keeping two mutable data structures
synchronized.

M

----------------------------------------------------------------------------
--
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT Develop your
own process in accordance with the BPMN 2 standard Learn Process modeling
best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
Develop your own process in accordance with the BPMN 2 standard
Learn Process modeling best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
Develop your own process in accordance with the BPMN 2 standard
Learn Process modeling best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
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: Suggestions for "shortest path with conditional nodes"?

org.jgrapht
On 2015-04-13T05:42:02 +0000
"Hoeltzcke, Claus-Dieter (EXTERN: Ethon)"
<[hidden email]> wrote:

> Hi,
>
> use masks using the MaskFunctor<> interface.

On 2015-04-13T10:26:30 -0700
John Sichi <[hidden email]> wrote:

> You can use one of the subgraph implementations for this:
>
> http://jgrapht.org/javadoc/org/jgrapht/graph/Subgraph.html
> http://jgrapht.org/javadoc/org/jgrapht/graph/MaskSubgraph.html
>

Interesting!

Thanks all, this looks ideal.

M

------------------------------------------------------------------------------
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
Develop your own process in accordance with the BPMN 2 standard
Learn Process modeling best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...