I try to simulate flow on directed capacity graphs.
The graph g is represented as 3 column matrix or a list of edges
containing: capacity starting-vertex ending-vertex.
g
5 1 2 NB. edge from 1 to 2 with capacity 5
8 2 3
7 1 3
...
A single flow-path is represented as its strength and all vertices:
fp
5 1 2 3 NB. flow of strength 5 from vertex 1 to vertex 2 to vertex 3
The search for paths is done with this verb:
NB. x capacity graph y flow path
NB. result: list of flow paths adding one vertex to the path
NB. the flow strength is the minimum of the edge capacity and the former
flow strength
NB. cycles are excluded
search_paths =: 4 : 0
NB. t =: ending vertex not within path and starting vertex equals path end
t=.( -.({:"1 x) e. }.}: y)*.(1{"1 x)={:y
(({. y)<.t#{."1 x) ,.(}. y),"1 0 t#{:"1 x
)
The idea is to use this like
(,/ @:(g&search_paths "_ 1))^:3 ,: _ 1
Eventually paths are finished and I get the following
0 0 0 0 0 0
0 0 0 0 0 0
5 1 3 4 6 2
4 1 3 5 6 2
...
A step before there were 4 paths but 2 are finished and give an empty
result.
How must the results be combined other than with ,/
such that empty path results just disappear?
I have tried to box the result and several other construction, but did
not succeed.
Any help is welcome!
Markus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
