graphite-0.5.0.0: Graphs and networks library

Data.Graph.DGraph

Contents

Synopsis

# Documentation

newtype DGraph v e Source #

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

Constructors

 DGraph FieldsunDGraph :: HashMap v (Links v e)

Instances

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

O(log n) Insert a directed Arc into a DGraph | The involved vertices are inserted if don't exist. If the graph already | contains the Arc, its attribute is updated

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

O(m*log n) Insert many directed Arcs into a DGraph | Same rules as insertArc are applied

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

O(log n) Remove the directed Arc from a DGraph if present | The involved vertices are left untouched

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

Same as removeArc but the arc is an ordered pair

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

O(log n) Remove the directed Arc from a DGraph if present | The involved vertices are also removed

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

O(n*m) Retrieve the Arcs of a DGraph

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

Same as arcs but the arcs are ordered pairs, and their attributes are | discarded

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

O(log n) Tell if a directed Arc exists in the graph

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

Same as containsArc but the arc is an ordered pair

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 | Both inbounding and outbounding arcs

isSymmetric :: DGraph v e -> Bool Source #

Tell if a DGraph is symmetric | All of its Arcs are bidirected

isOriented :: DGraph v e -> Bool Source #

Tell if a DGraph is oriented | There are none bidirected Arcs | Note: This is not the opposite of isSymmetric

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

Indegree of a vertex | The number of inbounding Arcs to a vertex

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

Outdegree of a vertex | 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

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 a 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

# Lists

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

Convert a DGraph to a list of Arcs | Same as arcs

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

Construct a DGraph from a list of Arcs