Re: [Rails-devel] Route calculation for huge runs

[John A. T. <ja...@ja...>]

On Sun, Aug 7, 2011 at 1:55 AM, Stefan Frey <ste...@we...> wrote:

> > A long, long time ago, I implemented route calculation by transforming
> the
> > problem to a flow graph and running the max-flow/min-cut algorithm on it
> > (sorry, I no longer have this code), which avoids exponential time.
>
> I think I can imagine how you approached this: You define the revenue of
> each
> node as negative cost of an edge inside the node and then minimize the
> costs
> (thus maximizing revenue) of the trains treated as flow.
>
> Even if you do not have the code any longer, can you still remember how you
> treated the issue of train length? And how did you ensure that each train
> at
> least visits one home token. I guess that it was some tricky adjustment of
> the
> graph, but maybe you can give some clues here.


It has been 24 years -- I was taking a Graph Theory class in grad school,
and one of the things we had to do was transform other traditional problems
to graphs and solve them using graph theory algorithms.  At the time we were
studying the Floyd-Fulkerson algorithm, so I am sure I used that.  Most of
the transforms involved creating extra nodes to represent other constraints,
or replacing each node in the base graph with a set of nodes to represent
those constraints.  I don't remember the specifics of how I solved it, but
it worked for 1830-style trains only (which was all I knew about at the
time).

-- 
John A. Tamplin