图形具有以下属性:
“edge”类型表示两个节点之间的边。
data Edge v = Edge {source :: v, target :: v}
deriving (Show,Eq,Ord)“graph”类型表示有向图。
data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
deriving Show函数'isDAG‘测试一个图是否是无圈的。
isDAG :: Ord v => Graph v -> Bool
isDAG g = isValid g && all nocycle (nodes g)
where nocycle v = all (\a -> v `notMember` reachable g a) $ Set.map target (adj g v)函数'isForest‘测试一个有效的DAG是否为一个森林(一组树)
isForest :: Ord v => DAG v -> Bool
isForest g = isDAG g && all (\v -> length (adj g v) <= 1) (nodes g)生成器代码是:
DAGs生成器
dag :: (Ord v, Arbitrary v) => Gen (DAG v)
dag = arbitrary `suchThat` isDAG森林生成器
forest :: (Ord v, Arbitrary v) => Gen (Forest v)
forest = arbitrary `suchThat` isForest我想改进生成器Dag和Forest,这样它们就是基于它们的属性来定义的,而不是用'suchThat‘来定义。我该怎么做呢?
提前谢谢你。
发布于 2016-04-28 05:00:50
我认为核心问题是如何生成DAG和森林。
什么是森林?森林是树木的集合。树是什么?树是一个图,其中除根节点外的每个节点都恰好有一个父节点。我们如何将其转化为算法?生成节点列表。对于列表中从左开始的每个节点,随机选取其右侧的一个元素作为其父元素,并为其创建一条边。
什么是DAG?DAG是一个有向无环图。我们可以使用DAG做什么?我们可以对它们进行拓扑排序。那是什么意思?这意味着我们可以将它们放在一个从左到右的序列中。我们如何将其转化为算法?生成节点列表。对于列表中从左到右的每个节点,随机选取它右侧的一个元素子集,并为它们创建一条边。
https://stackoverflow.com/questions/36893695
复制相似问题