用于处理由邻居列表函数定义的(可能是无限的)图形的库

Question

这是我在各种编程语言中无数次使用过的模式:

1. 遇到一个问题,可以很容易地简化为一些图算法.
2. 定义邻接函数:outEdges :: MyNode -> [MyNode].
3. 编码所述图算法的一些通用形式,该算法将该函数作为其第一个参数.

例如,考虑这种(有目的效率低下)的方法来计算两个单词之间的编辑距离.我们将计算通过广度优先搜索将一个单词转换为另一个单词所需的最少插入和删除次数.

import Data.List
import Data.Maybe

alphabet :: String
alphabet = ['a'..'z']

wordNeighbors :: String -> [String]
wordNeighbors word = deletions ++ insertions where
    insertions = [pre++[c]++suf | (pre,suf) <- splits, c <- alphabet]
    deletions =  [pre++suf      | (pre,_:suf) <- take (length word) splits]

    splits = zip (inits word) (tails word)

shortestDistance :: (Eq a,Hashable a)=> (a -> [a]) -> a -> a -> Maybe Int
shortestDistance edgeFunc source target =
    -- 8 lines of code where I do a breadth-first traversal,
    -- using a HashSet to track previously visited nodes;
    -- yawn...

editDistance :: String -> String -> Int
editDistance a b = fromJust $ shortestDistance wordNeighbors a b

main = print $ editDistance "cat" "can"  -- prints 2

问题是,我对第3步感到非常厌倦.(见shortestDistance上文......)

我觉得我已经写了数百次相同的算法.我喜欢它,如果我可以只是以某种方式利用FGL或Data.Graph并完成它,但据我所知,最终需要构建某种类型的Graph数据结构严格的设置所有节点.这是一个问题,因为在许多问题中,图形是无限的(例如在上面的例子中).

我特别询问Haskell,因为Haskell非常关注组合器,我以某种方式预期其中许多算法已经存在于某个地方.

---

附录:以下是除了最短路径之外我经常写的其他函数示例:

-- Useful for organizing the computation of a recursively-defined
-- property of the nodes in an acyclic graph, such as nimbers.
dfsPostOrder :: (v -> [v]) -> v -> [v]
dfsPostOrder adjFunc root = ...

-- Find all nodes connected in some manner to the root node.
-- In case I know the components are finite size, but am not sure
-- of a nice way to express their contents.
-- (Note: The API below is only good for undirected graphs)
getComponent :: (v -> [v]) -> v -> Set v
getComponent adjFunc root = ...

-- Lazily organize the graph into groups by their minimum distance
-- to any of the nodes in @roots@.
-- One could use this to help incrementalize parts of e.g. a Game
-- of Life or Kinetic Monte Carlo simulation by locating regions
-- invalidated by changes in the state.
groupsByProximity :: (v -> [v]) -> Set v -> [Set v]
groupsByProximity adjFunc roots = ...

---

TL; DR: 是否有任何通用的方法来编写可能无限的,可能是循环的有向图的算法 - 例如由邻接函数(Node -> [Node]或Node -> [(Node, Weight)])定义的图？

Answer 1

我认为大多数"广度优先"搜索算法实际上都是某种"最佳优先"算法.也就是说,搜索边界被放置在优先级队列中,该优先级队列确定访问节点的顺序.

我找到了两个实现通用最佳优先算法的软件包:

• 一个明星
• 单子,Dijkstra算法

这两个模块都具有非常通用的接口 - 即您提供邻居功能,节点间距离功能和(在A星的情况下)启发式功能.

通过适当选择启发式和距离函数,您可以将搜索映射到这些算法之一.例如,该专利描述了一种采用A-star来解决编辑距离问题的方法.