On Tue, Apr 24, 2012 at 6:39 AM, R.E. Boss <r.e.b...@planet.nl> wrote:
> Given the directed graph G (see <http://www.jsoftware.com/jwiki/RE%20Boss>
> http://www.jsoftware.com/jwiki/RE%20Boss) by its edges
>
> |: G
> 0 1 2 2 3 4 4 5 5 6 7 7 8 9 10 10 11 11 11 12 12 12
> 1 2 3 4 5 6 5 7 8 7 9 10 10 11 12 11 13 14 15 16 15 14
>
> determine all (different) paths from root 0 to the leaves.
In the general case, paths can be variable in length. So paths should
be boxed. We also need to deal with individual paths. I would use
"paths" to for labels for the boxed cases and "path" for labels for
the unboxed cases.
Also, note that cycles can cause problems. If we allow cycles the
number of paths between a node and a leaf can be infinite. So we
should explicitly disallow cycles. A cycle is a path where the same
node appears twice. Since the problem definition did not disallow
cycles, I feel that this exclusion belongs in the implementation.
Here is one way to treat this example:
'ST EN'=: ".;._2]0 :0
0 1 2 2 3 4 4 5 5 6 7 7 8 9 10 10 11 11 11 12 12 12
1 2 3 4 5 6 5 7 8 7 9 10 10 11 12 11 13 14 15 16 15 14
)
ROOTPATH=: ,0
ROOTPATHS=: ,<ROOTPATH
extendpath=: <@,"1 0 EN #~ ST = {:
validpaths=: = ~.&.>
extendpaths=: ] ~.@(, (#~ validpaths)@;) extendpath&.>
leafpaths=: #~ ] -.@e. }:&.>
paths_to_leaves=: [: leafpaths extendpaths^:_
(#, [: ~. #@>) paths_to_leaves ROOTPATHS
39 9
In this case, all 39 noncyclic paths which lead to leaf nodes are the
same length (9 nodes).
If this algorithm were generally useful, I would rebuild it so the
table that describes the graph would be the left argument for the
above verbs.
> This took me quite some time(days!). Am I getting old?
Everyone that is alive is getting old, so the answer would have to be yes.
As for the time you needed, I expect that you were focusing on other issues.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
