Data.Graph.UGraph

Documentation

newtype UGraph v e

Undirected Graph of Vertices in v and Edges with attributes in e

Constructors

UGraph

Fields

• unUGraph :: HashMap v (Links v e)

Instances

Graph UGraph

Methods

empty :: Hashable v => UGraph v e

order :: UGraph v e -> Int

size :: (Hashable v, Eq v) => UGraph v e -> Int

vertices :: UGraph v e -> [v]

edgePairs :: (Hashable v, Eq v) => UGraph v e -> [(v, v)]

containsVertex :: (Hashable v, Eq v) => UGraph v e -> v -> Bool

adjacentVertices :: (Hashable v, Eq v) => UGraph v e -> v -> [v]

vertexDegree :: (Hashable v, Eq v) => UGraph v e -> v -> Int

degrees :: (Hashable v, Eq v) => UGraph v e -> [Int]

maxDegree :: (Hashable v, Eq v) => UGraph v e -> Int

minDegree :: (Hashable v, Eq v) => UGraph v e -> Int

avgDegree :: (Hashable v, Eq v) => UGraph v e -> Double

density :: (Hashable v, Eq v) => UGraph v e -> Double

insertVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e

insertVertices :: (Hashable v, Eq v) => [v] -> UGraph v e -> UGraph v e

containsEdgePair :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> Bool

incidentEdgePairs :: (Hashable v, Eq v) => UGraph v e -> v -> [(v, v)]

insertEdgePair :: (Hashable v, Eq v) => (v, v) -> UGraph v () -> UGraph v ()

removeEdgePair :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

isSimple :: (Hashable v, Eq v) => UGraph v e -> Bool

isRegular :: UGraph v e -> Bool

fromAdjacencyMatrix :: [[Int]] -> Maybe (UGraph Int ())

toAdjacencyMatrix :: UGraph v e -> [[Int]]

(Eq e, Eq v) => Eq (UGraph v e)

Methods

(==) :: UGraph v e -> UGraph v e -> Bool

(/=) :: UGraph v e -> UGraph v e -> Bool

(Show e, Show v) => Show (UGraph v e)

Methods

showsPrec :: Int -> UGraph v e -> ShowS

show :: UGraph v e -> String

showList :: [UGraph v e] -> ShowS

(Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v) => Arbitrary (UGraph v e)

Methods

arbitrary :: Gen (UGraph v e)

shrink :: UGraph v e -> [UGraph v e]

removeVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e

O(n) Remove a vertex from a UGraph if present | Every Edge incident to this vertex is also removed

insertEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e

O(log n) Insert an undirected Edge into a UGraph | The involved vertices are inserted if don't exist. If the graph already | contains the Edge, its attribute is updated

insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e

O(m*log n) Insert many directed Edges into a UGraph | Same rules as insertEdge are applied

removeEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e

O(log n) Remove the undirected Edge from a UGraph if present | The involved vertices are left untouched

removeEdge' :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

Same as removeEdge but the edge is an unordered pair

removeEdgeAndVertices :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e

O(log n) Remove the undirected Edge from a UGraph if present | The involved vertices are also removed

removeEdgeAndVertices' :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

Same as removeEdgeAndVertices but the edge is an unordered pair

edges :: forall v e. (Hashable v, Eq v) => UGraph v e -> [Edge v e]

O(n*m) Retrieve the Edges of a UGraph

containsEdge :: (Hashable v, Eq v) => UGraph v e -> Edge v e -> Bool

O(log n) Tell if an undirected Edge exists in the graph

containsEdge' :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> Bool

Same as containsEdge but the edge is an unordered pair

incidentEdges :: (Hashable v, Eq v) => UGraph v e -> v -> [Edge v e]

Retrieve the incident Edges of a Vertex

areIsomorphic :: UGraph v e -> UGraph v' e' -> Bool

Tell if two UGraph are isomorphic

isomorphism :: UGraph v e -> UGraph v' e' -> v -> v'

newtype DegreeSequence

The Degree Sequence of a simple UGraph is a list of degrees

Constructors

DegreeSequence

Fields

• unDegreeSequence :: [Int]

Instances

Eq DegreeSequence

Methods

(==) :: DegreeSequence -> DegreeSequence -> Bool

(/=) :: DegreeSequence -> DegreeSequence -> Bool

Ord DegreeSequence

Methods

compare :: DegreeSequence -> DegreeSequence -> Ordering

(<) :: DegreeSequence -> DegreeSequence -> Bool

(<=) :: DegreeSequence -> DegreeSequence -> Bool

(>) :: DegreeSequence -> DegreeSequence -> Bool

(>=) :: DegreeSequence -> DegreeSequence -> Bool

max :: DegreeSequence -> DegreeSequence -> DegreeSequence

min :: DegreeSequence -> DegreeSequence -> DegreeSequence

Show DegreeSequence

Methods

showsPrec :: Int -> DegreeSequence -> ShowS

show :: DegreeSequence -> String

showList :: [DegreeSequence] -> ShowS

degreeSequence :: [Int] -> DegreeSequence

Construct a DegreeSequence from a list of degrees | Negative degree values are discarded

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

Get the DegreeSequence of a simple UGraph | If the graph is not simple (see isSimple) the result is Nothing

isGraphicalSequence :: DegreeSequence -> Bool

Tell if a DegreeSequence is a Graphical Sequence | A Degree Sequence is a Graphical Sequence if a corresponding UGraph for | it exists

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

Get the corresponding UGraph of a DegreeSequence | If the DegreeSequence is not graphical (see isGraphicalSequence) the | result is Nothing