在 Haskell QuickCheck 中测试 'DAG' aka 非循环图属性
Testing 'DAG' aka acyclic graphs properties in Haskell QuickCheck
module Graph where
import Control.Monad.State
import Data.Maybe
import Data.Set as Set
-- | 'Edge' represents an edge entre two nodes.
data Edge v = Edge {source :: v, target :: v}
deriving (Show,Eq,Ord)
data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
deriving Show
-- | 'Eq' for graphs.
instance Ord v => Eq (Graph v) where
g == g' = nodes g == nodes g' && edges g == edges g'
isValid :: Ord v => Graph v -> Bool
isValid g = (Set.map source (edges g) `Set.union` Set.map target (edges g)) `isSubsetOf` nodes g
-- | 'isDAG' tests if a graph is acyclic
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)
我正在尝试使用 QuickCheck 来测试 'isDAG',你能给我一个 'isDAG' 遵守的 属性 吗?
prop_isDAG :: Graph Int -> Property
prop_isDAG g =
我认为这是正确的函数声明,如果不正确,请随时更改!
这是我为另一个功能制作的另一个示例,用于指导可能的帮助者了解我正在寻找的内容:
-- | The function 'isSubgraphOf' tests if the first graph is subgraph of the second.
isSubgraphOf :: Ord v => Graph v -> Graph v -> Bool
isSubgraphOf g g' = isSubsetOf (nodes g) (nodes g') && isSubsetOf (edges g) (edges g')
这是它遵循的 QuickCheck 属性:
-- QuickCheck proprety to test 'isSubgraphOf'
prop_isSubgraphOf :: Graph Int -> Property
prop_isSubgraphOf g = forAll (elements $ elems $ nodes g) $ \v -> adj g v `isSubsetOf` edges g
prop_dag :: Property
prop_dag = forAll (dag :: Gen (DAG Int)) $ \g -> collect (length (edges g)) $ isDAG g
这正是我要找的。
module Graph where
import Control.Monad.State
import Data.Maybe
import Data.Set as Set
-- | 'Edge' represents an edge entre two nodes.
data Edge v = Edge {source :: v, target :: v}
deriving (Show,Eq,Ord)
data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
deriving Show
-- | 'Eq' for graphs.
instance Ord v => Eq (Graph v) where
g == g' = nodes g == nodes g' && edges g == edges g'
isValid :: Ord v => Graph v -> Bool
isValid g = (Set.map source (edges g) `Set.union` Set.map target (edges g)) `isSubsetOf` nodes g
-- | 'isDAG' tests if a graph is acyclic
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)
我正在尝试使用 QuickCheck 来测试 'isDAG',你能给我一个 'isDAG' 遵守的 属性 吗?
prop_isDAG :: Graph Int -> Property
prop_isDAG g =
我认为这是正确的函数声明,如果不正确,请随时更改!
这是我为另一个功能制作的另一个示例,用于指导可能的帮助者了解我正在寻找的内容:
-- | The function 'isSubgraphOf' tests if the first graph is subgraph of the second.
isSubgraphOf :: Ord v => Graph v -> Graph v -> Bool
isSubgraphOf g g' = isSubsetOf (nodes g) (nodes g') && isSubsetOf (edges g) (edges g')
这是它遵循的 QuickCheck 属性:
-- QuickCheck proprety to test 'isSubgraphOf'
prop_isSubgraphOf :: Graph Int -> Property
prop_isSubgraphOf g = forAll (elements $ elems $ nodes g) $ \v -> adj g v `isSubsetOf` edges g
prop_dag :: Property
prop_dag = forAll (dag :: Gen (DAG Int)) $ \g -> collect (length (edges g)) $ isDAG g
这正是我要找的。