{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DeriveFoldable #-} {-# LANGUAGE DeriveTraversable #-} -------------------------------------------------------------------------------- -- See end of this file for licence information. -------------------------------------------------------------------------------- -- | -- Module : GraphClass -- Copyright : (c) 2003, Graham Klyne, 2009 Vasili I Galchin, -- 2011, 2012 Douglas Burke -- License : GPL V2 -- -- Maintainer : Douglas Burke -- Stability : experimental -- Portability : DeriveFunctor, DeriveFoldable, DeriveTraversable, MultiParamTypeClasses -- -- This module defines a Labelled Directed Graph and Label classes, -- and the Arc datatype. -- -------------------------------------------------------------------------------- ------------------------------------------------------------ -- Define LDGraph, arc and related classes and types ------------------------------------------------------------ module Swish.GraphClass ( LDGraph(..) , Label(..) , Arc(..) , ArcSet , Selector , arc, arcToTriple, arcFromTriple , hasLabel, arcLabels -- , arcNodes , getComponents ) where import Data.Hashable (Hashable(..)) import Data.List (foldl') import Data.Ord (comparing) import qualified Data.Foldable as F import qualified Data.Set as S import qualified Data.Traversable as T -- NOTE: I wanted to declare this as a subclass of Functor, but -- the constraint on the label type seems to prevent that. -- So I've just declared specific instances to be Functors. -- {-| Labelled Directed Graph class. Minimum required implementation: 'emptyGraph', 'setArcs', and 'getArcs'. -} class LDGraph lg lb where -- | Create the empty graph. emptyGraph :: lg lb -- | Replace the existing arcs in the graph. setArcs :: lg lb -> ArcSet lb -> lg lb -- | Extract all the arcs from a graph getArcs :: lg lb -> ArcSet lb -- | Extract those arcs that match the given `Selector`. extract :: (Ord lb) => Selector lb -> lg lb -> lg lb extract sel = update (S.filter sel) -- | Add the two graphs addGraphs :: (Ord lb) => lg lb -> lg lb -> lg lb addGraphs addg = update (S.union (getArcs addg)) -- | Remove those arcs in the first graph from the second -- graph delete :: (Ord lb) => lg lb -- ^ g1 -> lg lb -- ^ g2 -> lg lb -- ^ g2 - g1 -> g3 delete g1 g2 = setArcs g2 (getArcs g2 `S.difference` getArcs g1) -- | Enumerate the distinct labels contained in a graph; -- that is, any label that appears in the subject, -- predicate or object position of an `Arc`. labels :: (Ord lb) => lg lb -> S.Set lb labels = getComponents arcLabels . getArcs -- | Enumerate the distinct nodes contained in a graph; -- that is, any label that appears in the subject -- or object position of an `Arc`. nodes :: (Ord lb) => lg lb -> S.Set lb nodes = getComponents arcNodes . getArcs -- | Update the arcs in a graph using a supplied function. update :: (ArcSet lb -> ArcSet lb) -> lg lb -> lg lb update f g = setArcs g ( f (getArcs g) ) -- | Extract components from a set. getComponents :: (Ord a, Ord b) => (a -> [b]) -> S.Set a -> S.Set b getComponents f = let ins sgr = foldl' (flip S.insert) sgr . f in S.foldl' ins S.empty -- | Label class. -- -- A label may have a fixed binding, which means that the label identifies (is) a -- particular graph node, and different such labels are always distinct nodes. -- Alternatively, a label may be unbound (variable), which means that it is a -- placeholder for an unknown node label. Unbound node labels are used as -- graph-local identifiers for indicating when the same node appears in -- several arcs. -- -- For the purposes of graph-isomorphism testing, fixed labels are matched when they -- are the same. Variable labels may be matched with any other variable label. -- Our definition of isomorphism (for RDF graphs) does not match variable labels -- with fixed labels. -- -- We do not need Ord/Show constraints here, but it means we can just use -- Label as a short-form for Ord/Show in code class (Ord lb, Show lb) => Label lb where -- | Does this node have a variable binding? labelIsVar :: lb -> Bool -- | Calculate the hash of the label using the supplied seed. labelHash :: Int -> lb -> Int -- could provide a default of -- labelHash = hashWithSalt -- but this would then force a Hashable constraint -- | Extract the local id from a variable node. getLocal :: lb -> String -- | Make a label value from a local id. makeLabel :: String -> lb -- | Arc type. -- -- Prior to @0.7.0.0@ you could also use @asubj@, @apred@ and @aobj@ -- to access the elements of the arc. -- data Arc lb = Arc { arcSubj :: lb -- ^ The subject of the arc. , arcPred :: lb -- ^ The predicate (property) of the arc. , arcObj :: lb -- ^ The object of the arc. } deriving (Eq, Functor, F.Foldable, T.Traversable) -- | A set - or graph - of arcs. type ArcSet lb = S.Set (Arc lb) instance (Hashable lb) => Hashable (Arc lb) where hash (Arc s p o) = hash s `hashWithSalt` p `hashWithSalt` o hashWithSalt salt (Arc s p o) = salt `hashWithSalt` s `hashWithSalt` p `hashWithSalt` o -- | Create an arc. arc :: lb -- ^ The subject of the arc. -> lb -- ^ The predicate of the arc. -> lb -- ^ The object of the arc. -> Arc lb arc = Arc -- | Convert an Arc into a tuple. arcToTriple :: Arc lb -> (lb,lb,lb) arcToTriple (Arc s p o) = (s, p, o) -- | Create an Arc from a tuple. arcFromTriple :: (lb,lb,lb) -> Arc lb arcFromTriple (s,p,o) = Arc s p o instance Ord lb => Ord (Arc lb) where compare = comparing arcToTriple instance (Show lb) => Show (Arc lb) where show (Arc lb1 lb2 lb3) = "("++ show lb1 ++","++ show lb2 ++","++ show lb3 ++")" -- | Identify arcs. type Selector lb = Arc lb -> Bool -- | Does the arc contain the label in any position (subject, predicate, or object)? hasLabel :: (Eq lb) => lb -> Arc lb -> Bool hasLabel lbv lb = lbv `elem` arcLabels lb -- | Return all the labels in an arc. arcLabels :: Arc lb -> [lb] arcLabels (Arc lb1 lb2 lb3) = [lb1,lb2,lb3] -- | Return just the subject and object labels in the arc. arcNodes :: Arc lb -> [lb] arcNodes (Arc lb1 _ lb3) = [lb1,lb3] -------------------------------------------------------------------------------- -- -- Copyright (c) 2003, Graham Klyne, 2009 Vasili I Galchin, -- 2011, 2012 Douglas Burke -- All rights reserved. -- -- This file is part of Swish. -- -- Swish is free software; you can redistribute it and/or modify -- it under the terms of the GNU General Public License as published by -- the Free Software Foundation; either version 2 of the License, or -- (at your option) any later version. -- -- Swish is distributed in the hope that it will be useful, -- but WITHOUT ANY WARRANTY; without even the implied warranty of -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -- GNU General Public License for more details. -- -- You should have received a copy of the GNU General Public License -- along with Swish; if not, write to: -- The Free Software Foundation, Inc., -- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -- --------------------------------------------------------------------------------