Re: [jgrapht-users] Algorithms for flow graphs

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

You could create a view graph which delegates to the real graph for
everything else, but returns the desired attribute when getEdgeWeight
is called.

See AsWeightedGraph for a similar case where we impose weights on top
of an unweighted graph.

JVS

On Thu, Mar 24, 2011 at 10:47 AM, Joris Kinable <de...@gm...> wrote:
> Hello,
>
> I'm about to build an algorithm for min-cost flow graphs. As you can
> imagine, this needs a flow graph which typically has the following
> properties:
>
> 1. Edges have a Capacity and a Cost
> 2. Vertices have a real postive/negative value indicating the
> demand/supply associated with each vertex.
> 3. The graph is directed
>
> Due to the generics in JgraphT I can easily create vertex/edge classes
> which maintain these values. There is however a problem with the
> currently existing algorithms in JgraphT. For example, in a flow
> graph, a shortest path is usually (or at least in my case) calculated
> using the edge costs as 'distances'. Furthermore, a max flow algorithm
> utilizes the edge capacities. When I would use
> org.jgrapht.alg.DijkstraShortestPath, the algorithm uses the
> getEdgeWeight(E edge) function to obtain the distances. Similarly,
> org.jgrapht.alg.EdmondsKarpMaximumFlow utilizes the getEdgeWeight(E
> edge) function to read the edge capacities. The getEdgeWeight(E edge)
> function can only return one value: either the edge capacity or the
> edge cost. What would be the cleanest way to resolve this issue
> (preferably something reusable by the jgrapht community)?
>
> ------------------------------------------------------------------------------
> Enable your software for Intel(R) Active Management Technology to meet the
> growing manageability and security demands of your customers. Businesses
> are taking advantage of Intel(R) vPro (TM) technology - will your software
> be a part of the solution? Download the Intel(R) Manageability Checker
> today! http://p.sf.net/sfu/intel-dev2devmar
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>