Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

- newtype DGraph v e = DGraph {}
- type DegreeSequence = [(Int, Int)]
- empty :: Hashable v => DGraph v e
- insertVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e
- removeVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e
- insertVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e
- insertArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e
- insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e
- removeArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e
- removeArc' :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e
- removeArcAndVertices :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e
- removeArcAndVertices' :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e
- vertices :: DGraph v e -> [v]
- order :: DGraph v e -> Int
- size :: (Hashable v, Eq v) => DGraph v e -> Int
- arcs :: forall v e. (Hashable v, Eq v) => DGraph v e -> [Arc v e]
- arcs' :: (Hashable v, Eq v) => DGraph v e -> [(v, v)]
- containsVertex :: (Hashable v, Eq v) => DGraph v e -> v -> Bool
- containsArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> Bool
- containsArc' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> Bool
- inboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]
- outboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]
- incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]
- adjacentVertices :: DGraph v e -> v -> [v]
- isSymmetric :: DGraph v e -> Bool
- isOriented :: DGraph v e -> Bool
- isIsolated :: DGraph v e -> Bool
- vertexDegree :: DGraph v e -> v -> Int
- vertexIndegree :: DGraph v e -> v -> Int
- vertexOutdegree :: DGraph v e -> v -> Int
- indegrees :: DGraph v e -> [Int]
- outdegrees :: DGraph v e -> [Int]
- isBalanced :: DGraph v e -> Bool
- isRegular :: DGraph v e -> Bool
- isSource :: DGraph v e -> v -> Bool
- isSink :: DGraph v e -> v -> Bool
- isInternal :: DGraph v e -> v -> Bool
- isDirectedGraphic :: DegreeSequence -> Bool

# Documentation

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

type DegreeSequence = [(Int, Int)] Source #

The Degree Sequence un a `DGraph`

is a list of pairs (Indegree, Outdegree)

empty :: Hashable v => DGraph v e Source #

The Empty (order-zero) `DGraph`

with no vertices and no arcs

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

`O(log n)`

Insert a vertex into a `DGraph`

| If the graph already contains the vertex leave the graph untouched

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

`O(m*log n)`

Insert a many vertices into a `DGraph`

| New vertices are inserted and already contained 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) => (v, v) -> DGraph v e -> DGraph v e Source #

Same as `removeArcAndVertices`

but the arc is an ordered pair

order :: DGraph v e -> Int Source #

`O(n)`

Retrieve the order of a `DGraph`

| The `order`

of a graph is its number of vertices

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

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

`O(log n)`

Tell if a vertex exists in the graph

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 `Arc`

s of a Vertex

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

Retrieve the outbounding `Arc`

s of a Vertex

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

Retrieve the incident `Arc`

s of a Vertex
| Both inbounding and outbounding arcs

adjacentVertices :: DGraph v e -> v -> [v] Source #

Retrieve the adjacent vertices of a vertex

isSymmetric :: DGraph v e -> Bool Source #

isOriented :: DGraph v e -> Bool Source #

Tell if a `DGraph`

is oriented
| There are none bidirected `Arc`

s
| Note: This is *not* the opposite of `isSymmetric`

isIsolated :: DGraph v e -> Bool Source #

Tell if a `DGraph`

is isolated
| A graph is `isolated`

if it has no edges, that is, it has a degree of 0
| TODO: What if it has a loop?

vertexDegree :: DGraph v e -> v -> Int Source #

Degree of a vertex
| The total number of inbounding and outbounding `Arc`

s of a vertex

vertexIndegree :: DGraph v e -> v -> Int Source #

Indegree of a vertex
| The number of inbounding `Arc`

s to a vertex

vertexOutdegree :: DGraph v e -> v -> Int Source #

Outdegree of a vertex
| The number of outbounding `Arc`

s from a vertex

isBalanced :: 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 toher.

isSource :: DGraph v e -> v -> Bool Source #

Tell if a vertex is a source
| A vertex is a `source`

when its `indegree = 0`

isSink :: DGraph v e -> v -> Bool Source #

Tell if a vertex is a sink
| A vertex is a `sink`

when its `outdegree = 0`

isInternal :: 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`

isDirectedGraphic :: DegreeSequence -> Bool Source #

Tell if a `DegreeSequence`

is a Directed Graphic
| A `Directed Graphic`

is a Degree Sequence for wich a `DGraph`

exists
TODO: Kleitman–Wang | Fulkerson–Chen–Anstee theorem algorithms