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

[John S. <js...@gm...>]

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


On Mon, Apr 13, 2015 at 8:00 AM, Rushang Karia <rus...@ho...>
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: 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
>
>
>
> ------------------------------------------------------------------------------
> 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
>