graphite-0.9.6.0: Graphs and networks library

Data.Graph.DGraph

Synopsis

DGraph data type

data DGraph v e Source #

Directed Graph of Vertices in v and Arcs with attributes in e

Instances

Functions on DGraph

insertArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e Source #

Insert a directed Arc into a DGraph

The involved vertices are inserted if they don't exist. If the graph already contains the Arc, its attribute gets updated

insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e Source #

Same as insertArc but for a list of Arcs

removeArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e Source #

Remove the directed Arc from a DGraph if present. The involved vertices are left untouched

removeArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e Source #

Same as removeArc but for a list of Arcs

removeArcAndVertices :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e Source #

Remove the directed Arc from a DGraph if present. The involved vertices also get removed

arcs :: forall v e. (Hashable v, Eq v) => DGraph v e -> [Arc v e] Source #

Retrieve the Arcs of a DGraph

containsArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> Bool Source #

Tell if a directed Arc exists in the graph

inboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] Source #

Retrieve the inbounding Arcs of a Vertex

outboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] Source #

Retrieve the outbounding Arcs of a Vertex

incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] Source #

Retrieve the incident Arcs of a Vertex

The incident arcs of a vertex are all the inbounding and outbounding arcs of the vertex

vertexIndegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int Source #

Indegree of a vertex

The indegree of a vertex is the number of inbounding Arcs to a vertex

vertexOutdegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int Source #

Outdegree of a vertex

The outdegree of a vertex is the number of outbounding Arcs from a vertex

indegrees :: (Hashable v, Eq v) => DGraph v e -> [Int] Source #

Indegrees of all the vertices in a DGraph

outdegrees :: (Hashable v, Eq v) => DGraph v e -> [Int] Source #

Outdegree of all the vertices in a DGraph

Query graph properties and characteristics

isSymmetric :: DGraph v e -> Bool Source #

Tell if a DGraph is symmetric

A directed graph is symmetric if all of its Arcs are bi-directed

isOriented :: DGraph v e -> Bool Source #

Tell if a DGraph is oriented

A directed graph is oriented if there are none bi-directed Arcs

Note: This is not the opposite of isSymmetric

isBalanced :: (Hashable v, Eq v) => DGraph v e -> Bool Source #

Tell if a DGraph is balanced

A directed graph is balanced when its indegree = outdegree

isRegular :: DGraph v e -> Bool Source #

Tell if a DGraph is regular

A directed graph is regular when all of its vertices have the same number of adjacent vertices AND when the indegree and outdegree of each vertex are equal to each other.

isSource :: (Hashable v, Eq v) => DGraph v e -> v -> Bool Source #

Tell if a vertex is a source

A vertex is a source when its indegree = 0

isSink :: (Hashable v, Eq v) => DGraph v e -> v -> Bool Source #

Tell if a vertex is a sink

A vertex is a sink when its outdegree = 0

isInternal :: (Hashable v, Eq v) => DGraph v e -> v -> Bool Source #

Tell if a vertex is internal

A vertex is internal when its neither a source nor a sink

Transformations

transpose :: (Hashable v, Eq v) => DGraph v e -> DGraph v e Source #

Get the transpose of a DGraph

The transpose of a directed graph is another directed graph where all of its arcs are reversed

toUndirected :: (Hashable v, Eq v) => DGraph v e -> UGraph v e Source #

Convert a directed DGraph to an undirected UGraph by converting all of its Arcs into Edges

List conversions

toArcsList :: (Hashable v, Eq v) => DGraph v e -> [Arc v e] Source #

Convert a DGraph to a list of Arcs discarding isolated vertices

Note that because toArcsList discards isolated vertices:

fromArcsList . toArcsList /= id

fromArcsList :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e Source #

Construct a DGraph from a list of Arcs

Pretty printing

prettyPrint :: (Hashable v, Eq v, Show v, Show e) => DGraph v e -> String Source #

Pretty print a DGraph