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

[Joris K. <j.k...@gm...>]

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
>