Raul Miller schrieb:
On Fri, Sep 5, 2008 at 11:37 AM, Markus Schmidt-Gröttrup
<[EMAIL PROTECTED]> wrote:
Good suggestion, but in my case the graph contains one source and one
target vertex, and only the paths reaching from source to target are of
interest.
Then you either need to:
[a] Compute all paths from the source and select those which reach the
target, or
[b] Identify your target to your computational mechanism.
I expect that approach [b] would be simpler.
You are absolutely right the target is specified, but not within the
search_paths verb.
Furtermore I am not using the
(;@:(<@(g&search_paths"1)))^: anything
thing I suggested. Actually the search_paths is called in another verb,
that controls
if either the target has been reached or no path exists to the target.
This gives a breadth-first search which is known to be optimal to the
situation.
The algorithm is the Ford-Fulkerson method: as long as a path to the
target can be found add it to the flow.
That said, I am wondering about cases like:
g=: 6 1 2,6 2 3,6 2 4,6 3 5,:6 4 5
where 1 is your desired source node and 5 is your desired end node.
Hypothetically speaking you would have
6 1 2 3
6 1 2 4
as an intermediate result, but your maximum flow through
both paths can not exceed 6. You would have this same
intermediate result if
g=: 12 1 2,6 2 3,6 2 4,6 3 5,:6 4 5
but here your maximum flow through both paths can
exceed 6.
In other words, I do not think your data structure is
capable of representing the concepts you have specified.
This implies that you should be using a different
data structure which represents some different
kind of abstraction.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
