Search code examples
jgrapht

Multiple weights per Edge in a JGraphT DAG

Is there a way in JGraphT that I can assign multiple weights to a single edge? For example, suppose I have a graph representing travel-time between cities. I want to assign edge-weights for "time by plane", "time by car", "time by bus", etc., and then find least-cost route by some specified mode of travel.

One approach I can think of is to have distinct graph for each travel mode and then add every city vertex to every graph but that seems like a messy and memory intensive solution.

My next thought was that I might be able to extend the class implementing the graph ( probably DirectedWeightedPseudograph) and customize the getEdgeWeight() method to take an additional argument specifying which weight value to use. That, however, would require extending all the algorithm classes as well (e.g., DijkstraShortestPath) which I am trying to avoid.

To get around that problem I considered the following:

  1. Extend my Graph class by adding a method setWeightMode(enum mode)
  2. customize the getEdgeWeight() method to use the currently assigned mode to determine which weight value to return to the caller.

On the plus side it would be 100% transparent to any existing analysis classes. On the negative side, it would not be thread-safe.

At this point I'm out of ideas. Can anyone suggest an approach that is scalable for large graphs, supports multi-threading, and minimizes the need to re-implement code already provided by JGraphT?

Solution

  • There exists a much easier solution: you want to use the AsWeightedGraph class. This is a wrapper class that allows you to create different weighted views of an underlying graph. From the class description:

    Provides a weighted view of a graph. The class stores edge weights internally. All getEdgeWeight calls are handled by this view; all other graph operations are propagated to the graph backing this view. This class can be used to make an unweighted graph weighted, to override the weights of a weighted graph, or to provide different weighted views of the same underlying graph. For instance, the edges of a graph representing a road network might have two weights associated with them: a travel time and a travel distance. Instead of creating two weighted graphs of the same network, one would simply create two weighted views of the same underlying graph.