新泽西州 SML 中的图表

Question

我需要使用机器学习编写一些函数，该函数接收有向图的边列表[(1,2),(1,3),(3,2)] ，这意味着从 1 到 2 和从 1 到 3 的有向边...，并且我还收到两个顶点，我需要找到从第一个顶点到第二个顶点的所有可能路径以及可能路径的列表，例如对于顶点1, 2，我需要显示列表[[1,2],[1,3,2]]，我该怎么做ML如果可以不存储有关顶点的数据，提前感谢您的任何想法。

Answer 1

如果要存储有关顶点的数据，则需要从顶点到数据的有限映射。
该地图可能提供如下签名：

type 'a vmap (* vertex map *)
val empty : 'a vmap  (* empty map *)
val insert : vertex * 'a * 'a vmap -> 'a vmap  (* add info about a vertex *)
val lookup : vertex * 'a vmap -> 'a option  (* look for info about a vertex *)

要实现此签名，您可以考虑一个简单的 vertex * 'a 对列表，或者更雄心勃勃的东西，例如平衡二叉搜索树。

Answer 2

您可以存储有关顶点的数据！

例如，您想记录您访问过哪些顶点吗？

假设您有一个函数，可以从当前顶点递归地探索所有可能的未探索边。

它可以接受未探索的边的向量，加上当前顶点和目标顶点。它将返回成功到达目标顶点的路径向量。

在内部，它将找到从此顶点开始的边集，并针对该集中的每条边递归到自身，将所选边从未探索的边列表中删除到每个子函数中。

Answer 3

抱歉，我无法抗拒，

我在 雅虎！答案，我
回答了它。

该实现最初是基于创建一棵树的设计
遍历图；但最终还是符合设计的
Alex Brown 之前曾表达过。

最初规划是在Haskell中完成的，因此这个辅助函数

fun replicate len el = 
    if len = 0 then nil else el::replicate (len -1) el

：主要实现：

fun routes  dst (edges:(int * int) list) src  = 
    let val (very_possible,remotely_possible) =
            if null edges
            then (nil,nil)
            else List.partition ((fn s=> s = src) o #1) edges 
        val (raw_solutions,dsts_is_nx_srcs) = 
            List.partition  ((fn d => d = dst) o #2) very_possible
        val solutions = replicate  (length raw_solutions) [src,dst]
        val full_rest_routes =
            let val rest_rest_routes = 
                    map (routes dst remotely_possible)  
                            ( map #2 dsts_is_nx_srcs )
              in map (fn lst => src::lst) (List.concat rest_rest_routes)
     end
     in case (very_possible, solutions, remotely_possible)
        of (nil, _,  _)       => nil
         |  (_::_, (p::ps), _) =>  solutions @ full_rest_routes
         |  (_::_, nil, _::_)  =>  full_rest_routes
  |  (_   , nil, nil )  => nil
     end

用户界面：

fun getPaths edges src dst  =  routes dst edges src 

上面的代码来自 routes4.sml;
但省略了测试和IO。虽然时间不长，但我还是希望
它可以更简单。