Re: [jgrapht-users] Suggestions for "shortest path with conditional nodes"?

[Rushang K. <rus...@ho...>]

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: org...@io... [mailto:org...@io...] 
Sent: Sunday, April 12, 2015 6:23 AM
To: jgr...@li...
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
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users