Data.Graph.Unordered

Known limitations:

• Adding edges might not be the same depending on graph construction (if you add then delete a lot of edges, then the next new edge might be higher than expected).

Graph datatype

data Graph et n nl el

Instances

(Eq (et n), Eq n, Eq nl, Eq el) => Eq (Graph et n nl el)

(ValidGraph et n, Read n, Read nl, Read el) => Read (Graph et n nl el)

(EdgeType et, Show n, Show nl, Show el) => Show (Graph et n nl el)

(NFData n, NFData (et n), NFData nl, NFData el) => NFData (Graph et n nl el)

type DirGraph = Graph DirEdge

type UndirGraph = Graph UndirEdge

type ValidGraph et n = (Hashable n, Eq n, EdgeType et)

Edge types

newtype Edge

Constructors

Edge

Fields

unEdge :: Word

Instances

Bounded Edge

Enum Edge

Eq Edge

Ord Edge

Read Edge

Show Edge

NFData Edge

Hashable Edge

ToContext (n, nl, AdjLookup (at n) el)

FromContext (n, nl, AdjLookup (at n) el)

Contextual (n, nl, AdjLookup (at n) el)

type CNode (n, nl, AdjLookup (at n) el) = n

type CAType (n, nl, AdjLookup (at n) el) = at

type CNLabel (n, nl, AdjLookup (at n) el) = nl

type CELabel (n, nl, AdjLookup (at n) el) = el

data DirEdge n

Constructors

DE

Fields

fromNode :: !n

toNode :: !n

Instances

Functor DirEdge

EdgeType DirEdge

Note that for loops, the result of otherN will always be a ToNode.

EdgeMergeable DirEdge

Eq n => Eq (DirEdge n)

Ord n => Ord (DirEdge n)

Read n => Read (DirEdge n)

Show n => Show (DirEdge n)

Generic (DirEdge n)

NFData n => NFData (DirEdge n)

type AdjType DirEdge = DirAdj

type Rep (DirEdge n)

newtype UndirEdge n

Constructors

UE

Fields

ueElem :: [n]

Instances

Functor UndirEdge

EdgeType UndirEdge

EdgeMergeable UndirEdge

Eq n => Eq (UndirEdge n)

Ord n => Ord (UndirEdge n)

Read n => Read (UndirEdge n)

Show n => Show (UndirEdge n)

Generic (UndirEdge n)

NFData n => NFData (UndirEdge n)

type AdjType UndirEdge = Identity

type Rep (UndirEdge n)

class (Functor et, NodeFrom (AdjType et)) => EdgeType et where

Associated Types

type AdjType et :: * -> *

Methods

mkEdge :: n -> n -> et n

otherN :: Eq n => n -> et n -> AdjType et n

Assumes n is one of the end points of this edge.

toEdge :: n -> AdjType et n -> et n

edgeNodes :: et n -> [n]

Returns a list of length 2.

edgeTriple :: (et n, el) -> (n, n, el)

Instances

EdgeType UndirEdge

EdgeType DirEdge

Note that for loops, the result of otherN will always be a ToNode.

class NodeFrom at where

Methods

getNode :: at n -> n

Instances

NodeFrom Identity

NodeFrom DirAdj

data DirAdj n

Constructors

ToNode n

FromNode n

Instances

NodeFrom DirAdj

Eq n => Eq (DirAdj n)

Ord n => Ord (DirAdj n)

Read n => Read (DirAdj n)

Show n => Show (DirAdj n)

Generic (DirAdj n)

NFData n => NFData (DirAdj n)

type Rep (DirAdj n)

newtype Identity a :: * -> *

Identity functor and monad. (a non-strict monad)

Since: 4.8.0.0

Constructors

Identity

Fields

runIdentity :: a

Instances

Monad Identity

Functor Identity

MonadFix Identity

Applicative Identity

Foldable Identity

Traversable Identity

Generic1 Identity

MonadZip Identity

NodeFrom Identity

Eq a => Eq (Identity a)

Data a => Data (Identity a)

Ord a => Ord (Identity a)

Read a => Read (Identity a)

This instance would be equivalent to the derived instances of the Identity newtype if the runIdentity field were removed

Show a => Show (Identity a)

This instance would be equivalent to the derived instances of the Identity newtype if the runIdentity field were removed

Generic (Identity a)

NFData a => NFData (Identity a)

Since: 1.4.0.0

type Rep1 Identity = D1 D1Identity (C1 C1_0Identity (S1 S1_0_0Identity Par1))

type Rep (Identity a) = D1 D1Identity (C1 C1_0Identity (S1 S1_0_0Identity (Rec0 a)))

Graph Context

data Context at n nl el

Constructors

Ctxt

Fields

cNode :: !n

cLabel :: !nl

cAdj :: !(AdjLookup (at n) el)

Instances

(Eq n, Eq nl, Eq el, Eq (at n)) => Eq (Context at n nl el)

(Read n, Read nl, Read el, Read (at n)) => Read (Context at n nl el)

(Show n, Show nl, Show el, Show (at n)) => Show (Context at n nl el)

Generic (Context at n nl el)

(NFData n, NFData nl, NFData el, NFData (at n)) => NFData (Context at n nl el)

ToContext (Context at n nl el)

FromContext (Context at n nl el)

Contextual (Context at n nl el)

type Rep (Context at n nl el)

type CNode (Context at n nl el) = n

type CAType (Context at n nl el) = at

type CNLabel (Context at n nl el) = nl

type CELabel (Context at n nl el) = el

type AdjLookup n el = HashMap Edge (n, el)

class Contextual ctxt

Associated Types

type CNode ctxt :: *

type CAType ctxt :: * -> *

type CNLabel ctxt :: *

type CELabel ctxt :: *

Instances

Contextual (n, nl, [(n, [el])])

Contextual (n, nl, AdjLookup (at n) el)

Contextual (Context at n nl el)

type ValidContext et n nl el ctxt = (Contextual ctxt, n ~ CNode ctxt, AdjType et ~ CAType ctxt, nl ~ CNLabel ctxt, el ~ CELabel ctxt)

class Contextual ctxt => FromContext ctxt where

Methods

fromContext :: Context (CAType ctxt) (CNode ctxt) (CNLabel ctxt) (CELabel ctxt) -> ctxt

Instances

Ord n => FromContext (n, nl, [(n, [el])])

FromContext (n, nl, AdjLookup (at n) el)

FromContext (Context at n nl el)

class Contextual ctxt => ToContext ctxt where

Methods

toContext :: ctxt -> Context (CAType ctxt) (CNode ctxt) (CNLabel ctxt) (CELabel ctxt)

Instances

ToContext (n, nl, AdjLookup (at n) el)

ToContext (Context at n nl el)

Graph functions

Graph Information

isEmpty :: Graph et n nl el -> Bool

Node information

order :: Graph et n nl el -> Int

Number of nodes

hasNode :: ValidGraph et n => Graph et n nl el -> n -> Bool

ninfo :: ValidGraph et n => Graph et n nl el -> n -> Maybe ([Edge], nl)

nodes :: Graph et n nl el -> [n]

nodeDetails :: Graph et n nl el -> [(n, ([Edge], nl))]

lnodes :: Graph et n nl el -> [(n, nl)]

nlab :: ValidGraph et n => Graph et n nl el -> n -> Maybe nl

neighbours :: ValidGraph et n => Graph et n nl el -> n -> [n]

Edge information

size :: Graph et n nl el -> Int

Number of edges

hasEdge :: ValidGraph et n => Graph et n nl el -> Edge -> Bool

einfo :: ValidGraph et n => Graph et n nl el -> Edge -> Maybe (et n, el)

edges :: Graph et n nl el -> [Edge]

edgeDetails :: Graph et n nl el -> [(Edge, (et n, el))]

ledges :: Graph et n nl el -> [(Edge, el)]

elab :: ValidGraph et n => Graph et n nl el -> Edge -> Maybe el

edgePairs :: EdgeType et => Graph et n nl el -> [(n, n)]

ledgePairs :: EdgeType et => Graph et n nl el -> [(n, n, el)]

Graph construction

empty :: Graph et n nl el

mkGraph :: ValidGraph et n => [(n, nl)] -> [(n, n, el)] -> Graph et n nl el

Assumes all nodes are in the node list.

buildGr :: ValidGraph et n => [Context (AdjType et) n nl el] -> Graph et n nl el

Assumes the Contexts describe a graph in total, with the outermost one first (i.e. buildGr (c:cs) == c merge buildGr cs).

insNode :: ValidGraph et n => n -> nl -> Graph et n nl el -> Graph et n nl el

insEdge :: ValidGraph et n => (n, n, el) -> Graph et n nl el -> (Edge, Graph et n nl el)

Merging

type Mergeable et n nl el ctxt = (ValidGraph et n, ToContext ctxt, ValidContext et n nl el ctxt)

merge :: ValidGraph et n => Context (AdjType et) n nl el -> Graph et n nl el -> Graph et n nl el

mergeAs :: Mergeable et n nl el ctxt => ctxt -> Graph et n nl el -> Graph et n nl el

Graph deconstruction

delNode :: ValidGraph et n => n -> Graph et n nl el -> Graph et n nl el

delEdge :: ValidGraph et n => Edge -> Graph et n nl el -> Graph et n nl el

delEdgeLabel :: (ValidGraph et n, Eq el) => (n, n, el) -> Graph et n nl el -> Graph et n nl el

delEdgesBetween :: ValidGraph et n => n -> n -> Graph et n nl el -> Graph et n nl el

Matching

type Matchable et n nl el ctxt = (ValidGraph et n, FromContext ctxt, ValidContext et n nl el ctxt)

match :: ValidGraph et n => n -> Graph et n nl el -> Maybe (Context (AdjType et) n nl el, Graph et n nl el)

Note that for any loops, the resultant edge will only appear once in the output cAdj field.

matchAs :: Matchable et n nl el ctxt => n -> Graph et n nl el -> Maybe (ctxt, Graph et n nl el)

matchAny :: ValidGraph et n => Graph et n nl el -> Maybe (Context (AdjType et) n nl el, Graph et n nl el)

matchAnyAs :: Matchable et n nl el ctxt => Graph et n nl el -> Maybe (ctxt, Graph et n nl el)

Manipulation

nmap :: ValidGraph et n => (nl -> nl') -> Graph et n nl el -> Graph et n nl' el

nmapFor :: ValidGraph et n => (nl -> nl) -> Graph et n nl el -> n -> Graph et n nl el

emap :: ValidGraph et n => (el -> el') -> Graph et n nl el -> Graph et n nl el'

emapFor :: ValidGraph et n => (el -> el) -> Graph et n nl el -> Edge -> Graph et n nl el