combinat-diagrams (empty) → 0.1
raw patch · 11 files changed
+627/−0 lines, 11 filesdep +arraydep +basedep +coloursetup-changed
Dependencies added: array, base, colour, combinat, containers, diagrams-core, diagrams-lib, transformers, vector-space
Files
- LICENSE +29/−0
- Math/Combinat/Diagrams.hs +22/−0
- Math/Combinat/Diagrams/LatticePaths.hs +82/−0
- Math/Combinat/Diagrams/Partitions.hs +16/−0
- Math/Combinat/Diagrams/Partitions/Integer.hs +104/−0
- Math/Combinat/Diagrams/Partitions/NonCrossing.hs +126/−0
- Math/Combinat/Diagrams/Partitions/Plane.hs +75/−0
- Math/Combinat/Diagrams/Tableaux.hs +59/−0
- Math/Combinat/Diagrams/Trees/Binary.hs +60/−0
- Setup.lhs +3/−0
- combinat-diagrams.cabal +51/−0
+ LICENSE view
@@ -0,0 +1,29 @@+Copyright (c) 2014, Balazs Komuves+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++- Redistributions of source code must retain the above copyright notice,+this list of conditions and the following disclaimer.+ +- Redistributions in binary form must reproduce the above copyright notice,+this list of conditions and the following disclaimer in the documentation+and/or other materials provided with the distribution.+ +- Neither names of the copyright holders nor the names of the contributors+may be used to endorse or promote products derived from this software without+specific prior written permission. ++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+
+ Math/Combinat/Diagrams.hs view
@@ -0,0 +1,22 @@+ +-- | This module re-exports several of the individual submodules +module Math.Combinat.Diagrams + ( module Math.Combinat.Diagrams.LatticePaths + , module Math.Combinat.Diagrams.Partitions.Integer + , module Math.Combinat.Diagrams.Partitions.NonCrossing + , module Math.Combinat.Diagrams.Partitions.Plane + , module Math.Combinat.Diagrams.Tableaux + , module Math.Combinat.Diagrams.Trees.Binary + ) + where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Diagrams.LatticePaths +import Math.Combinat.Diagrams.Partitions.Integer +import Math.Combinat.Diagrams.Partitions.NonCrossing +import Math.Combinat.Diagrams.Partitions.Plane +import Math.Combinat.Diagrams.Tableaux +import Math.Combinat.Diagrams.Trees.Binary + +--------------------------------------------------------------------------------
+ Math/Combinat/Diagrams/LatticePaths.hs view
@@ -0,0 +1,82 @@+ +-- | Lattice path diagrams + +{-# LANGUAGE FlexibleContexts #-} +module Math.Combinat.Diagrams.LatticePaths where + +-------------------------------------------------------------------------------- + +import Math.Combinat.LatticePaths + +-- import Data.Monoid +import Data.VectorSpace +import Data.Colour +import Diagrams.Core +import Diagrams.Prelude + +-------------------------------------------------------------------------------- + +-- | Which orientation to draw the lattice paths +data LatticeConvention + = Hilly -- ^ the steps are @(1,1)@ and @(1,-1)@ + | UpRight -- ^ the steps are @(0,1)@ and @(0,1)@ + deriving (Eq,Show) + +-------------------------------------------------------------------------------- + +-- | Draws a lattice path with the default settings +drawLatticePath :: Renderable (Path R2) b => LatticePath -> Diagram b R2 +drawLatticePath = drawLatticePath' Hilly red True + +drawLatticePath' + :: Renderable (Path R2) b + => LatticeConvention -- ^ orientation + -> Colour Double -- ^ color + -> Bool -- ^ whether to draw a grid + -> LatticePath -- ^ whether to draw a grid + -> Diagram b R2 +drawLatticePath' convention color hasgrid xs = + if hasgrid + then path <> grid + else path + + where +{- + path = go 0 0 ps where + go !x !y [] = mempty + go !x !y (p:ps) = case p of + UpStep -> translate (r2 x y) up <> go (x+1) (y+1) ps + DownStep -> translate (r2 x y) dn <> go (x+1) (y-1) ps +-} + + linewidth = 0.025 + + path = path0 # lwL (linewidth*2) # lc color + grid = grid0 # lwL (linewidth ) + + path0 = fromOffsets [ case p of { UpStep -> up ; DownStep -> dn } | p <- xs ] + grid0 = case convention of + Hilly -> drawRectangularGrid (length xs, pathHeight xs) + UpRight -> drawRectangularGrid (b,a) + + (a,b) = pathNumberOfUpDownSteps xs + + (up,dn) = case convention of + Hilly -> ( r2 (1,1) , r2 (1,-1) ) + UpRight -> ( r2 (0,1) , r2 (1, 0) ) + +-------------------------------------------------------------------------------- + +-- | Draws a rectangular grid of the given size +drawRectangularGrid :: Renderable (Path R2) b => (Int,Int) -> Diagram b R2 +drawRectangularGrid (x,y) = grid # lc grey where + grid = horiz <> vert + + horiz = mconcat [ translateY (fromIntegral i) hline | i<-[0..y] ] + vert = mconcat [ translateX (fromIntegral j) vline | j<-[0..x] ] + + hline = fromOffsets [ (fromIntegral x) *^ unitX ] + vline = fromOffsets [ (fromIntegral y) *^ unitY ] + +-------------------------------------------------------------------------------- +
+ Math/Combinat/Diagrams/Partitions.hs view
@@ -0,0 +1,16 @@+ +-- | Young and Ferrers diagrams for integer partitions + +{-# LANGUAGE FlexibleContexts #-} +module Math.Combinat.Diagrams.Partitions + ( module Math.Combinat.Diagrams.Partitions.Integer + ) + where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Diagrams.Partitions.Integer + +-------------------------------------------------------------------------------- + +
+ Math/Combinat/Diagrams/Partitions/Integer.hs view
@@ -0,0 +1,104 @@+ +-- | Young and Ferrers diagrams for integer partitions + +{-# LANGUAGE FlexibleContexts #-} +module Math.Combinat.Diagrams.Partitions.Integer where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Partitions.Integer + +-- import Data.Monoid +import Data.VectorSpace +import Data.Colour +import Diagrams.Core +import Diagrams.Prelude + +-------------------------------------------------------------------------------- + +{- +-- this is now specified in the combinat library already + +-- | Which orientation to draw the Ferrers diagrams +data PartitionConvention + = EnglishNotation -- ^ English notation + | EnglishNotationCCW -- ^ English notation rotated by 90 degrees counterclockwise + | FrenchNotation -- ^ French notation (mirror of English notation to the x axis) + deriving (Eq,Show) +-} + +-------------------------------------------------------------------------------- + +partitionConventionTransformation :: PartitionConvention -> Diagram b R2 -> Diagram b R2 +partitionConventionTransformation conv what = + case conv of + EnglishNotation -> what + EnglishNotationCCW -> rotate (90 @@ deg) what + FrenchNotation -> scaleY (-1) what + +-------------------------------------------------------------------------------- + +-- | Draws a Ferrers diagram with the default settings (English notation, no boxes) +drawFerrersDiagram :: Renderable (Path R2) b => Partition -> Diagram b R2 +drawFerrersDiagram = drawFerrersDiagram' EnglishNotation black False + + +drawFerrersDiagram' + :: Renderable (Path R2) b + => PartitionConvention -- ^ orientation + -> Colour Double -- ^ color + -> Bool -- ^ whether to draw the boxes + -> Partition + -> Diagram b R2 +drawFerrersDiagram' convention color hasgrid part = + if hasgrid + then balls <> boxes + else balls + + where + + ps = fromPartition part :: [Int] + n = length ps + + balls = partitionConventionTransformation convention balls0 + + balls0 = mconcat [ ball j i | i<-[0..n-1], j<-[0..(ps!!i)-1] ] + # lc color + + ball x y = translate (r2 (0.5 + fromIntegral x, - 0.5 - fromIntegral y)) + $ circle ballradius # lwL linewidth # lc black # fc color + + ballradius = 0.30 + linewidth = 0.025 + + boxes = drawPartitionBoxes convention part + +-------------------------------------------------------------------------------- + +-- | Draws a partition as a grid of boxes (sometimes also called Young diagram) +drawPartitionBoxes :: Renderable (Path R2) b => PartitionConvention -> Partition -> Diagram b R2 +drawPartitionBoxes conv part = partitionConventionTransformation conv boxes + + where + + linewidth = 0.05 + + boxes = boxes0 # lc black # lwL linewidth + + boxes0 + | null ps = mempty + | otherwise = horiz <> vert + + ps = fromPartition $ part :: [Int] + qs = fromPartition $ dualPartition part :: [Int] + + f xs = head xs : xs + + horiz = mconcat [ translateY (fromIntegral (-i)) (hline j) | (i,j) <- zip [0..] (f ps) ] + vert = mconcat [ translateX (fromIntegral j ) (vline i) | (i,j) <- zip (f qs) [0..] ] + + hline x = fromOffsets [ (fromIntegral x) *^ unitX ] + vline y = fromOffsets [ (fromIntegral y) *^ unit_Y ] + +-------------------------------------------------------------------------------- +
+ Math/Combinat/Diagrams/Partitions/NonCrossing.hs view
@@ -0,0 +1,126 @@+ +-- | Diagrams of non-crossing partitions + +{-# LANGUAGE FlexibleContexts #-} +module Math.Combinat.Diagrams.Partitions.NonCrossing where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Partitions.NonCrossing + +-- import Data.Monoid +import Data.AffineSpace +import Data.VectorSpace +import Data.Colour +import Diagrams.Core +import Diagrams.Prelude +import Diagrams.TwoD.Text + +-------------------------------------------------------------------------------- + + +-- | Draws a Ferrers diagram with the default settings (English notation, no boxes) +drawNonCrossingCircleDiagram :: (Renderable (Path R2) b, Renderable Text b) => NonCrossing -> Diagram b R2 +drawNonCrossingCircleDiagram = drawNonCrossingCircleDiagram' grey False + + +drawNonCrossingCircleDiagram' + :: (Renderable (Path R2) b, Renderable Text b) + => Colour Double -- ^ color + -> Bool -- ^ whether to write numbers from @[1..n]@ next to the set elements + -> NonCrossing + -> Diagram b R2 +drawNonCrossingCircleDiagram' color hasnumbers (NonCrossing nc) = final where + + final = xdots <> xparts <> xcirc <> (if hasnumbers then numbers else mempty) + xparts = mconcat (map worker nc) # lc black # lwL linewidth # fc color + xdots = dots0 # lw none # fc black + xcirc = circle radius # lc red # lwL (linewidth*4) + + linewidth = 0.02 :: Double + + radius = 1.0 + radius2 = radius + extraradius + + extraradius = 0.10 + ballradius = 0.05 + + superradius = 1.30 + + n = length $ concat nc + fn = fromIntegral n + + r2p2 :: R2 -> P2 + r2p2 v = origin .+^ v + + p2r2 :: P2 -> R2 + p2r2 p = p .-. origin + + numbers = mconcat ns # lw none # fc blue + ns = [ translate v (scale 0.3 $ translate (r2 (0,-0.35)) $ text (show i)) + | (i,v) <- zip [1..n] (verticesR superradius) ] + + verticesR :: Double -> [R2] + verticesR r = [ r2 (r * sin phi , r * cos phi) | i <- [0..n-1] , let phi = fromIntegral i * 2*pi/fn ] + + verticesP :: Double -> [P2] + verticesP r = map r2p2 (verticesR r) + + vtxs = verticesP radius + + dots0 = mconcat [ translate vtx (circle ballradius # lc black) | vtx <- verticesR radius ] + + worker part = makeRoundedPolygonCCW extraradius [ vtxs!!(i-1) | i<-part ] + +{- + mkloop ixs = ixs ++ [head ixs] + worker [ix] = let p = vtxs !! (ix-1) + in translate (p2r2 p) (circle extraradius) + worker part = translate (p2r2 $ vtxs !! (head part - 1)) + $ (strokeTrail $ glueTrail $ trailFromVertices $ mkloop [ vtxs!!(i-1) | i<-part ]) +-} + +-------------------------------------------------------------------------------- + +makeRoundedPolygonCCW :: Renderable (Path R2) b => Double -> [P2] -> Diagram b R2 +makeRoundedPolygonCCW radius xs = + + case xs of + [] -> mempty + [x] -> translate (p2r2 x ) $ circle radius + (x:_) -> translate (p2r2 x ^+^ iniOfs) $ strokeTrail stuff + + where + + stuff = glueTrail $ mconcat $ concat $ go (xs ++ take 2 xs) + + iniOfs = case xs of (p:q:_) -> iniOfs' p q + iniOfs' p q = radius *^ nx where + u = q .-. p + (ux,uy) = unr2 u + ua = atan2 uy ux + ua' = ua - pi/2 + nx = r2 (cos ua' , sin ua') + + go (p:rest@(q:r:_)) = [ mySeg `mappend` myArc ] : go rest where + mySeg = trailFromOffsets [u] + myArc = arc' radius (ua' @@ rad) (va' @@ rad) + u = q .-. p + v = r .-. q + (ux,uy) = unr2 u + (vx,vy) = unr2 v + ua = atan2 uy ux + va = atan2 vy vx + ua' = ua - pi/2 + va' = va - pi/2 + -- nx = radius *^ r2 (cos ua' , sin ua') + go _ = [] + + r2p2 :: R2 -> P2 + r2p2 v = origin .+^ v + + p2r2 :: P2 -> R2 + p2r2 p = p .-. origin + +-------------------------------------------------------------------------------- +
+ Math/Combinat/Diagrams/Partitions/Plane.hs view
@@ -0,0 +1,75 @@+ +-- | Drawing plane partitions + +{-# LANGUAGE FlexibleContexts, TypeFamilies #-} +module Math.Combinat.Diagrams.Partitions.Plane where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Partitions.Integer +import Math.Combinat.Partitions.Plane + +import Math.Combinat.Diagrams.Tableaux as Tableaux + +-- import Data.Monoid +import Data.AffineSpace +import Data.VectorSpace +import Data.Colour +import Diagrams.Core +import Diagrams.Prelude +import Diagrams.TwoD.Text + +-------------------------------------------------------------------------------- + +drawPlanePartition3D :: (Renderable (Path R2) b) => PlanePart -> Diagram b R2 +drawPlanePartition3D = drawPlanePartition3D' (cadetblue,indianred,lawngreen) + +-- | Draws 3D-like (but in fact 2D) diagram of a plane partition, coloring the faces with the given colors +-- +drawPlanePartition3D' :: (Renderable (Path R2) b) => (Colour Double, Colour Double, Colour Double) -> PlanePart -> Diagram b R2 +drawPlanePartition3D' (col1,col2,col3) pp@(PlanePart pps) = final where + + final = leftSides # fc col1 # lwL linewidth + <> rightSides # fc col2 # lwL linewidth + <> topSides # fc col3 # lwL linewidth + + layers = planePartLayers pp + + linewidth = 0.05 :: Double + + dir_top = unitY + dir_left = fromDirection ( 210 @@ deg) + dir_right = fromDirection ((-30) @@ deg) + + ndir_top = negateV dir_top + ndir_left = negateV dir_left + ndir_right = negateV dir_right + + leftSides = mconcat $ zipWith lefts [0..] layers + rightSides = mconcat $ zipWith rights [0..] layers + + topSides = mconcat $ map tops [1..planePartZHeight pp] + + iscale i v = if i /= 0 then scale (fromIntegral i) v else zeroV + + tr :: (Transformable t, V t ~ R2) => Int -> Int -> Int -> t -> t + tr i j k = translate ( iscale i dir_right ^+^ + iscale j dir_left ^+^ + iscale k dir_top ) + + rights h (Partition ps) = mconcat [ tr p i h rightRect | (p,i) <- zip ps [0..] ] + lefts h (Partition ps) = mconcat [ tr j q h leftRect | (j,q) <- zip [0..] (_dualPartition ps) ] + + tops h = mconcat [ tr j i h topRect | (i,ps) <- (zip [0..] pps) , (j,k) <- (zip [0..] ps) , k==h ] + + rightRect = strokeTrail $ glueTrail $ trailFromOffsets [ dir_top , dir_left , ndir_top , ndir_left ] + leftRect = strokeTrail $ glueTrail $ trailFromOffsets [ dir_top , dir_right , ndir_top , ndir_right ] + topRect = strokeTrail $ glueTrail $ trailFromOffsets [ dir_left , dir_right , ndir_left , ndir_right ] + +-------------------------------------------------------------------------------- + +-- | Draws a plane partitions as a tablaeux, with numbers indicating the Z height +drawPlanePartition2D :: (Renderable (Path R2) b, Renderable Text b) => PlanePart -> Diagram b R2 +drawPlanePartition2D = Tableaux.drawTableau . fromPlanePart + +--------------------------------------------------------------------------------
+ Math/Combinat/Diagrams/Tableaux.hs view
@@ -0,0 +1,59 @@+ +-- | Tableau diagrams + +{-# LANGUAGE FlexibleContexts #-} +module Math.Combinat.Diagrams.Tableaux where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Tableaux +import Math.Combinat.Partitions +import Math.Combinat.Diagrams.Partitions + +-- import Data.Monoid +import Data.VectorSpace +import Data.Colour +import Diagrams.Core +import Diagrams.Prelude +import Diagrams.TwoD.Text + +-------------------------------------------------------------------------------- + +-- | Draws a Ferrers diagram with the default settings (English notation, black) +drawTableau :: (Renderable (Path R2) b, Renderable Text b) => Tableau Int -> Diagram b R2 +drawTableau = drawTableau' EnglishNotation black + + +drawTableau' + :: (Renderable (Path R2) b, Renderable Text b) + => PartitionConvention -- ^ orientation + -> Colour Double -- ^ color + -> Tableau Int + -> Diagram b R2 +drawTableau' convention color tableau = numbers <> boxes where + + part = shape tableau + + ps = fromPartition part :: [Int] + n = length ps + + numbers = mconcat [ number j i a | i<-[(0::Int)..n-1], (j,a)<-zip [(0::Int)..] (tableau!!i) ] + # lc color + + number x y a = trafo x y $ scale 0.85 $ text (show a) # lw none # lc color # fc color + + v = 0.22 :: Double + + trafo x y = case convention of + EnglishNotation -> translate (r2 (0.5 + fromIntegral x , - 1 + v - fromIntegral y)) + EnglishNotationCCW -> translate (r2 (0.5 + fromIntegral y , v + fromIntegral x)) + FrenchNotation -> translate (r2 (0.5 + fromIntegral x , v + fromIntegral y)) + + -- numberSize = 0.35 :: Double + -- linewidth = 0.025 :: Double + + boxes = drawPartitionBoxes convention part + +-------------------------------------------------------------------------------- + +
+ Math/Combinat/Diagrams/Trees/Binary.hs view
@@ -0,0 +1,60 @@+ +-- | Binary trees + +{-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-} +module Math.Combinat.Diagrams.Trees.Binary where + +-------------------------------------------------------------------------------- + +import Math.Combinat.Trees.Binary + +import Data.VectorSpace +import Data.Colour hiding ( atop ) +import Diagrams.Core +import Diagrams.Prelude + +-------------------------------------------------------------------------------- + +drawBinTree_ :: forall a b. (Backend b R2, Renderable (Path R2) b ) => BinTree a -> Diagram b R2 +drawBinTree_ = go "." where + + radius = 0.25 + radius1 = 0.15 + + fx = 0.5 + fy = 1 + + linewidth = 0.04 + + go :: String -> BinTree a -> Diagram b R2 + go name t = (centerXY stuff # lwL linewidth) where + stuff = case t of + Leaf _ -> square radius # named name # fc blue + Branch l r -> cherry where + cherry = subdiags # attach name lname # attach name rname + node = circle radius1 # extrudeBottom fy # fc red # named name + subdiags = (centerX node) === (centerX (ldiag ||| rdiag)) + ldiag = alignT (go lname l # extrudeRight fx) + rdiag = alignT (go rname r # extrudeLeft fx) + lname = 'L' : name + rname = 'R' : name + + attach n1 n2 = + withName n1 $ \b1 -> withName n2 $ \b2 -> + (flip atop) ((location b1 ~~ location b2) # lwL linewidth) + + frameX t = extrudeLeft t . extrudeRight t + frameY t = extrudeTop t + +-------------------------------------------------------------------------------- + +{- +padX :: (Backend b R2, Monoid' m) => Double -> QDiagram b R2 m -> QDiagram b R2 m +padX s d = withEnvelope (d # scaleX s) d + +frame :: ( Backend b v, InnerSpace v, OrderedField (Scalar v), Monoid' m) + => Scalar v -> QDiagram b v m -> QDiagram b v m +frame s d = setEnvelope (onEnvelope t (d^.envelope)) d + where + t f = \x -> f x + s +-}
+ Setup.lhs view
@@ -0,0 +1,3 @@+#! /usr/bin/env runhaskell+> import Distribution.Simple+> main = defaultMain
+ combinat-diagrams.cabal view
@@ -0,0 +1,51 @@+Name: combinat-diagrams+Version: 0.1+Synopsis: Graphical representations for various combinatorial objects+Description: Uses the @diagrams@ library to generate graphical + representations of combinatorial objects from + the @combinat@ library+License: BSD3+License-file: LICENSE+Author: Balazs Komuves+Copyright: (c) 2014 Balazs Komuves+Maintainer: bkomuves (plus) hackage (at) gmail (dot) com+Homepage: http://code.haskell.org/~bkomuves/+Stability: Experimental+Category: Math+Tested-With: GHC == 7.8.3+Cabal-Version: >= 1.6+Build-Type: Simple++Flag base4+ Description: Base v4+ +Library++ if flag(base4)+ Build-Depends: base >= 4 && < 5+ cpp-options: -DBASE_VERSION=4+ else + Build-Depends: base >= 3 && < 4+ cpp-options: -DBASE_VERSION=3++ Build-Depends: array, containers, transformers, + colour, vector-space,+ diagrams-core, diagrams-lib,+ combinat >= 0.2.7.0++ Exposed-Modules: Math.Combinat.Diagrams+ Math.Combinat.Diagrams.LatticePaths+ Math.Combinat.Diagrams.Tableaux+ Math.Combinat.Diagrams.Partitions+ Math.Combinat.Diagrams.Partitions.Integer+ Math.Combinat.Diagrams.Partitions.NonCrossing+ Math.Combinat.Diagrams.Partitions.Plane+ Math.Combinat.Diagrams.Trees.Binary++ Extensions: CPP, MultiParamTypeClasses, ScopedTypeVariables, + GeneralizedNewtypeDeriving, BangPatterns ++ Hs-Source-Dirs: .++ ghc-options: -Wall -fno-warn-unused-matches+