Pangraph

See Pangraph for the type which provides a guaranteed well-formed graph once constructed. The rest of the modules provides constructors and getters on this type.

Abstract Types

data Pangraph

The Pangraph type is the core intermediate type between abstract representations of graphs.

Instances

Eq Pangraph

Defined in Pangraph

Methods

(==) :: Pangraph -> Pangraph -> Bool

(/=) :: Pangraph -> Pangraph -> Bool

Show Pangraph

Defined in Pangraph

Methods

showsPrec :: Int -> Pangraph -> ShowS

show :: Pangraph -> String

showList :: [Pangraph] -> ShowS

ToGraph Pangraph

Defined in Pangraph

Associated Types

type ToVertex Pangraph :: *

Methods

toGraph :: Pangraph -> Graph (ToVertex Pangraph)

foldg :: r -> (ToVertex Pangraph -> r) -> (r -> r -> r) -> (r -> r -> r) -> Pangraph -> r

isEmpty :: Pangraph -> Bool

size :: Pangraph -> Int

hasVertex :: ToVertex Pangraph -> Pangraph -> Bool

hasEdge :: ToVertex Pangraph -> ToVertex Pangraph -> Pangraph -> Bool

vertexCount :: Pangraph -> Int

edgeCount :: Pangraph -> Int

vertexList :: Pangraph -> [ToVertex Pangraph]

edgeList :: Pangraph -> [(ToVertex Pangraph, ToVertex Pangraph)]

vertexSet :: Pangraph -> Set (ToVertex Pangraph)

vertexIntSet :: Pangraph -> IntSet

edgeSet :: Pangraph -> Set (ToVertex Pangraph, ToVertex Pangraph)

preSet :: ToVertex Pangraph -> Pangraph -> Set (ToVertex Pangraph)

preIntSet :: Int -> Pangraph -> IntSet

postSet :: ToVertex Pangraph -> Pangraph -> Set (ToVertex Pangraph)

postIntSet :: Int -> Pangraph -> IntSet

adjacencyList :: Pangraph -> [(ToVertex Pangraph, [ToVertex Pangraph])]

adjacencyMap :: Pangraph -> Map (ToVertex Pangraph) (Set (ToVertex Pangraph))

adjacencyIntMap :: Pangraph -> IntMap IntSet

adjacencyMapTranspose :: Pangraph -> Map (ToVertex Pangraph) (Set (ToVertex Pangraph))

adjacencyIntMapTranspose :: Pangraph -> IntMap IntSet

dfsForest :: Pangraph -> Forest (ToVertex Pangraph)

dfsForestFrom :: [ToVertex Pangraph] -> Pangraph -> Forest (ToVertex Pangraph)

dfs :: [ToVertex Pangraph] -> Pangraph -> [ToVertex Pangraph]

reachable :: ToVertex Pangraph -> Pangraph -> [ToVertex Pangraph]

topSort :: Pangraph -> Maybe [ToVertex Pangraph]

isAcyclic :: Pangraph -> Bool

toAdjacencyMap :: Pangraph -> AdjacencyMap (ToVertex Pangraph)

toAdjacencyMapTranspose :: Pangraph -> AdjacencyMap (ToVertex Pangraph)

toAdjacencyIntMap :: Pangraph -> AdjacencyIntMap

toAdjacencyIntMapTranspose :: Pangraph -> AdjacencyIntMap

isDfsForestOf :: Forest (ToVertex Pangraph) -> Pangraph -> Bool

isTopSortOf :: [ToVertex Pangraph] -> Pangraph -> Bool

type ToVertex Pangraph

Defined in Pangraph

type ToVertex Pangraph = VertexID

data Edge

Edges also reqiure [Attribute] and a tuple of Vertex passed as connections to be constructed with makeEdge

Instances

Eq Edge

Defined in Pangraph

Methods

(==) :: Edge -> Edge -> Bool

(/=) :: Edge -> Edge -> Bool

Show Edge

Defined in Pangraph

Methods

showsPrec :: Int -> Edge -> ShowS

show :: Edge -> String

showList :: [Edge] -> ShowS

data Vertex

A Vertex holds [Attribute] and must have a unique VertexID to be constructed with makeVertex.

Instances

Eq Vertex

Defined in Pangraph

Methods

(==) :: Vertex -> Vertex -> Bool

(/=) :: Vertex -> Vertex -> Bool

Show Vertex

Defined in Pangraph

Methods

showsPrec :: Int -> Vertex -> ShowS

show :: Vertex -> String

showList :: [Vertex] -> ShowS

type Attribute = (Key, Value)

The type alias for storage of fields.

type Key = ByteString

The Key in the tuple that makes up Attribute.

type Value = ByteString

The Value in the tuple that makes up Attribute.

type VertexID = ByteString

A field that is Maybe internally is exposed for lookup.

type EdgeID = Int

A type exposed for lookup in the resulting lists.

type MalformedEdge = (Edge, (Maybe VertexID, Maybe VertexID))

Constructors

makePangraph :: [Vertex] -> [Edge] -> Maybe Pangraph

Takes lists of Vertex and Edge to produce 'Just Pangraph' if the graph is correctly formed.

makeEdge :: (VertexID, VertexID) -> [Attribute] -> Edge

Edge constructor

makeVertex :: VertexID -> [Attribute] -> Vertex

Vertex constructor

Pangraph Getters

edgeList :: Pangraph -> [Edge]

Returns the [Edge] from a Pangraph instance

vertexList :: Pangraph -> [Vertex]

Returns the [Vertex] from a Pangraph instance

lookupVertex :: VertexID -> Pangraph -> Maybe Vertex

Lookup of the VertexID in a Pangraph. Complexity: O(log n)

lookupEdge :: EdgeID -> Pangraph -> Maybe Edge

Lookup of the EdgeID in a Pangraph. Complexity: O(log n)

Getters on Vertex and Edge

edgeAttributes :: Edge -> [Attribute]

Returns the [Attribute] of an Edge

vertexAttributes :: Vertex -> [Attribute]

Returns the [Attribute] list of an Edge

edgeEndpoints :: Edge -> (VertexID, VertexID)

Returns the endpoint of tupled Vertex of an Edge

edgeID :: Edge -> Maybe EdgeID

Returns the EdgeID if it has one. Edges are given a new EdgeID when they are passed and retrived from a Pangraph

vertexID :: Vertex -> VertexID

Returns a VertexID