ModuleCabal-syntax-3.12.1.0Haskell2010

Distribution.Compat.Graph

A data type representing directed graphs, backed by Data.Graph. It is strict in the node type.

This is an alternative interface to Data.Graph. In this interface, nodes (identified by the IsNode type class) are associated with a key and record the keys of their neighbors. This interface is more convenient than Graph, which requires vertices to be explicitly handled by integer indexes.

The current implementation has somewhat peculiar performance characteristics. The asymptotics of all map-like operations mirror their counterparts in Data.Map. However, to perform a graph operation, we first must build the Data.Graph representation, an operation that takes O(V + E log V). However, this operation can be amortized across all queries on that particular graph.

Some nodes may be broken, i.e., refer to neighbors which are not stored in the graph. In our graph algorithms, we transparently ignore such edges; however, you can easily query for the broken vertices of a graph using broken (and should, e.g., to ensure that a closure of a graph is well-formed.) It's possible to take a closed subset of a broken graph and get a well-formed graph.

3 types
1 class
26 values

PackageCabal-syntax-3.12.1.0
Exports31
LanguageHaskell2010
LicenceBSD-3-Clause
SourceGraph.hs

Graph type

2 declarations

datadata Graph a

A graph of nodes a. The nodes are expected to have instance of class IsNode.

Instances7Foldable, Eq, Read, Show, NFData, Binary, …

Foldable GraphDefined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(Eq (Key a), Eq a) => Eq (Graph a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(IsNode a, Read a, Show (Key a)) => Read (Graph a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
Show a => Show (Graph a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(NFData a, NFData (Key a)) => NFData (Graph a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(IsNode a, Binary a, Show (Key a)) => Binary (Graph a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
Structured a => Structured (Graph a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph

classclass Ord (Key a) => IsNode a where

The IsNode class is used for datatypes which represent directed graph nodes. A node of type a is associated with some unique key of type Key a; given a node we can determine its key (nodeKey) and the keys of its neighbors (nodeNeighbors).

Associated types

type family Key a

Methods

nodeKey :: a -> Key a
nodeNeighbors :: a -> [Key a]

Instances3IsNode

IsNode InstalledPackageInfoDefined in Cabal-syntax-3.12.1.0 · Distribution.Types.InstalledPackageInfo
Ord k => IsNode (Node k a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(IsNode a, IsNode b, Key a ~ Key b) => IsNode (Either a b)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph

Query

4 declarations

valuenull :: Graph a -> Bool

O(1). Is the graph empty?

valuesize :: Graph a -> Int

O(1). The number of nodes in the graph.

valuemember :: IsNode a => Key a -> Graph a -> Bool

O(log V). Check if the key is in the graph.

valuelookup :: IsNode a => Key a -> Graph a -> Maybe a

O(log V). Lookup the node at a key in the graph.

Construction

4 declarations

valueempty :: IsNode a => Graph a

O(1). The empty graph.

valueinsert :: IsNode a => a -> Graph a -> Graph a

O(log V). Insert a node into a graph.

valuedeleteKey :: IsNode a => Key a -> Graph a -> Graph a

O(log V). Delete the node at a key from the graph.

valuedeleteLookup :: IsNode a => Key a -> Graph a -> (Maybe a, Graph a)

O(log V). Lookup and delete. This function returns the deleted value if it existed.

Combine

2 declarations

valueunionLeft :: IsNode a => Graph a -> Graph a -> Graph a

O(V + V'). Left-biased union, preferring entries from the first map when conflicts occur.

valueunionRight :: IsNode a => Graph a -> Graph a -> Graph a

O(V + V'). Right-biased union, preferring entries from the second map when conflicts occur. nodeKey x = nodeKey (f x).

Graph algorithms

11 declarations

valuestronglyConnComp :: Graph a -> [SCC a]

Ω(V + E). Compute the strongly connected components of a graph. Requires amortized construction of graph.

datadata SCC vertex

Strongly connected component.

Constructors

AcyclicSCC vertex
A single vertex that is not in any cycle.
NECyclicSCC !(NonEmpty vertex)
A maximal set of mutually reachable vertices.

Instances17Functor, Foldable, Traversable, Foldable1, Eq1, Read1, …

Functor SCCDefined in containers-0.7 · Data.Graph
Foldable SCCDefined in containers-0.7 · Data.Graph
Traversable SCCDefined in containers-0.7 · Data.Graph
Foldable1 SCCDefined in containers-0.7 · Data.Graph
Eq1 SCCDefined in containers-0.7 · Data.Graph
Read1 SCCDefined in containers-0.7 · Data.Graph
Show1 SCCDefined in containers-0.7 · Data.Graph
Generic1 SCCDefined in containers-0.7 · Data.Graph
Lift vertex => Lift (SCC vertex)Defined in containers-0.7 · Data.Graph
Eq vertex => Eq (SCC vertex)Defined in containers-0.7 · Data.Graph
Data vertex => Data (SCC vertex)Defined in containers-0.7 · Data.Graph
Read vertex => Read (SCC vertex)Defined in containers-0.7 · Data.Graph
Show vertex => Show (SCC vertex)Defined in containers-0.7 · Data.Graph
Generic (SCC vertex)Defined in containers-0.7 · Data.Graph
NFData a => NFData (SCC a)Defined in containers-0.7 · Data.Graph
type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-1cc3" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 vertex)) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec0 (NonEmpty vertex))))Defined in containers-0.7 · Data.Graph
type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-1cc3" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec1 NonEmpty)))Defined in containers-0.7 · Data.Graph

patternpattern CyclicSCC :: [vertex] -> SCC vertex

Partial pattern synonym for backward compatibility with containers < 0.7.

valuecycles :: Graph a -> [[a]]

Ω(V + E). Compute the cycles of a graph. Requires amortized construction of graph.

valuebroken :: Graph a -> [(a, [Key a])]

O(1). Return a list of nodes paired with their broken neighbors (i.e., neighbor keys which are not in the graph). Requires amortized construction of graph.

valueneighbors :: Graph a -> Key a -> Maybe [a]

Lookup the immediate neighbors from a key in the graph. Requires amortized construction of graph.

valuerevNeighbors :: Graph a -> Key a -> Maybe [a]

Lookup the immediate reverse neighbors from a key in the graph. Requires amortized construction of graph.

valueclosure :: Graph a -> [Key a] -> Maybe [a]

Compute the subgraph which is the closure of some set of keys. Returns Nothing if one (or more) keys are not present in the graph. Requires amortized construction of graph.

valuerevClosure :: Graph a -> [Key a] -> Maybe [a]

Compute the reverse closure of a graph from some set of keys. Returns Nothing if one (or more) keys are not present in the graph. Requires amortized construction of graph.

valuetopSort :: Graph a -> [a]

Topologically sort the nodes of a graph. Requires amortized construction of graph.

valuerevTopSort :: Graph a -> [a]

Reverse topologically sort the nodes of a graph. Requires amortized construction of graph.

Conversions

0 declarations

Maps

valuetoMap :: Graph a -> Map (Key a) a

O(1). Convert a graph into a map from keys to nodes. The resulting map m is guaranteed to have the property that all ((k,n) -> k == nodeKey n) (Data.Map.toList m).

Lists

valuefromDistinctList :: (IsNode a, Show (Key a)) => [a] -> Graph a

O(V log V). Convert a list of nodes (with distinct keys) into a graph.

valuetoList :: Graph a -> [a]

O(V). Convert a graph into a list of nodes.

valuekeys :: Graph a -> [Key a]

O(V). Convert a graph into a list of keys.

Sets

valuekeysSet :: Graph a -> Set (Key a)

O(V). Convert a graph into a set of keys.

Graphs

valuetoGraph :: Graph a -> (Graph, Vertex -> a, Key a -> Maybe Vertex)

O(1). Convert a graph into a Graph. Requires amortized construction of graph.

Node type

2 declarations

datadata Node k a

A simple, trivial data type which admits an IsNode instance.

Constructors

N a k [k]

Instances5Functor, Eq, Show, IsNode, Key

Functor (Node k)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(Eq a, Eq k) => Eq (Node k a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
(Show a, Show k) => Show (Node k a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
Ord k => IsNode (Node k a)Defined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph
type Key (Node k a) = kDefined in Cabal-syntax-3.12.1.0 · Distribution.Compat.Graph

valuenodeValue :: Node k a -> a

Get the value from a Node.