Re: [jgrapht-users] reverse-cost for UndirectedGraphs

[Mario B. <mar...@gm...>]

Thank you very much John and Joris. Both your replies were very
informative.

Actually yes, what I had in mind was a "mixed graph", but as both of you
have  pointed out, it seems this will be problematic. I will probably just
create a new path by reversing the nodes and assign a reverse_cost as
suggested to simulate one way roads. I work with millions of edges though,
and I am truly hoping that this won't result in a performance hit. Will
test it out.

Again, thank you very much.

Mario.


On Sat, Oct 30, 2021 at 5:09 AM Joris Kinable <j.k...@gm...> wrote:

>
> Hi Mario,
>
> These questions are best asked on stackoverflow as this will allow more
> people to benefit from the answer.
>
> Typically, what you want to do to represent a road network, is to use a
> directed graph. Each arc represents a set of driving lanes that are all in
> the same direction. To represent a one-way street, you would use 1 arc. To
> represent a street which can be driven in two directions, you would use 2
> arcs.
> Here's a simplified definition of a RoadSegment I've used in the past:
>
> public class RoadSegment{
>
>     /* Unique identifier of the road segment */
>     public final String ID;
>     /* Street name */
>     public final String streetName;
>     /* Set of waypoints defining the shape of the segment (for plotting
> and GPS routing) */
>     public final List<WayPoint> wayPoints;
>     /* Type of the road segment, e.g. highway, residential road */
>     public final RoadType roadType;
>     /* Speed limit in ft/sec */
>     public final int speedLimit;
>     /* Length of road segment in feet, rounded to the nearest integer */
>     public final int length;
>     /* Total number of lanes directed from the tail of this road segment,
> to the head of this road segment. */
>     public final int lanes;
>
>     ...
> }
> If you want to calculate the shortest path (in terms of distance), or the
> fastest path (in terms of time), the easiest thing to do is take advantage
> of the AsWeightedGraph class, as it allows you to run Dijkstra (or similar
> algorithms) with different weights.
>
> Now if you really insist, you can actually use jgrapht with mixed graphs,
> which contain both directed arcs and undirected edges. I've done this in
> the past, using the above RoadSegment class:
>
> /**
> * The following graphs are for routing purposes. They contain the city
> topology.
> * -undirectedRoutingGraph: graph containing all residential streets
> * -directedRoutingGraph: graph containing all the directed arcs
> (one-directional lanes, including one-directional streets)
> * -unionRoutingGraph: a union of the previous 2 graphs
> * **/
> public final Multigraph<RoutingNode, RoadSegment> undirectedRoutingGraph;
> public final DirectedMultigraph<RoutingNode, RoadSegment>
> directedRoutingGraph;
> public final MixedGraphUnion<RoutingNode, RoadSegment> unionRoutingGraph;
>
> Various graph algorithms work quite well on the above graph. Some need
> some tweaking. Either way, it's best if you can avoid using mixed graphs.
>
> Joris Kinable
>
>
> On Fri, Oct 29, 2021 at 4:55 AM John Sichi <js...@gm...> wrote:
>
>> Hi Mario,
>>
>> I think you are describing a "mixed graph", which we allow you to
>> construct via the union of an undirected and directed graph; but most of
>> our algorithms don't know what to do with such a beast, so it's not a
>> terribly useful concept yet.
>>
>> The problematic workaround is a directed graph with opposing edge pairs
>> simulating undirected edges.
>>
>> I don't believe there's currently anything in the way of algorithms being
>> improved to support mixed graphs; this would be a great GSoC project if we
>> are able to participate in that again in the future.
>>
>> There's one open bug for the current inability to directly instantiate a
>> mixed graph:
>>
>> https://github.com/jgrapht/jgrapht/issues/1039
>>
>> This also requires quite a bit of work under the hood.
>>
>>
>> On Tue, Oct 26, 2021 at 1:35 PM Mario Basa <mar...@gm...> wrote:
>>
>>> Is it possible to assign a reverse-cost along with the usual edge cost
>>> in  UndirectedGraphs? This is to simulate one-way passages in a road
>>> network.
>>>
>>> Thanks a lot.
>>>
>>> Mario.
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>