Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.Libgraph

Synopsis

Documentation

data Graph vertex arc Source

Constructors

Graph
Fields root :: vertex vertices :: [vertex] arcs :: [Arc vertex arc]

data Arc vertex arc Source

Constructors

Arc
Fields source :: vertex target :: vertex arc :: arc

Instances

(Eq vertex, Eq arc) => Eq (Arc vertex arc)
(Show vertex, Show arc) => Show (Arc vertex arc)

(-->) :: vertex -> vertex -> SimpleArc vertex Source

Create an arc between two vertices.

succs :: Eq vertex => Graph vertex arc -> vertex -> [vertex] Source

Direct successors of a vertex.

preds :: Eq vertex => Graph vertex arc -> vertex -> [vertex] Source

Direct predecessors of a vertex.

isSucc :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool Source

Is first vertex a successor of second?

isPred :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool Source

Is first vertex a predecessor of second?

mapGraph :: (a -> b) -> Graph a c -> Graph b c Source

mapArcs :: (a -> b) -> Graph c a -> Graph c b Source

data Dfs vertex arc Source

Instances

(Eq vertex, Show vertex) => Show (Dfs vertex arc)

data EdgeType Source

Constructors

TreeEdge
BackEdge
FwdEdge
CrossEdge

Instances

Eq EdgeType
Show EdgeType

getDfs :: Eq vertex => Graph vertex arc -> Dfs vertex arc Source

Walk graph in depth-first order and number the vertices.

getEdgetype :: (Eq vertex, Show vertex) => Dfs vertex arc -> Arc vertex arc -> EdgeType Source

The EdgeType of an Arc.

getPreorder :: Dfs vertex arc -> [vertex] Source

Get list of vertices in the order they were visited by the depth-first search.

getPostorder :: Dfs vertex arc -> [vertex] Source

Get list of vertices in the order they were last visited by the depth-first search.

isAncestor :: (Eq vertex, Show vertex) => Dfs vertex arc -> vertex -> vertex -> Maybe Bool Source

Is first vertex a (recursive) parent of second vertex? May fail when one of the vertices is unreachable from the root.

data Domsets vertex arc Source

Instances

(Eq vertex, Show vertex) => Show (Domsets vertex arc)

getDomsets :: Eq vertex => Graph vertex arc -> Domsets vertex arc Source

Compute dominator sets. N.B. currently a naive algorithm is implemented with time-complexity O(vertex^2).

getDominators :: Eq vertex => vertex -> Domsets vertex arc -> [vertex] Source

Vertices dominating the vertex given as argument.

data CycleTree vertex Source

Constructors

CycleTree vertex [CycleTree vertex]
Reducible vertex [CycleTree vertex]
Irreducible [CycleTree vertex]

Instances

Show vertex => Show (CycleTree vertex)

getCycles :: Ord vertex => CycleNest vertex -> CycleTree vertex Source

getRedHeaders :: CycleNest vertex -> [vertex] Source

Entry vertices of reducible cycles.

dagify :: (Ord v, Eq a, Show v) => ([v] -> v) -> Graph v a -> Graph v a Source

findFaulty :: (Ord v, Eq a, Show v) => (v -> Judgement) -> ([v] -> v) -> Graph v a -> [v] Source

findFaulty_dag :: (Ord v, Eq a, Show v) => (v -> Judgement) -> Graph v a -> [v] Source

data Judgement Source

Constructors

Right
Wrong
Unassessed

Instances

Eq Judgement
Ord Judgement
Show Judgement

showWith :: Eq vertex => Graph vertex arc -> (vertex -> (String, String)) -> (Arc vertex arc -> String) -> String Source

Convert Graph to String with functions to show vertices and arcs.

escape :: String -> String Source

display :: (Graph vertex arc -> String) -> Graph vertex arc -> IO () Source

Invoke Graphviz and Imagemagick to display graph on screen.

collapse :: (Show v, Ord v, Eq a) => ([v] -> v) -> Graph v a -> Graph v a Source

remove :: (Ord v, Show v) => Graph v a -> Graph v a Source

treeDepth :: Ord v => Graph v a -> Int Source