首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Haskell生成具有QuickCheck属性的图

问Haskell生成具有QuickCheck属性的图
EN

Stack Overflow用户
提问于 2016-04-27 23:03:57
回答 1查看 366关注 0票数 0

图形具有以下属性:

“edge”类型表示两个节点之间的边。

代码语言:javascript
复制
data Edge v = Edge {source :: v, target :: v}
          deriving (Show,Eq,Ord)

“graph”类型表示有向图。

代码语言:javascript
复制
data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
           deriving Show

函数'isDAG‘测试一个图是否是无圈的。

代码语言:javascript
复制
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是否为一个森林(一组树)

代码语言:javascript
复制
isForest :: Ord v => DAG v -> Bool
isForest g = isDAG g && all (\v -> length (adj g v) <= 1) (nodes g)

生成器代码是:

DAGs生成器

代码语言:javascript
复制
dag :: (Ord v, Arbitrary v) => Gen (DAG v)
dag = arbitrary `suchThat` isDAG

森林生成器

代码语言:javascript
复制
forest :: (Ord v, Arbitrary v) => Gen (Forest v)
forest = arbitrary `suchThat` isForest

我想改进生成器Dag和Forest,这样它们就是基于它们的属性来定义的,而不是用'suchThat‘来定义。我该怎么做呢?

提前谢谢你。

EN

回答 1

Stack Overflow用户

发布于 2016-04-28 05:00:50

我认为核心问题是如何生成DAG和森林。

什么是森林?森林是树木的集合。树是什么?树是一个图,其中除根节点外的每个节点都恰好有一个父节点。我们如何将其转化为算法?生成节点列表。对于列表中从左开始的每个节点,随机选取其右侧的一个元素作为其父元素,并为其创建一条边。

什么是DAG?DAG是一个有向无环图。我们可以使用DAG做什么?我们可以对它们进行拓扑排序。那是什么意思?这意味着我们可以将它们放在一个从左到右的序列中。我们如何将其转化为算法?生成节点列表。对于列表中从左到右的每个节点,随机选取它右侧的一个元素子集,并为它们创建一条边。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/36893695

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档