Safe Haskell	None
Language	Haskell98

Warshall

Documentation

traceSolve :: String -> a -> a Source #

traceSolveM :: Monad m => String -> m () Source #

class SemiRing a where Source #

Methods

oplus :: a -> a -> a Source #

otimes :: a -> a -> a Source #

ozero :: a Source #

oone :: a Source #

Instances

Instances details

SemiRing PPoly Source #
Instance details Defined in Polarity Methods oplus :: PPoly -> PPoly -> PPoly Source # otimes :: PPoly -> PPoly -> PPoly Source # ozero :: PPoly Source # oone :: PPoly Source #
SemiRing Pol Source #
Instance details Defined in Polarity Methods oplus :: Pol -> Pol -> Pol Source # otimes :: Pol -> Pol -> Pol Source # ozero :: Pol Source # oone :: Pol Source #
SemiRing Weight Source #
Instance details Defined in Warshall Methods oplus :: Weight -> Weight -> Weight Source # otimes :: Weight -> Weight -> Weight Source # ozero :: Weight Source # oone :: Weight Source #

type Matrix a = Array (Int, Int) a Source #

warshall :: SemiRing a => Matrix a -> Matrix a Source #

data Weight Source #

Constructors

Finite Int
Infinite

Instances

Instances details

SemiRing Weight Source #
Instance details Defined in Warshall Methods oplus :: Weight -> Weight -> Weight Source # otimes :: Weight -> Weight -> Weight Source # ozero :: Weight Source # oone :: Weight Source #
Show Constraint Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> Constraint -> ShowS # show :: Constraint -> String # showList :: [Constraint] -> ShowS #
Show Weight Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> Weight -> ShowS # show :: Weight -> String # showList :: [Weight] -> ShowS #
Eq Weight Source #
Instance details Defined in Warshall Methods (==) :: Weight -> Weight -> Bool # (/=) :: Weight -> Weight -> Bool #
Ord Weight Source #
Instance details Defined in Warshall Methods compare :: Weight -> Weight -> Ordering # (<) :: Weight -> Weight -> Bool # (<=) :: Weight -> Weight -> Bool # (>) :: Weight -> Weight -> Bool # (>=) :: Weight -> Weight -> Bool # max :: Weight -> Weight -> Weight # min :: Weight -> Weight -> Weight #

inc :: Weight -> Int -> Weight Source #

data Node rigid Source #

Constructors

Rigid rigid
Flex FlexId

Instances

Instances details

Show rigid => Show (Node rigid) Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> Node rigid -> ShowS # show :: Node rigid -> String # showList :: [Node rigid] -> ShowS #
Eq rigid => Eq (Node rigid) Source #
Instance details Defined in Warshall Methods (==) :: Node rigid -> Node rigid -> Bool # (/=) :: Node rigid -> Node rigid -> Bool #
Ord rigid => Ord (Node rigid) Source #
Instance details Defined in Warshall Methods compare :: Node rigid -> Node rigid -> Ordering # (<) :: Node rigid -> Node rigid -> Bool # (<=) :: Node rigid -> Node rigid -> Bool # (>) :: Node rigid -> Node rigid -> Bool # (>=) :: Node rigid -> Node rigid -> Bool # max :: Node rigid -> Node rigid -> Node rigid # min :: Node rigid -> Node rigid -> Node rigid #

data Rigid Source #

Constructors

RConst Weight
RVar RigidId

Instances

Instances details

Show Constraint Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> Constraint -> ShowS # show :: Constraint -> String # showList :: [Constraint] -> ShowS #
Show Rigid Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> Rigid -> ShowS # show :: Rigid -> String # showList :: [Rigid] -> ShowS #
Eq Rigid Source #
Instance details Defined in Warshall Methods (==) :: Rigid -> Rigid -> Bool # (/=) :: Rigid -> Rigid -> Bool #
Ord Rigid Source #
Instance details Defined in Warshall Methods compare :: Rigid -> Rigid -> Ordering # (<) :: Rigid -> Rigid -> Bool # (<=) :: Rigid -> Rigid -> Bool # (>) :: Rigid -> Rigid -> Bool # (>=) :: Rigid -> Rigid -> Bool # max :: Rigid -> Rigid -> Rigid # min :: Rigid -> Rigid -> Rigid #

type NodeId = Int Source #

type RigidId = Int Source #

type FlexId = Int Source #

type Scope = RigidId -> Bool Source #

infinite :: Rigid -> Bool Source #

isBelow :: Rigid -> Weight -> Rigid -> Bool Source #

data Constrnt edgeLabel rigid flexScope Source #

Constructors

NewFlex FlexId flexScope
Arc (Node rigid) edgeLabel (Node rigid)

Instances

Instances details

Show Constraint Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> Constraint -> ShowS # show :: Constraint -> String # showList :: [Constraint] -> ShowS #

type Constraint = Constrnt Weight Rigid Scope Source #

arc :: Node Rigid -> Int -> Node Rigid -> Constraint Source #

type Constraints = [Constraint] Source #

emptyConstraints :: Constraints Source #

data Graph edgeLabel rigid flexScope Source #

Constructors

Graph
Fields flexScope :: Map FlexId flexScope nodeMap :: Map (Node rigid) NodeId intMap :: Map NodeId (Node rigid) nextNode :: NodeId graph :: NodeId -> NodeId -> edgeLabel

initGraph :: SemiRing edgeLabel => Graph edgeLabel rigid flexScope Source #

type GM edgeLabel rigid flexScope = State (Graph edgeLabel rigid flexScope) Source #

addFlex :: FlexId -> flexScope -> GM edgeLabel rigid flexScope () Source #

addNode :: (Eq rigid, Ord rigid) => Node rigid -> GM edgeLabel rigid flexScope Int Source #

addEdge :: (Eq rigid, Ord rigid, SemiRing edgeLabel) => Node rigid -> edgeLabel -> Node rigid -> GM edgeLabel rigid flexScope () Source #

addConstraint :: (Eq rigid, Ord rigid, SemiRing edgeLabel) => Constrnt edgeLabel rigid flexScope -> GM edgeLabel rigid flexScope () Source #

buildGraph :: (Eq rigid, Ord rigid, SemiRing edgeLabel) => [Constrnt edgeLabel rigid flexScope] -> Graph edgeLabel rigid flexScope Source #

mkMatrix :: Int -> (Int -> Int -> a) -> Matrix a Source #

data LegendMatrix a b c Source #

Constructors

LegendMatrix
Fields matrix :: Matrix a rowdescr :: Int -> b coldescr :: Int -> c

Instances

Instances details

(Show a, Show b, Show c) => Show (LegendMatrix a b c) Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> LegendMatrix a b c -> ShowS # show :: LegendMatrix a b c -> String # showList :: [LegendMatrix a b c] -> ShowS #

type Solution = Map Int MaxExpr Source #

emptySolution :: Solution Source #

extendSolution :: Solution -> Int -> SizeExpr -> Solution Source #

type MaxExpr = [SizeExpr] Source #

data SizeExpr Source #

Constructors

SizeVar Int Int
SizeConst Weight

Instances

Instances details

Show SizeExpr Source #
Instance details Defined in Warshall Methods showsPrec :: Int -> SizeExpr -> ShowS # show :: SizeExpr -> String # showList :: [SizeExpr] -> ShowS #

sizeRigid :: Rigid -> Int -> SizeExpr Source #

solve :: Constraints -> Maybe Solution Source #