Copyright	(c) Martin Erwig Christian Maeder and Uni Bremen 1999-2006
License	GPLv2 or higher, see LICENSE.txt
Maintainer	Christian.Maeder@dfki.de
Stability	provisional
Portability	portable
Safe Haskell	Safe

Common.Lib.Graph

Description

Tree-based implementation of Graph and DynGraph using Data.IntMap instead of Data.Graph.Inductive.Internal.FiniteMap

Synopsis

newtype Gr a b = Gr {
- convertToMap :: IntMap (GrContext a b)
}
data GrContext a b = GrContext {
- nodeLabel :: a
- nodeSuccs :: IntMap [b]
- loops :: [b]
- nodePreds :: IntMap [b]
}
unsafeConstructGr :: IntMap (GrContext a b) -> Gr a b
decomposeGr :: Node -> Gr a b -> Maybe (GrContext a b, Gr a b)
getPaths :: Node -> Gr a b -> [[LEdge b]]
getAllPathsTo :: Node -> Gr a b -> [[LEdge b]]
getPathsTo :: Node -> Node -> Gr a b -> [[LEdge b]]
getLEdges :: Node -> Node -> Gr a b -> [b]
delLEdge :: (b -> b -> Ordering) -> LEdge b -> Gr a b -> Gr a b
insLEdge :: Bool -> (b -> b -> Ordering) -> LEdge b -> Gr a b -> (Gr a b, Bool)
delLNode :: (a -> a -> Bool) -> LNode a -> Gr a b -> Gr a b
labelNode :: LNode a -> Gr a b -> (Gr a b, a)
getNewNode :: Gr a b -> Node
rmIsolated :: Gr a b -> Gr a b

Documentation

newtype Gr a b Source #

the graph type constructor

Constructors

Gr
Fields convertToMap :: IntMap (GrContext a b)

Instances

Instances details

DynGraph Gr Source #
Instance details Defined in Common.Lib.Graph Methods (&) :: Context a b -> Gr a b -> Gr a b
Graph Gr Source #
Instance details Defined in Common.Lib.Graph Methods empty :: Gr a b isEmpty :: Gr a b -> Bool match :: Node -> Gr a b -> Decomp Gr a b mkGraph :: [LNode a] -> [LEdge b] -> Gr a b labNodes :: Gr a b -> [LNode a] matchAny :: Gr a b -> GDecomp Gr a b noNodes :: Gr a b -> Int nodeRange :: Gr a b -> (Node, Node) labEdges :: Gr a b -> [LEdge b]
(Data a, Data b) => Data (Gr a b) Source #
Instance details Defined in Common.Lib.Graph Methods gfoldl :: (forall d b0. Data d => c (d -> b0) -> d -> c b0) -> (forall g. g -> c g) -> Gr a b -> c (Gr a b) gunfold :: (forall b0 r. Data b0 => c (b0 -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Gr a b) toConstr :: Gr a b -> Constr dataTypeOf :: Gr a b -> DataType dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Gr a b)) dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Gr a b)) gmapT :: (forall b0. Data b0 => b0 -> b0) -> Gr a b -> Gr a b gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Gr a b -> r gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Gr a b -> r gmapQ :: (forall d. Data d => d -> u) -> Gr a b -> [u] gmapQi :: Int -> (forall d. Data d => d -> u) -> Gr a b -> u gmapM :: Monad m => (forall d. Data d => d -> m d) -> Gr a b -> m (Gr a b) gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Gr a b -> m (Gr a b) gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Gr a b -> m (Gr a b)
(Show a, Show b) => Show (Gr a b) Source #
Instance details Defined in Common.Lib.Graph Methods showsPrec :: Int -> Gr a b -> ShowS show :: Gr a b -> String showList :: [Gr a b] -> ShowS
Generic (Gr a b)
Instance details Defined in ATC.Graph Associated Types type Rep (Gr a b) :: Type -> Type Methods from :: Gr a b -> Rep (Gr a b) x to :: Rep (Gr a b) x -> Gr a b
(FromJSON a, FromJSON b) => FromJSON (Gr a b)
Instance details Defined in ATC.Graph Methods parseJSON :: Value -> Parser (Gr a b) parseJSONList :: Value -> Parser [Gr a b]
(ToJSON a, ToJSON b) => ToJSON (Gr a b)
Instance details Defined in ATC.Graph Methods toJSON :: Gr a b -> Value toEncoding :: Gr a b -> Encoding toJSONList :: [Gr a b] -> Value toEncodingList :: [Gr a b] -> Encoding
(ShATermConvertible a, ShATermConvertible b) => ShATermConvertible (Gr a b)
Instance details Defined in ATC.Graph Methods toShATermAux :: ATermTable -> Gr a b -> IO (ATermTable, Int) toShATermList' :: ATermTable -> [Gr a b] -> IO (ATermTable, Int) fromShATermAux :: Int -> ATermTable -> (ATermTable, Gr a b) fromShATermList' :: Int -> ATermTable -> (ATermTable, [Gr a b])
(Pretty a, Pretty b) => Pretty (Gr a (Int, b)) Source #
Instance details Defined in CASL.Amalgamability Methods pretty :: Gr a (Int, b) -> Doc Source # pretties :: [Gr a (Int, b)] -> Doc Source #
(ShATermLG a, ShATermLG b) => ShATermLG (Gr a b) Source #
Instance details Defined in ATC.Grothendieck Methods toShATermLG :: ATermTable -> Gr a b -> IO (ATermTable, Int) Source # fromShATermLG :: LogicGraph -> Int -> ATermTable -> (ATermTable, Gr a b) Source #
type Rep (Gr a b)
Instance details Defined in ATC.Graph type Rep (Gr a b) = D1 ('MetaData "Gr" "Common.Lib.Graph" "main" 'True) (C1 ('MetaCons "Gr" 'PrefixI 'True) (S1 ('MetaSel ('Just "convertToMap") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (IntMap (GrContext a b)))))

data GrContext a b Source #

Constructors

GrContext
Fields nodeLabel :: a nodeSuccs :: IntMap [b] loops :: [b] nodePreds :: IntMap [b]

Instances

Instances details

(Data a, Data b) => Data (GrContext a b) Source #
Instance details Defined in Common.Lib.Graph Methods gfoldl :: (forall d b0. Data d => c (d -> b0) -> d -> c b0) -> (forall g. g -> c g) -> GrContext a b -> c (GrContext a b) gunfold :: (forall b0 r. Data b0 => c (b0 -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (GrContext a b) toConstr :: GrContext a b -> Constr dataTypeOf :: GrContext a b -> DataType dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (GrContext a b)) dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (GrContext a b)) gmapT :: (forall b0. Data b0 => b0 -> b0) -> GrContext a b -> GrContext a b gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> GrContext a b -> r gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> GrContext a b -> r gmapQ :: (forall d. Data d => d -> u) -> GrContext a b -> [u] gmapQi :: Int -> (forall d. Data d => d -> u) -> GrContext a b -> u gmapM :: Monad m => (forall d. Data d => d -> m d) -> GrContext a b -> m (GrContext a b) gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> GrContext a b -> m (GrContext a b) gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> GrContext a b -> m (GrContext a b)
Generic (GrContext a b)
Instance details Defined in ATC.Graph Associated Types type Rep (GrContext a b) :: Type -> Type Methods from :: GrContext a b -> Rep (GrContext a b) x to :: Rep (GrContext a b) x -> GrContext a b
(FromJSON a, FromJSON b) => FromJSON (GrContext a b)
Instance details Defined in ATC.Graph Methods parseJSON :: Value -> Parser (GrContext a b) parseJSONList :: Value -> Parser [GrContext a b]
(ToJSON a, ToJSON b) => ToJSON (GrContext a b)
Instance details Defined in ATC.Graph Methods toJSON :: GrContext a b -> Value toEncoding :: GrContext a b -> Encoding toJSONList :: [GrContext a b] -> Value toEncodingList :: [GrContext a b] -> Encoding
(ShATermConvertible a, ShATermConvertible b) => ShATermConvertible (GrContext a b)
Instance details Defined in ATC.Graph Methods toShATermAux :: ATermTable -> GrContext a b -> IO (ATermTable, Int) toShATermList' :: ATermTable -> [GrContext a b] -> IO (ATermTable, Int) fromShATermAux :: Int -> ATermTable -> (ATermTable, GrContext a b) fromShATermList' :: Int -> ATermTable -> (ATermTable, [GrContext a b])
(ShATermLG a, ShATermLG b) => ShATermLG (GrContext a b) Source #
Instance details Defined in ATC.Grothendieck Methods toShATermLG :: ATermTable -> GrContext a b -> IO (ATermTable, Int) Source # fromShATermLG :: LogicGraph -> Int -> ATermTable -> (ATermTable, GrContext a b) Source #
type Rep (GrContext a b)
Instance details Defined in ATC.Graph type Rep (GrContext a b) = D1 ('MetaData "GrContext" "Common.Lib.Graph" "main" 'False) (C1 ('MetaCons "GrContext" 'PrefixI 'True) ((S1 ('MetaSel ('Just "nodeLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :: S1 ('MetaSel ('Just "nodeSuccs") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (IntMap [b]))) :: (S1 ('MetaSel ('Just "loops") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [b]) :*: S1 ('MetaSel ('Just "nodePreds") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (IntMap [b])))))

unsafeConstructGr :: IntMap (GrContext a b) -> Gr a b Source #

decomposeGr :: Node -> Gr a b -> Maybe (GrContext a b, Gr a b) Source #

getPaths :: Node -> Gr a b -> [[LEdge b]] Source #

compute the possible cycle free paths from a start node

getAllPathsTo :: Node -> Gr a b -> [[LEdge b]] Source #

compute the possible cycle free reversed paths from a start node

getPathsTo :: Node -> Node -> Gr a b -> [[LEdge b]] Source #

compute the possible cycle free paths from a start node to a target node.

getLEdges :: Node -> Node -> Gr a b -> [b] Source #

get all the edge labels between two nodes

delLEdge :: (b -> b -> Ordering) -> LEdge b -> Gr a b -> Gr a b Source #

delete a labeled edge from a graph

insLEdge :: Bool -> (b -> b -> Ordering) -> LEdge b -> Gr a b -> (Gr a b, Bool) Source #

insert a labeled edge into a graph, returns False if edge exists

delLNode :: (a -> a -> Bool) -> LNode a -> Gr a b -> Gr a b Source #

delete a labeled node

labelNode :: LNode a -> Gr a b -> (Gr a b, a) Source #

sets the node with new label and returns the new graph and the old label

getNewNode :: Gr a b -> Node Source #

returns one new node id for the given graph

rmIsolated :: Gr a b -> Gr a b Source #

remove isolated nodes without edges