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

Language | Haskell2010 |

- data DegreeSequence
- degreeSequence :: [Int] -> DegreeSequence
- getDegreeSequence :: (Hashable v, Eq v) => UGraph v e -> Maybe DegreeSequence
- isGraphicalSequence :: DegreeSequence -> Bool
- isDirectedGraphic :: DegreeSequence -> Bool
- holdsHandshakingLemma :: DegreeSequence -> Bool
- fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ())

# Documentation

data DegreeSequence Source #

The Degree Sequence of a simple `UGraph`

is a list of degrees of the
vertices in the graph

Use `degreeSequence`

to construct a valid Degree Sequence

# Construction

degreeSequence :: [Int] -> DegreeSequence Source #

Construct a `DegreeSequence`

from a list of degrees. Negative degree values
get discarded

getDegreeSequence :: (Hashable v, Eq v) => UGraph v e -> Maybe DegreeSequence Source #

Get the `DegreeSequence`

of a simple `UGraph`

. If the graph is not `simple`

(see `isSimple`

) the result is Nothing

# Queries

isGraphicalSequence :: DegreeSequence -> Bool Source #

Tell if a `DegreeSequence`

is a Graphical Sequence

A Degree Sequence is a `Graphical Sequence`

if a corresponding `UGraph`

for
it exists. Uses the Havel-Hakimi algorithm

isDirectedGraphic :: DegreeSequence -> Bool Source #

Tell if a `DegreeSequence`

is a Directed Graphic

A `Directed Graphic`

is a Degree Sequence for which a `DGraph`

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

holdsHandshakingLemma :: DegreeSequence -> Bool Source #

Tell if a `DegreeSequence`

holds the Handshaking lemma, that is, if the
number of vertices with odd degree is even

# Graph generation

fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ()) Source #

Get the corresponding `UGraph`

of a `DegreeSequence`

. If the
`DegreeSequence`

is not graphical (see `isGraphicalSequence`

) the result is
Nothing