Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
- newtype DGraph v e = DGraph {}
- type DegreeSequence = [(Int, Int)]
- removeVertex :: (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) => DGraph v e -> Arc v e -> DGraph v e
- removeArc' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> DGraph v e
- removeArcAndVertices :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> DGraph v e
- removeArcAndVertices' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> DGraph v e
- arcs :: forall v e. (Hashable v, Eq v) => DGraph v e -> [Arc v e]
- arcs' :: (Hashable v, Eq v) => DGraph v e -> [(v, v)]
- 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]
- isSymmetric :: DGraph v e -> Bool
- isOriented :: DGraph v e -> Bool
- 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
- toUndirected :: (Hashable v, Eq v) => DGraph v e -> UGraph v e
- isDirectedGraphic :: DegreeSequence -> Bool
Documentation
Directed Graph of Vertices in v and Arcs with attributes in e
type DegreeSequence = [(Int, Int)] Source #
The Degree Sequence of a DGraph
is a list of pairs (Indegree, Outdegree)
removeArc' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> DGraph v e Source #
Same as removeArc
but the arc is an ordered pair
removeArcAndVertices' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> DGraph v e Source #
Same as removeArcAndVertices
but the arc is an ordered pair
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 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
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
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