msakai / pseudo-boolean / 87

Committed 23 Mar 2024 04:07PM UTC coverage: 93.632% (+0.5%) from 93.148%

Build # 87

Build Type

push

github

Committed by

web-flow

Commit Message

Merge 54e5e7037 into 3349efa05

Run Details

46 of 48 new or added lines in 5 files covered. (95.83%)

1 existing line in 1 file now uncovered.

544 of 581 relevant lines covered (93.63%)

0.94 hits per line

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

73.81

/src/Data/PseudoBoolean/Types.hs

{-# LANGUAGE BangPatterns, DeriveDataTypeable, DeriveGeneric #-}
{-# OPTIONS_GHC -Wall #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.PseudoBoolean.Types
-- Copyright   :  (c) Masahiro Sakai 2011-2015
-- License     :  BSD-style
-- 
-- Maintainer  :  masahiro.sakai@gmail.com
-- Portability :  non-portable (BangPatterns, DeriveDataTypeable, DeriveGeneric)
-- 
-- References:
--
-- * Input/Output Format and Solver Requirements for the Competitions of
--   Pseudo-Boolean Solvers
--   <http://www.cril.univ-artois.fr/PB11/format.pdf>
--
-----------------------------------------------------------------------------

module Data.PseudoBoolean.Types
  (
  -- * Abstract Syntax
    Formula (..)
  , Objective
  , Constraint
  , OptDir (..)
  , Op (..)
  , SoftFormula (..)
  , SoftConstraint
  , Sum
  , WeightedTerm
  , Term
  , Lit
  , Var

  -- * Internal utilities
  , pbComputeNumVars
  , pbProducts
  , wboComputeNumVars
  , wboProducts
  , wboNumSoft
  ) where

import GHC.Generics (Generic)
import Control.Monad
import Control.DeepSeq
import Data.Data
import Data.OptDir
import Data.Set (Set)
import qualified Data.Set as Set
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import Data.Hashable
import Data.Maybe

-- | Pair of /objective function/ and a list of constraints.
data Formula
  = Formula
  { pbObjectiveFunction :: Maybe Objective
  , pbConstraints :: [Constraint]
  , pbNumVars :: !Int
  , pbNumConstraints :: !Int
  }
  deriving (Eq, Ord, Show, Read, Typeable, Data, Generic)

instance NFData Formula
instance Hashable Formula

-- | Objective type and sum of weighted terms.
type Objective = (OptDir, Sum)

-- | Lhs, relational operator and rhs.
type Constraint = (Sum, Op, Integer)

-- | Relational operators
data Op
  = Ge -- ^ /greater than or equal/
  | Le -- ^ /lesser than or equal/
  | Gt -- ^ /greater than/
  | Lt -- ^ /lesser than/
  | Eq -- ^ /equal/
  | NEq -- ^ /not equal/
  deriving (Eq, Ord, Show, Read, Enum, Bounded, Typeable, Data, Generic)

instance NFData Op
instance Hashable Op

-- | A pair of /top cost/ and a list of soft constraints.
data SoftFormula
  = SoftFormula
  { wboTopCost :: Maybe Integer
  , wboConstraints :: [SoftConstraint]
  , wboNumVars :: !Int
  , wboNumConstraints :: !Int
  }
  deriving (Eq, Ord, Show, Read, Typeable, Data, Generic)

instance NFData SoftFormula
instance Hashable SoftFormula

-- | A pair of weight and constraint.
type SoftConstraint = (Maybe Integer, Constraint)

-- | Sum of 'WeightedTerm'
type Sum = [WeightedTerm]

-- | Coefficient and 'Term'
type WeightedTerm = (Integer, Term)

-- | List of variables interpreted as products
type Term = [Lit]

-- | Positive (resp. negative) literals are represented as positive (resp. negative) integers.
type Lit = Int

-- | Variable are repserented as positive integers.
type Var = Int

-- | Utility function for computing number of variables in given objective function and constraints.
pbComputeNumVars :: Maybe Sum -> [Constraint] -> Int
pbComputeNumVars obj cs = maximum (0 : vs)
  where
    vs = do
      s <- maybeToList obj ++ [s | (s,_,_) <- cs]
      (_, tm) <- s
      lit <- tm
      return $ abs lit

-- | Utility function for computing number of variables in given objective function and constraints.
wboComputeNumVars :: [SoftConstraint] -> Int
wboComputeNumVars cs = maximum (0 : vs)
  where
    vs = do
      s <- [s | (_, (s,_,_)) <- cs]
      (_, tm) <- s
      lit <- tm
      return $ abs lit

pbProducts :: Formula -> Set IntSet
pbProducts formula = Set.fromList $ do  
  s <- maybeToList (fmap snd (pbObjectiveFunction formula)) ++ [s | (s,_,_) <- pbConstraints formula]
  (_, tm)  <- s
  let tm2 = IntSet.fromList tm
  guard $ IntSet.size tm2 > 1
  return tm2

wboProducts :: SoftFormula -> Set IntSet
wboProducts softformula = Set.fromList $ do
  (_,(s,_,_)) <- wboConstraints softformula
  (_, tm) <- s
  let tm2 = IntSet.fromList tm
  guard $ IntSet.size tm2 > 1
  return tm2

wboNumSoft :: SoftFormula -> Int
wboNumSoft softformula = length [() | (Just _, _) <- wboConstraints softformula]

1	{-# LANGUAGE BangPatterns, DeriveDataTypeable, DeriveGeneric #-}
2	{-# OPTIONS_GHC -Wall #-}
3	-----------------------------------------------------------------------------
4	-- \|
5	-- Module : Data.PseudoBoolean.Types
6	-- Copyright : (c) Masahiro Sakai 2011-2015
7	-- License : BSD-style
8	--
9	-- Maintainer : masahiro.sakai@gmail.com
10	-- Portability : non-portable (BangPatterns, DeriveDataTypeable, DeriveGeneric)
11	--
12	-- References:
13	--
14	-- * Input/Output Format and Solver Requirements for the Competitions of
15	-- Pseudo-Boolean Solvers
16	-- <http://www.cril.univ-artois.fr/PB11/format.pdf>
17	--
18	-----------------------------------------------------------------------------
19
20	module Data.PseudoBoolean.Types
21	(
22	-- * Abstract Syntax
23	Formula (..)
24	, Objective
25	, Constraint
26	, OptDir (..)
27	, Op (..)
28	, SoftFormula (..)
29	, SoftConstraint
30	, Sum
31	, WeightedTerm
32	, Term
33	, Lit
34	, Var
35
36	-- * Internal utilities
37	, pbComputeNumVars
38	, pbProducts
39	, wboComputeNumVars
40	, wboProducts
41	, wboNumSoft
42	) where
43
44	import GHC.Generics (Generic)
45	import Control.Monad
46	import Control.DeepSeq
47	import Data.Data
48	import Data.OptDir
49	import Data.Set (Set)
50	import qualified Data.Set as Set
51	import Data.IntSet (IntSet)
52	import qualified Data.IntSet as IntSet
53	import Data.Hashable
54	import Data.Maybe
55
56	-- \| Pair of /objective function/ and a list of constraints.
57	data Formula
58	= Formula
59	{ pbObjectiveFunction :: Maybe Objective	1✔
60	, pbConstraints :: [Constraint]	1✔
61	, pbNumVars :: !Int	1✔
62	, pbNumConstraints :: !Int	1✔
63	}
64	deriving (Eq, Ord, Show, Read, Typeable, Data, Generic)	×
65
66	instance NFData Formula	×
67	instance Hashable Formula	×
68
69	-- \| Objective type and sum of weighted terms.
70	type Objective = (OptDir, Sum)
71
72	-- \| Lhs, relational operator and rhs.
73	type Constraint = (Sum, Op, Integer)
74
75	-- \| Relational operators
76	data Op
77	= Ge -- ^ /greater than or equal/
78	\| Le -- ^ /lesser than or equal/
79	\| Gt -- ^ /greater than/
80	\| Lt -- ^ /lesser than/
81	\| Eq -- ^ /equal/
82	\| NEq -- ^ /not equal/
UNCOV 83	deriving (Eq, Ord, Show, Read, Enum, Bounded, Typeable, Data, Generic)	×
84
85	instance NFData Op	×
86	instance Hashable Op	×
87
88	-- \| A pair of /top cost/ and a list of soft constraints.
89	data SoftFormula
90	= SoftFormula
91	{ wboTopCost :: Maybe Integer	1✔
92	, wboConstraints :: [SoftConstraint]	1✔
93	, wboNumVars :: !Int	1✔
94	, wboNumConstraints :: !Int	1✔
95	}
96	deriving (Eq, Ord, Show, Read, Typeable, Data, Generic)	×
97
98	instance NFData SoftFormula	×
99	instance Hashable SoftFormula	×
100
101	-- \| A pair of weight and constraint.
102	type SoftConstraint = (Maybe Integer, Constraint)
103
104	-- \| Sum of 'WeightedTerm'
105	type Sum = [WeightedTerm]
106
107	-- \| Coefficient and 'Term'
108	type WeightedTerm = (Integer, Term)
109
110	-- \| List of variables interpreted as products
111	type Term = [Lit]
112
113	-- \| Positive (resp. negative) literals are represented as positive (resp. negative) integers.
114	type Lit = Int
115
116	-- \| Variable are repserented as positive integers.
117	type Var = Int
118
119	-- \| Utility function for computing number of variables in given objective function and constraints.
120	pbComputeNumVars :: Maybe Sum -> [Constraint] -> Int
121	pbComputeNumVars obj cs = maximum (0 : vs)	1✔
122	where
123	vs = do	1✔
124	s <- maybeToList obj ++ [s \| (s,_,_) <- cs]	1✔
125	(_, tm) <- s	1✔
126	lit <- tm	1✔
127	return $ abs lit	1✔
128
129	-- \| Utility function for computing number of variables in given objective function and constraints.
130	wboComputeNumVars :: [SoftConstraint] -> Int
131	wboComputeNumVars cs = maximum (0 : vs)	1✔
132	where
133	vs = do	1✔
134	s <- [s \| (_, (s,_,_)) <- cs]	1✔
135	(_, tm) <- s	1✔
136	lit <- tm	1✔
137	return $ abs lit	1✔
138
139	pbProducts :: Formula -> Set IntSet
140	pbProducts formula = Set.fromList $ do	1✔
141	s <- maybeToList (fmap snd (pbObjectiveFunction formula)) ++ [s \| (s,_,_) <- pbConstraints formula]	1✔
142	(_, tm) <- s	1✔
143	let tm2 = IntSet.fromList tm	1✔
144	guard $ IntSet.size tm2 > 1	1✔
145	return tm2	1✔
146
147	wboProducts :: SoftFormula -> Set IntSet
148	wboProducts softformula = Set.fromList $ do	1✔
149	(_,(s,_,_)) <- wboConstraints softformula	1✔
150	(_, tm) <- s	1✔
151	let tm2 = IntSet.fromList tm	1✔
152	guard $ IntSet.size tm2 > 1	1✔
153	return tm2	×
154
155	wboNumSoft :: SoftFormula -> Int
156	wboNumSoft softformula = length [() \| (Just _, _) <- wboConstraints softformula]	×

msakai / pseudo-boolean / 87

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

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