msakai / toysolver / 539

coverage: 69.236% (-0.5%) from 69.781%
539

push

github

msakai 
update CHANGELOG.markdown

10042 of 14504 relevant lines covered (69.24%)

0.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.21
/src/ToySolver/Graph/Base.hs
1 
{-# LANGUAGE FlexibleContexts #-}
2 
-----------------------------------------------------------------------------
3 
-- |
4 
-- Module      :  ToySolver.Graph.Base
5 
-- Copyright   :  (c) Masahiro Sakai 2020
6 
-- License     :  BSD-style
7 
--
8 
-- Maintainer  :  masahiro.sakai@gmail.com
9 
-- Stability   :  provisional
10 
-- Portability :  non-portable
11 
--
12 
-----------------------------------------------------------------------------
13 
module ToySolver.Graph.Base
14 
  ( EdgeLabeledGraph
15 
  , Graph
16 
  , graphToUnorderedEdges
17 
  , graphFromUnorderedEdges
18 
  , graphFromUnorderedEdgesWith
19 
  , isIndependentSet
20 
  ) where
21 









22



import Control.Monad










23



import Data.Array.IArray










24



import Data.Array.ST










25



import qualified Data.IntMap.Lazy as IntMap










26



import Data.IntMap.Lazy (IntMap)










27



import qualified Data.IntSet as IntSet










28



import Data.IntSet (IntSet)










29












30



type EdgeLabeledGraph a = Array Int (IntMap a)










31












32



type Graph = EdgeLabeledGraph ()










33












34



graphToUnorderedEdges :: EdgeLabeledGraph a -> [(Int, Int, a)]










35



graphToUnorderedEdges g = do




1✔





36



  (node1, nodes) <- assocs g




1✔





37



  (node2, a) <- IntMap.toList $ snd $ IntMap.split node1 nodes




1✔





38



  return (node1, node2, a)




1✔





39












40



graphFromUnorderedEdges :: Int -> [(Int, Int, a)] -> EdgeLabeledGraph a










41



graphFromUnorderedEdges = graphFromUnorderedEdgesWith const




×







42












43



graphFromUnorderedEdgesWith :: (a -> a -> a) -> Int -> [(Int, Int, a)] -> EdgeLabeledGraph a










44



graphFromUnorderedEdgesWith f n es = runSTArray $ do




1✔





45



  a <- newArray (0, n-1) IntMap.empty




1✔





46



  let ins i x l = do




1✔





47



        m <- readArray a i




1✔





48



        writeArray a i $! IntMap.insertWith f x l m




×







49



  forM_ es $ \(node1, node2, a) -> do




1✔





50



    ins node1 node2 a




1✔





51



    ins node2 node1 a




1✔





52



  return a




1✔





53












54



isIndependentSet :: EdgeLabeledGraph a -> IntSet -> Bool










55



isIndependentSet g s = null $ do




1✔





56



  (node1, node2, _) <- graphToUnorderedEdges g




1✔





57



  guard $ node1 `IntSet.member` s




1✔





58



  guard $ node2 `IntSet.member` s




1✔





59



  return ()




×





















    

  • 

    •