HGraph.Directed

Documentation

class DirectedGraph t where

Minimal complete definition

empty, vertices, arcs, linearizeVertices, isVertex

Methods

empty :: t a -> t a

vertices :: t a -> [a]

numVertices :: Integral b => t a -> b

arcs :: t a -> [(a, a)]

numArcs :: Integral b => t a -> b

linearizeVertices :: t a -> (t Int, [(Int, a)])

isVertex :: t a -> a -> Bool

Instances

DirectedGraph Digraph

Defined in HGraph.Directed.AdjacencyMap

Methods

empty :: Digraph a -> Digraph a

vertices :: Digraph a -> [a]

numVertices :: Integral b => Digraph a -> b

arcs :: Digraph a -> [(a, a)]

numArcs :: Integral b => Digraph a -> b

linearizeVertices :: Digraph a -> (Digraph Int, [(Int, a)])

isVertex :: Digraph a -> a -> Bool

class Adjacency t where

Minimal complete definition

outneighbors, inneighbors, arcExists

Methods

outneighbors :: t a -> a -> [a]

inneighbors :: t a -> a -> [a]

outdegree :: Integral b => t a -> a -> b

indegree :: Integral b => t a -> a -> b

incomingArcs :: t a -> a -> [(a, a)]

outgoingArcs :: t a -> a -> [(a, a)]

arcExists :: t a -> (a, a) -> Bool

metaBfs :: Ord a => t a -> a -> ([a] -> [a]) -> ([a] -> [a]) -> [a]

Instances

Adjacency Digraph

Defined in HGraph.Directed.AdjacencyMap

Methods

outneighbors :: Digraph a -> a -> [a]

inneighbors :: Digraph a -> a -> [a]

outdegree :: Integral b => Digraph a -> a -> b

indegree :: Integral b => Digraph a -> a -> b

incomingArcs :: Digraph a -> a -> [(a, a)]

outgoingArcs :: Digraph a -> a -> [(a, a)]

arcExists :: Digraph a -> (a, a) -> Bool

metaBfs :: Ord a => Digraph a -> a -> ([a] -> [a]) -> ([a] -> [a]) -> [a]

class Mutable t where

Methods

addVertex :: a -> t a -> t a

removeVertex :: a -> t a -> t a

addArc :: (a, a) -> t a -> t a

removeArc :: (a, a) -> t a -> t a

Instances

Mutable Digraph

Defined in HGraph.Directed.AdjacencyMap

Methods

addVertex :: a -> Digraph a -> Digraph a

removeVertex :: a -> Digraph a -> Digraph a

addArc :: (a, a) -> Digraph a -> Digraph a

removeArc :: (a, a) -> Digraph a -> Digraph a

subgraphAround :: (DirectedGraph t, Adjacency t, Mutable t) => Int -> t a -> a -> t a

renameVertices :: (DirectedGraph t, Mutable t, Ord a) => Map a b -> t b -> t a -> t b

topologicalOrdering :: (DirectedGraph t, Mutable t, Adjacency t, Ord a) => t a -> Maybe [a]

inducedSubgraph :: (Mutable t, DirectedGraph t, Ord a) => t a -> Set a -> t a

lineDigraphI :: (DirectedGraph t, Adjacency t, Mutable t) => t Int -> (t Int, [(Int, (Int, Int))])

The line digraph of a digraph d is the digraph `(V', A')`, where V' is the set of arcs of d there is an arc (a,b) if the head of b in d is the same as the tail of a in d.

transitiveClosure :: (Mutable t, DirectedGraph t, Adjacency t, Ord t) => t t -> t t

isIsomorphicTo :: (Adjacency t, Adjacency t, DirectedGraph t, DirectedGraph t) => t a -> t a -> Bool

Find an isomorphism from d0 to d1, if it exists.

isIsomorphicToI :: forall {t} {t} {a} {k}. (Adjacency t, Adjacency t, DirectedGraph t, DirectedGraph t, Ord k, Ord a) => t k -> t a -> Bool

splitVertices :: (Mutable t, DirectedGraph t, Num a) => t a -> t a

Split each vertex v of the digraph into two vertices v_in and v_out. All incoming arcs of v become incoming arcs of v_in, all outgoing arcs from v become outgoing arcs from v_out and there is an arc `(v_in, v_out)`.

This operation is useful when obtaining a vertex variant of arc-based algorithms like maximum flow.

union :: (Mutable t, DirectedGraph t) => t a -> t a -> t a