graphite-0.9.5.1: Graphs and networks library

Safe HaskellSafe
LanguageHaskell2010

Data.Graph.UGraph.DegreeSequence

Contents

Synopsis

Documentation

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