從任意節點列表生成邊線

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 


instance Arbitrary v => Arbitrary (Edge v) where 
    arbitrary = do s <- arbitrary 
        t <- arbitrary 
        return $ Edge {source = s, target = t} 

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where 
    arbitrary = aux `suchThat` validGraph 
     where aux = do lNodes <- arbitrary 
         lEdges <- arbitrary 
         return $ Graph {nodes = fromList lNodes, edges = fromList lEdges}

我目前有這個來生成我的圖形。但是通過在ghci上使用示例，我注意到它或者不會生成邊或者它會生成一個邊。是否可以控制生成的邊數量？我該怎麼做？從任意節點列表生成邊線

編輯：圖形被認爲是有效的： 1 - 邊緣的源節點和目標節點存在。 2-A節點不能成爲多個Edge的源。

來源

2016-04-23 ohiohai

它可能真的很難（可以說它非常幸運*）像這樣生成一個'validGraph'（特別是當有更多的邊時） - 生成節點然後從這些節點中繪製成對的節點來生成邊緣可能會更好 – Carsten

事情是那些對需要任意生成。我如何告訴哈斯克爾形成隨機對？ – ohiohai

安arbitrary值是Gen monad中的值。你可以在這個monad中做更多的事情，而不僅僅是將arbitrary的值組合在一起。您可以在其他Gen操作，包括choose執行任何：

choose :: Random a => (a, a) -> Gen a 
生成在給定的範圍包括隨機元素。

您可以使用choose生成除arbitrary之外的其他隨機值。

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where 
    arbitrary = do 
     nodes <- arbitrary 
     let 
      lNodes = toList nodes 
      numNodes = length lNodes 
      arbitraryEdge = do 
       source <- elements lNodes 
       target <- elements lNodes 
       return $ Edge { 
        source = source, 
        target = target 
       } 
     numEdges <- choose (0, numNodes * numNodes) 
     lEdges <- vectorOf numEdges arbitraryEdge 
     return $ Graph {nodes = nodes, edges = fromList lEdges}

這種樸素的實現在生成大圖時效率不高。如果它不需要每次使用生成的值時都需要掃描列表，那麼它可能會成爲圖表中節點數量的一個因素。elements

來源

2016-04-23 16:55:49 Cirdec

我明白了。然而，這帶來了同樣的問題..它不會產生邊緣，或者如果我用類似於您發送給我的東西來做，它會但不會以我的圖形被認爲有效的方式進行... – ohiohai

順便說一句，繼續我以前評論：如果我與你發送給我的東西它不會生成有效的圖表，因爲它繼續使用重複節點作爲「源」到幾個邊緣。一個有效的圖形不能有一個節點來源於多個Edge。 – ohiohai

@ohiohai這不是您在問題中指定的標準。如果一個節點不能成爲多於一條邊的源，則可以爲每個節點生成0或1條邊，而不是生成任意邊。它還表明你的圖形數據類型是錯誤的，因爲你可以把圖形表示爲'Map k（Maybe k）'，並且每個圖形總是有效的。 – Cirdec

從任意節點列表生成邊線

回答

相關問題