This is an alternative site for discovering Elm packages. You may be looking for the official Elm package site instead.

# Graph.Degree

This module provides functions to calculate the degrees of nodes in a graph.

• outdegree: number of outgoing edges
• indegree: number of incoming edges

## Types

type alias Degree = Int

The degree of a node in a graph is the number of edges incident to it.

type alias InOut a = { incoming : a , outgoing : a }

Encapsulates information about incoming and outgoing degrees.

## Functions

allDegrees : Graph node -> Dict Node.Identifier (InOut Degree)

Get a dictionary of all degrees (incoming and outgoing) for all nodes in a graph.

incoming : Graph node -> Node.Identifier -> Degree

Get the incoming degree of a node in a graph.

outgoing : Graph node -> Node.Identifier -> Degree

Get the outgoing degree of a node in a graph.

topDegrees : Graph node -> InOut (List ( Node.Identifier, InOut Degree ))

Get a list of all top inbound and outbound nodes with their respective InOut Degrees. The lists are sorting descending by the degree (fallback alphabetically by identifier).

``````module Graph.Degree
exposing
( Degree
, InOut
, allDegrees
, incoming
, outgoing
, topDegrees
)

{-| This module provides functions to calculate the degrees of nodes in a graph.

* outdegree: number of outgoing edges
* indegree: number of incoming edges

## Types

@docs Degree, InOut

## Functions

@docs allDegrees, incoming, outgoing, topDegrees
-}

import Graph exposing (Graph)
import Graph.Edge exposing (Edge)
import Graph.Node as Node exposing (Node)
import Dict exposing (Dict)

{-| The degree of a node in a graph is the number of edges incident to it.

See https://en.wikipedia.org/wiki/Vertex_(graph_theory)
-}
type alias Degree =
Int

{-| Encapsulates information about incoming and outgoing degrees.
-}
type alias InOut a =
{ incoming : a
, outgoing : a
}

{-| Get the outgoing degree of a node in a graph.
-}
outgoing : Graph node -> Node.Identifier -> Degree
outgoing graph identifier =
List.filter (\edge -> edge.from == identifier) graph.edges
|> List.length

{-| Get the incoming degree of a node in a graph.
-}
incoming : Graph node -> Node.Identifier -> Degree
incoming graph identifier =
List.filter (\edge -> edge.to == identifier) graph.edges
|> List.length

{-| Get a dictionary of all degrees (incoming and outgoing) for all nodes in a
graph.
-}
allDegrees : Graph node -> Dict Node.Identifier (InOut Degree)
allDegrees graph =
List.foldl (\edge dict -> updateDegrees graph.edges edge dict) Dict.empty graph.edges

{-| Get a list of all top inbound and outbound nodes with their respective
InOut Degrees. The lists are sorting descending by the degree (fallback
alphabetically by identifier).
-}
topDegrees : Graph node -> InOut (List ( Node.Identifier, InOut Degree ))
topDegrees graph =
let
degreesList =
allDegrees graph
|> Dict.toList

topIn =
List.sortWith (compareDegreesDictTuple .incoming) degreesList
|> List.reverse

topOut =
List.sortWith (compareDegreesDictTuple .outgoing) degreesList
|> List.reverse
in
InOut topIn topOut

compareDegreesDictTuple : (InOut Degree -> Degree) -> ( Node.Identifier, InOut Degree ) -> ( Node.Identifier, InOut Degree ) -> Basics.Order
compareDegreesDictTuple sortByField ( identifierA, degreesA ) ( identifierB, degreesB ) =
let
degreeCompare =
compare (sortByField degreesA) (sortByField degreesB)
in
if degreeCompare == EQ then
-- This function is primarily used in the topDegrees function where
-- we sort descending by the degree field selected above.
-- The sorting by name however should be alphabetically ascending,
-- hence we invert the arguments here.
compare identifierB identifierA
else
degreeCompare

updateDegrees : List Edge -> Edge -> Dict Node.Identifier (InOut Degree) -> Dict Node.Identifier (InOut Degree)
updateDegrees allEdges edge dict =
let
fromDegree =
degreesInDict dict edge.from

toDegree =
degreesInDict dict edge.to

updatedFromDegree =
{ fromDegree | outgoing = fromDegree.outgoing + 1 }

updatedToDegree =
{ toDegree | incoming = toDegree.incoming + 1 }
in
Dict.insert edge.from updatedFromDegree dict
|> Dict.insert edge.to updatedToDegree

degreesInDict : Dict Node.Identifier (InOut Degree) -> Node.Identifier -> InOut Degree
degreesInDict dict identifier =
Dict.get identifier dict
|> Maybe.withDefault (InOut 0 0)
```
```