Graph.Inductive

Graph

data Gr a b

Instances

Bifunctor Gr

Defined in Data.Graph.Inductive.PatriciaTree

Methods

bimap :: (a -> b) -> (c -> d) -> Gr a c -> Gr b d

first :: (a -> b) -> Gr a c -> Gr b c

second :: (b -> c) -> Gr a b -> Gr a c

Graph Gr

Defined in Data.Graph.Inductive.PatriciaTree

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]

DynGraph Gr

Defined in Data.Graph.Inductive.PatriciaTree

Methods

(&) :: Context a b -> Gr a b -> Gr a b

(Eq a, Ord b) => Eq (Gr a b)

Defined in Data.Graph.Inductive.PatriciaTree

Methods

(==) :: Gr a b -> Gr a b -> Bool

(/=) :: Gr a b -> Gr a b -> Bool

(Read a, Read b) => Read (Gr a b)

Defined in Data.Graph.Inductive.PatriciaTree

Methods

readsPrec :: Int -> ReadS (Gr a b)

readList :: ReadS [Gr a b]

readPrec :: ReadPrec (Gr a b)

readListPrec :: ReadPrec [Gr a b]

(Show a, Show b) => Show (Gr a b)

Defined in Data.Graph.Inductive.PatriciaTree

Methods

showsPrec :: Int -> Gr a b -> ShowS

show :: Gr a b -> String

showList :: [Gr a b] -> ShowS

Generic (Gr a b)

Defined in Data.Graph.Inductive.PatriciaTree

Associated Types

type Rep (Gr a b) :: * -> *

Methods

from :: Gr a b -> Rep (Gr a b) x

to :: Rep (Gr a b) x -> Gr a b

(NFData a, NFData b) => NFData (Gr a b)

Defined in Data.Graph.Inductive.PatriciaTree

Methods

rnf :: Gr a b -> ()

type Rep (Gr a b)

Defined in Data.Graph.Inductive.PatriciaTree

type Rep (Gr a b) = D1 (MetaData "Gr" "Data.Graph.Inductive.PatriciaTree" "fgl-5.6.0.0-IGmeQfkpQmd48thU3Ee01i" True) (C1 (MetaCons "Gr" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (GraphRep a b))))

type UGr = Gr () ()

Static graphs

class Graph (gr :: * -> * -> *) where

Minimum implementation: empty, isEmpty, match, mkGraph, labNodes

Minimal complete definition

empty, isEmpty, match, mkGraph, labNodes

Methods

empty :: gr a b

An empty Graph.

isEmpty :: gr a b -> Bool

True if the given Graph is empty.

match :: Node -> gr a b -> Decomp gr a b

Decompose a Graph into the MContext found for the given node and the remaining Graph.

mkGraph :: [LNode a] -> [LEdge b] -> gr a b

Create a Graph from the list of LNodes and LEdges.

For graphs that are also instances of DynGraph, mkGraph ns es should be equivalent to (insEdges es . insNodes ns) empty.

labNodes :: gr a b -> [LNode a]

A list of all LNodes in the Graph.

matchAny :: gr a b -> GDecomp gr a b

Decompose a graph into the Context for an arbitrarily-chosen Node and the remaining Graph.

noNodes :: gr a b -> Int

The number of Nodes in a Graph.

nodeRange :: gr a b -> (Node, Node)

The minimum and maximum Node in a Graph.

labEdges :: gr a b -> [LEdge b]

A list of all LEdges in the Graph.

Instances

Graph Gr

Defined in Data.Graph.Inductive.PatriciaTree

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]

mkUGraph :: Graph gr => [Node] -> [Edge] -> gr () ()

Build a quasi-unlabeled Graph.

order :: Graph gr => gr a b -> Int

The number of nodes in the graph. An alias for noNodes.

size :: Graph gr => gr a b -> Int

The number of edges in the graph.

Note that this counts every edge found, so if you are representing an unordered graph by having each edge mirrored this will be incorrect.

If you created an unordered graph by either mirroring every edge (including loops!) or using the undir function in Data.Graph.Inductive.Basic then you can safely halve the value returned by this.

nodes :: Graph gr => gr a b -> [Node]

List all Nodes in the Graph.

edges :: Graph gr => gr a b -> [Edge]

List all Edges in the Graph.

context :: Graph gr => gr a b -> Node -> Context a b

Find the context for the given Node. Causes an error if the Node is not present in the Graph.

lab :: Graph gr => gr a b -> Node -> Maybe a

Find the label for a Node.

neighbors :: Graph gr => gr a b -> Node -> [Node]

Find the neighbors for a Node.

lneighbors :: Graph gr => gr a b -> Node -> Adj b

Find the labelled links coming into or going from a Context.

suc :: Graph gr => gr a b -> Node -> [Node]

Find all Nodes that have a link from the given Node.

pre :: Graph gr => gr a b -> Node -> [Node]

Find all Nodes that link to to the given Node.

lsuc :: Graph gr => gr a b -> Node -> [(Node, b)]

Find all Nodes that are linked from the given Node and the label of each link.

lpre :: Graph gr => gr a b -> Node -> [(Node, b)]

Find all Nodes that link to the given Node and the label of each link.

out :: Graph gr => gr a b -> Node -> [LEdge b]

Find all outward-bound LEdges for the given Node.

inn :: Graph gr => gr a b -> Node -> [LEdge b]

Find all inward-bound LEdges for the given Node.

outdeg :: Graph gr => gr a b -> Node -> Int

The outward-bound degree of the Node.

indeg :: Graph gr => gr a b -> Node -> Int

The inward-bound degree of the Node.

deg :: Graph gr => gr a b -> Node -> Int

The degree of the Node.

hasNeighbor :: Graph gr => gr a b -> Node -> Node -> Bool

Checks if there is an undirected edge between two nodes.

hasNeighborAdj :: (Graph gr, Eq b) => gr a b -> Node -> (b, Node) -> Bool

Checks if there is an undirected labelled edge between two nodes.

hasEdge :: Graph gr => gr a b -> Edge -> Bool

Checks if there is a directed edge between two nodes.

hasLEdge :: (Graph gr, Eq b) => gr a b -> LEdge b -> Bool

Checks if there is a labelled edge between two nodes.

equal :: (Eq a, Eq b, Graph gr) => gr a b -> gr a b -> Bool

gelem :: Graph gr => Node -> gr a b -> Bool

True if the Node is present in the Graph.

gsel :: Graph gr => (Context a b -> Bool) -> gr a b -> [Context a b]

Return all Contexts for which the given function returns True.

gfold

Arguments

:: Graph gr

=> (Context a b -> [Node])

direction of fold

-> (Context a b -> c -> d)

depth aggregation

-> (Maybe d -> c -> c, c)

breadth/level aggregation

-> [Node]

-> gr a b

-> c

Directed graph fold.

ufold :: Graph gr => (Context a b -> c -> c) -> c -> gr a b -> c

Fold a function over the graph by recursively calling match.

hasLoop :: Graph gr => gr a b -> Bool

True if the graph has any edges of the form (A, A).

isSimple :: Graph gr => gr a b -> Bool

The inverse of hasLoop.

newNodes :: Graph gr => Int -> gr a b -> [Node]

List N available Nodes, i.e. Nodes that are not used in the Graph.

Articulation points

ap :: Graph gr => gr a b -> [Node]

Finds the articulation points for a connected undirected graph, by using the low numbers criteria:

a) The root node is an articulation point iff it has two or more children.

b) An non-root node v is an articulation point iff there exists at least one child w of v such that lowNumber(w) >= dfsNumber(v).

Breadth-first search

bfs :: Graph gr => Node -> gr a b -> [Node]

bfsn :: Graph gr => [Node] -> gr a b -> [Node]

bfsWith :: Graph gr => (Context a b -> c) -> Node -> gr a b -> [c]

bfsnWith :: Graph gr => (Context a b -> c) -> [Node] -> gr a b -> [c]

level :: Graph gr => Node -> gr a b -> [(Node, Int)]

leveln :: Graph gr => [(Node, Int)] -> gr a b -> [(Node, Int)]

bfe :: Graph gr => Node -> gr a b -> [Edge]

bfen :: Graph gr => [Edge] -> gr a b -> [Edge]

bft :: Graph gr => Node -> gr a b -> RTree

lbft :: Graph gr => Node -> gr a b -> LRTree b

esp :: Graph gr => Node -> Node -> gr a b -> Path

lesp :: Graph gr => Node -> Node -> gr a b -> LPath b

Depth-first search

type CFun a b c = Context a b -> c

dfs :: Graph gr => [Node] -> gr a b -> [Node]

Depth-first search.

dfs' :: Graph gr => gr a b -> [Node]

dfsWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [c]

dfsWith' :: Graph gr => CFun a b c -> gr a b -> [c]

dff :: Graph gr => [Node] -> gr a b -> [Tree Node]

Directed depth-first forest.

dff' :: Graph gr => gr a b -> [Tree Node]

dffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]

dffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]

xdfsWith

Arguments

:: Graph gr

=> CFun a b [Node]

Mapping from a node to its neighbours to be visited as well. suc' for example makes xdfsWith traverse the graph following the edge directions, while pre' means reversed directions.

-> CFun a b c

Mapping from the Context of a node to a result value.

-> [Node]

Nodes to be visited.

-> gr a b

-> [c]

Most general DFS algorithm to create a list of results. The other list-returning functions such as dfs are all defined in terms of this one.

xdfsWith d f vs = preorderF . xdffWith d f vs

xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)

Most general DFS algorithm to create a forest of results, otherwise very similar to xdfsWith. The other forest-returning functions such as dff are all defined in terms of this one.

xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]

Discard the graph part of the result of xdfWith.

xdffWith d f vs g = fst (xdfWith d f vs g)

udfs :: Graph gr => [Node] -> gr a b -> [Node]

Undirected depth-first search, obtained by following edges regardless of their direction.

udfs' :: Graph gr => gr a b -> [Node]

udff :: Graph gr => [Node] -> gr a b -> [Tree Node]

Undirected depth-first forest, obtained by following edges regardless of their direction.

udff' :: Graph gr => gr a b -> [Tree Node]

udffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]

udffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]

rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]

Reverse depth-first forest, obtained by following predecessors.

rdff' :: Graph gr => gr a b -> [Tree Node]

rdfs' :: Graph gr => gr a b -> [Node]

rdffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]

rdffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]

topsort :: Graph gr => gr a b -> [Node]

Topological sorting, i.e. a list of Nodes so that if there's an edge between a source and a target node, the source appears earlier in the result.

topsort' :: Graph gr => gr a b -> [a]

topsort, returning only the labels of the nodes.

scc :: Graph gr => gr a b -> [[Node]]

Collection of strongly connected components

reachable :: Graph gr => Node -> gr a b -> [Node]

Collection of nodes reachable from a starting point.

components :: Graph gr => gr a b -> [[Node]]

Collection of connected components

noComponents :: Graph gr => gr a b -> Int

Number of connected components

isConnected :: Graph gr => gr a b -> Bool

Is the graph connected?

condensation :: Graph gr => gr a b -> gr [Node] ()

The condensation of the given graph, i.e., the graph of its strongly connected components.

Dominators

dom :: Graph gr => gr a b -> Node -> [(Node, [Node])]

return the set of dominators of the nodes of a graph, given a root

iDom :: Graph gr => gr a b -> Node -> [(Node, Node)]

return immediate dominators for each node of a graph, given a root

Voronoi diagrams

type Voronoi a = LRTree a

Representation of a shortest path forest.

gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b

Produce a shortest path forest (the roots of which are those nodes specified) from nodes in the graph to one of the root nodes (if possible).

gvdOut :: (Graph gr, Real b) => [Node] -> gr a b -> Voronoi b

Produce a shortest path forest (the roots of which are those nodes specified) from nodes in the graph from one of the root nodes (if possible).

voronoiSet :: Node -> Voronoi b -> [Node]

Return the nodes reachable to/from (depending on how the Voronoi was constructed) from the specified root node (if the specified node is not one of the root nodes of the shortest path forest, an empty list will be returned).

nearestNode :: Node -> Voronoi b -> Maybe Node

Try to determine the nearest root node to the one specified in the shortest path forest.

nearestDist :: Node -> Voronoi b -> Maybe b

The distance to the nearestNode (if there is one) in the shortest path forest.

nearestPath :: Node -> Voronoi b -> Maybe Path

Try to construct a path to/from a specified node to one of the root nodes of the shortest path forest.

Independent node sets

indep :: DynGraph gr => gr a b -> [Node]

Calculate the maximum independent node set of the specified graph.

indepSize :: DynGraph gr => gr a b -> ([Node], Int)

The maximum independent node set along with its size.

Minimum spanning trees

msTreeAt :: (Graph gr, Real b) => Node -> gr a b -> LRTree b

msTree :: (Graph gr, Real b) => gr a b -> LRTree b

msPath :: LRTree b -> Node -> Node -> Path

Max flow

getRevEdges :: Num b => [Edge] -> [LEdge b]

                i                                 0
For each edge a--->b this function returns edge b--->a .
         i
Edges a<--->b are ignored
         j

augmentGraph :: (DynGraph gr, Num b) => gr a b -> gr a (b, b, b)

                i                                  0
For each edge a--->b insert into graph the edge a<---b . Then change the
                           i         (i,0,i)
label of every edge from a---->b to a------->b

where label (x,y,z)=(Max Capacity, Current flow, Residual capacity)

updAdjList :: Num b => Adj (b, b, b) -> Node -> b -> Bool -> Adj (b, b, b)

Given a successor or predecessor list for node u and given node v, find the label corresponding to edge (u,v) and update the flow and residual capacity of that edge's label. Then return the updated list.

updateFlow :: (DynGraph gr, Num b) => Path -> b -> gr a (b, b, b) -> gr a (b, b, b)

Update flow and residual capacity along augmenting path from s to t in graph @G. For a path [u,v,w,...] find the node u in G and its successor and predecessor list, then update the corresponding edges (u,v) and (v,u)@ on those lists by using the minimum residual capacity of the path.

mfmg :: (DynGraph gr, Num b, Ord b) => gr a (b, b, b) -> Node -> Node -> gr a (b, b, b)

Compute the flow from s to t on a graph whose edges are labeled with (x,y,z)=(max capacity,current flow,residual capacity) and all edges are of the form a<---->b. First compute the residual graph, that is, delete those edges whose residual capacity is zero. Then compute the shortest augmenting path from s to t, and finally update the flow and residual capacity along that path by using the minimum capacity of that path. Repeat this process until no shortest path from s to t exist.

mf :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b, b)

Compute the flow from s to t on a graph whose edges are labeled with x, which is the max capacity and where not all edges need to be of the form a<---->b. Return the flow as a grap whose edges are labeled with (x,y,z)=(max capacity,current flow,residual capacity) and all edges are of the form a<---->b

maxFlowgraph :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b)

Compute the maximum flow from s to t on a graph whose edges are labeled with x, which is the max capacity and where not all edges need to be of the form a<---->b. Return the flow as a graph whose edges are labeled with (y,x) = (current flow, max capacity).

maxFlow :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> b

Compute the value of a maximumflow

type Network = Gr () (Double, Double)

ekSimple :: Network -> Node -> Node -> (Network, Double)

ekFused :: Network -> Node -> Node -> (Network, Double)

ekList :: Network -> Node -> Node -> (Network, Double)

Shortest path

data Heap a b

Instances

(Eq a, Eq b) => Eq (Heap a b)

Defined in Data.Graph.Inductive.Internal.Heap

Methods

(==) :: Heap a b -> Heap a b -> Bool

(/=) :: Heap a b -> Heap a b -> Bool

(Read a, Read b) => Read (Heap a b)

Defined in Data.Graph.Inductive.Internal.Heap

Methods

readsPrec :: Int -> ReadS (Heap a b)

readList :: ReadS [Heap a b]

readPrec :: ReadPrec (Heap a b)

readListPrec :: ReadPrec [Heap a b]

(Show a, Show b) => Show (Heap a b)

Defined in Data.Graph.Inductive.Internal.Heap

Methods

showsPrec :: Int -> Heap a b -> ShowS

show :: Heap a b -> String

showList :: [Heap a b] -> ShowS

(NFData a, NFData b) => NFData (Heap a b)

Defined in Data.Graph.Inductive.Internal.Heap

Methods

rnf :: Heap a b -> ()

spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b

Tree of shortest paths from a certain node to the rest of the (reachable) nodes.

Corresponds to dijkstra applied to a heap in which the only known node is the starting node, with a path of length 0 leading to it.

The edge labels of type b are the edge weights; negative edge weights are not supported.

sp

Arguments

:: (Graph gr, Real b)

=> Node

Start

-> Node

Destination

-> gr a b

-> Maybe Path

Shortest path between two nodes, if any.

Returns Nothing if the destination is not reachable from the start node, and Just path otherwise.

The edge labels of type b are the edge weights; negative edge weights are not supported.

spLength

Arguments

:: (Graph gr, Real b)

=> Node

Start

-> Node

Destination

-> gr a b

-> Maybe b

Length of the shortest path between two nodes, if any.

Returns Nothing if there is no path, and Just length otherwise.

The edge labels of type b are the edge weights; negative edge weights are not supported.

dijkstra

Arguments

:: (Graph gr, Real b)

=> Heap b (LPath b)

Initial heap of known paths and their lengths.

-> gr a b

-> LRTree b

Dijkstra's shortest path algorithm.

The edge labels of type b are the edge weights; negative edge weights are not supported.

Dynamic graphs

class Graph gr => DynGraph (gr :: * -> * -> *) where

Minimal complete definition

(&)

Methods

(&) :: Context a b -> gr a b -> gr a b

Merge the Context into the DynGraph.

Context adjacencies should only refer to either a Node already in a graph or the node in the Context itself (for loops).

Behaviour is undefined if the specified Node already exists in the graph.

Instances

DynGraph Gr

Defined in Data.Graph.Inductive.PatriciaTree

Methods

(&) :: Context a b -> Gr a b -> Gr a b

buildGr :: DynGraph gr => [Context a b] -> gr a b

Build a Graph from a list of Contexts.

The list should be in the order such that earlier Contexts depend upon later ones (i.e. as produced by ufold (:) []).

insNode :: DynGraph gr => LNode a -> gr a b -> gr a b

Insert a LNode into the Graph.

insNodes :: DynGraph gr => [LNode a] -> gr a b -> gr a b

Insert multiple LNodes into the Graph.

insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a b

Insert a LEdge into the Graph.

insEdges :: DynGraph gr => [LEdge b] -> gr a b -> gr a b

Insert multiple LEdges into the Graph.

delNode :: Graph gr => Node -> gr a b -> gr a b

Remove a Node from the Graph.

delNodes :: Graph gr => [Node] -> gr a b -> gr a b

Remove multiple Nodes from the Graph.

delEdge :: DynGraph gr => Edge -> gr a b -> gr a b

Remove an Edge from the Graph.

NOTE: in the case of multiple edges, this will delete all such edges from the graph as there is no way to distinguish between them. If you need to delete only a single such edge, please use delLEdge.

delEdges :: DynGraph gr => [Edge] -> gr a b -> gr a b

Remove multiple Edges from the Graph.

delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b

Remove an LEdge from the Graph.

NOTE: in the case of multiple edges with the same label, this will only delete the first such edge. To delete all such edges, please use delAllLedge.

delAllLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b

Remove all edges equal to the one specified.

gmap :: DynGraph gr => (Context a b -> Context c d) -> gr a b -> gr c d

Map a function over the graph by recursively calling match.

nmap :: DynGraph gr => (a -> c) -> gr a b -> gr c b

Map a function over the Node labels in a graph.

emap :: DynGraph gr => (b -> c) -> gr a b -> gr a c

Map a function over the Edge labels in a graph.

nemap :: DynGraph gr => (a -> c) -> (b -> d) -> gr a b -> gr c d

Map functions over both the Node and Edge labels in a graph.

gfiltermap :: DynGraph gr => (Context a b -> MContext c d) -> gr a b -> gr c d

Build a graph out of the contexts for which the predicate is satisfied by recursively calling match.

nfilter :: DynGraph gr => (Node -> Bool) -> gr a b -> gr a b

Returns the subgraph only containing the nodes which satisfy the given predicate.

labnfilter :: Graph gr => (LNode a -> Bool) -> gr a b -> gr a b

Returns the subgraph only containing the labelled nodes which satisfy the given predicate.

labfilter :: DynGraph gr => (a -> Bool) -> gr a b -> gr a b

Returns the subgraph only containing the nodes whose labels satisfy the given predicate.

subgraph :: DynGraph gr => [Node] -> gr a b -> gr a b

Returns the subgraph induced by the supplied nodes.

grev :: DynGraph gr => gr a b -> gr a b

Reverse the direction of all edges.

undir :: (Eq b, DynGraph gr) => gr a b -> gr a b

Make the graph undirected, i.e. for every edge from A to B, there exists an edge from B to A.

unlab :: DynGraph gr => gr a b -> gr () ()

Remove all labels.

efilter :: DynGraph gr => (LEdge b -> Bool) -> gr a b -> gr a b

Filter based on edge property.

elfilter :: DynGraph gr => (b -> Bool) -> gr a b -> gr a b

Filter based on edge label property.

Bi-connected components

bcc :: DynGraph gr => gr a b -> [gr a b]

Finds the bi-connected components of an undirected connected graph. It first finds the articulation points of the graph. Then it disconnects the graph on each articulation point and computes the connected components.

Pretty-printing

prettify :: (DynGraph gr, Show a, Show b) => gr a b -> String

Pretty-print the graph. Note that this loses a lot of information, such as edge inverses, etc.

prettyPrint :: (DynGraph gr, Show a, Show b) => gr a b -> IO ()

Pretty-print the graph to stdout.

Transitive/reflexive closure

trc :: DynGraph gr => gr a b -> gr a ()

Finds the transitive, reflexive closure of a directed graph. Given a graph G=(V,E), its transitive closure is the graph: G* = (V,E*) where E*={(i,j): i,j in V and either i = j or there is a path from i to j in G}

rc :: DynGraph gr => gr a b -> gr a ()

Finds the reflexive closure of a directed graph. Given a graph G=(V,E), its transitive closure is the graph: G* = (V,Er union E) where Er = {(i,i): i in V}

tc :: DynGraph gr => gr a b -> gr a ()

Finds the transitive closure of a directed graph. Given a graph G=(V,E), its transitive closure is the graph: G* = (V,E*) where E*={(i,j): i,j in V and there is a path from i to j in G}

Misc. types

Node

type Node = Int

Unlabeled node

type LNode a = (Node, a)

Labeled node

type UNode = LNode ()

Quasi-unlabeled node

Edge

type Edge = (Node, Node)

Unlabeled edge

type LEdge b = (Node, Node, b)

Labeled edge

type UEdge = LEdge ()

Quasi-unlabeled edge

toEdge :: LEdge b -> Edge

Drop the label component of an edge.

edgeLabel :: LEdge b -> b

The label in an edge.

toLEdge :: Edge -> b -> LEdge b

Add a label to an edge.

Context

type Context a b = (Adj b, Node, a, Adj b)

Links to the Node, the Node itself, a label, links from the Node.

In other words, this captures all information regarding the specified Node within a graph.

type MContext a b = Maybe (Context a b)

type UContext = ([Node], Node, [Node])

Unlabeled context.

node' :: Context a b -> Node

The Node in a Context.

lab' :: Context a b -> a

The label in a Context.

labNode' :: Context a b -> LNode a

The LNode from a Context.

neighbors' :: Context a b -> [Node]

All Nodes linked to or from in a Context.

lneighbors' :: Context a b -> Adj b

All labelled links coming into or going from a Context.

suc' :: Context a b -> [Node]

All Nodes linked to in a Context.

pre' :: Context a b -> [Node]

All Nodes linked from in a Context.

lpre' :: Context a b -> [(Node, b)]

All Nodes linked from in a Context, and the label of the links.

lsuc' :: Context a b -> [(Node, b)]

All Nodes linked from in a Context, and the label of the links.

out' :: Context a b -> [LEdge b]

All outward-directed LEdges in a Context.

inn' :: Context a b -> [LEdge b]

All inward-directed LEdges in a Context.

outdeg' :: Context a b -> Int

The outward degree of a Context.

indeg' :: Context a b -> Int

The inward degree of a Context.

deg' :: Context a b -> Int

The degree of a Context.

Decomposition

type Decomp (g :: * -> * -> *) a b = (MContext a b, g a b)

Graph decomposition - the context removed from a Graph, and the rest of the Graph.

type GDecomp (g :: * -> * -> *) a b = (Context a b, g a b)

The same as Decomp, only more sure of itself.

type UDecomp g = (Maybe UContext, g)

Unlabeled decomposition.

Path

type Path = [Node]

Unlabeled path

newtype LPath a

Labeled path

Constructors

LP

Fields

• unLPath :: [LNode a]

Instances

Eq a => Eq (LPath a)

Defined in Data.Graph.Inductive.Graph

Methods

(==) :: LPath a -> LPath a -> Bool

(/=) :: LPath a -> LPath a -> Bool

Ord a => Ord (LPath a)

Defined in Data.Graph.Inductive.Graph

Methods

compare :: LPath a -> LPath a -> Ordering

(<) :: LPath a -> LPath a -> Bool

(<=) :: LPath a -> LPath a -> Bool

(>) :: LPath a -> LPath a -> Bool

(>=) :: LPath a -> LPath a -> Bool

max :: LPath a -> LPath a -> LPath a

min :: LPath a -> LPath a -> LPath a

Show a => Show (LPath a)

Defined in Data.Graph.Inductive.Graph

Methods

showsPrec :: Int -> LPath a -> ShowS

show :: LPath a -> String

showList :: [LPath a] -> ShowS

type UPath = [UNode]

Quasi-unlabeled path

Tree

type RTree = [Path]

type LRTree a = [LPath a]

Adj

type Adj b = [(b, Node)]

Labeled links to or from a Node.

OrdGr

newtype OrdGr (gr :: * -> * -> *) a b

OrdGr comes equipped with an Ord instance, so that graphs can be used as e.g. Map keys.

Constructors

OrdGr

Fields

• unOrdGr :: gr a b

Instances

(Graph gr, Ord a, Ord b) => Eq (OrdGr gr a b)

Defined in Data.Graph.Inductive.Graph

Methods

(==) :: OrdGr gr a b -> OrdGr gr a b -> Bool

(/=) :: OrdGr gr a b -> OrdGr gr a b -> Bool

(Graph gr, Ord a, Ord b) => Ord (OrdGr gr a b)

Defined in Data.Graph.Inductive.Graph

Methods

compare :: OrdGr gr a b -> OrdGr gr a b -> Ordering

(<) :: OrdGr gr a b -> OrdGr gr a b -> Bool

(<=) :: OrdGr gr a b -> OrdGr gr a b -> Bool

(>) :: OrdGr gr a b -> OrdGr gr a b -> Bool

(>=) :: OrdGr gr a b -> OrdGr gr a b -> Bool

max :: OrdGr gr a b -> OrdGr gr a b -> OrdGr gr a b

min :: OrdGr gr a b -> OrdGr gr a b -> OrdGr gr a b

Read (gr a b) => Read (OrdGr gr a b)

Defined in Data.Graph.Inductive.Graph

Methods

readsPrec :: Int -> ReadS (OrdGr gr a b)

readList :: ReadS [OrdGr gr a b]

readPrec :: ReadPrec (OrdGr gr a b)

readListPrec :: ReadPrec [OrdGr gr a b]

Show (gr a b) => Show (OrdGr gr a b)

Defined in Data.Graph.Inductive.Graph

Methods

showsPrec :: Int -> OrdGr gr a b -> ShowS

show :: OrdGr gr a b -> String

showList :: [OrdGr gr a b] -> ShowS