Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
- newtype DegreeSequence = DegreeSequence {
- unDegreeSequence :: [Int]
- 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
newtype DegreeSequence Source #
The Degree Sequence of a simple UGraph
is a list of degrees of vertices
| in a graph
| Use degreeSequence
to construct a valid Degree Sequence
degreeSequence :: [Int] -> DegreeSequence Source #
Construct a DegreeSequence
from a list of degrees
| Negative degree values are 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
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.
| Use the Havel-Hakimi algorithm
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
holdsHandshakingLemma :: DegreeSequence -> Bool Source #
Tell if a DegreeSequence
holds the Handshaking lemma, that is, if the
| number of vertices with odd degree is even
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