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.

Graph type

data Graph a

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

Instances

Foldable Graph

Defined in Distribution.Compat.Graph

Methods

fold :: Monoid m => Graph m -> m

foldMap :: Monoid m => (a -> m) -> Graph a -> m

foldMap' :: Monoid m => (a -> m) -> Graph a -> m

foldr :: (a -> b -> b) -> b -> Graph a -> b

foldr' :: (a -> b -> b) -> b -> Graph a -> b

foldl :: (b -> a -> b) -> b -> Graph a -> b

foldl' :: (b -> a -> b) -> b -> Graph a -> b

foldr1 :: (a -> a -> a) -> Graph a -> a

foldl1 :: (a -> a -> a) -> Graph a -> a

toList :: Graph a -> [a]

null :: Graph a -> Bool

length :: Graph a -> Int

elem :: Eq a => a -> Graph a -> Bool

maximum :: Ord a => Graph a -> a

minimum :: Ord a => Graph a -> a

sum :: Num a => Graph a -> a

product :: Num a => Graph a -> a

(Eq (Key a), Eq a) => Eq (Graph a)

Defined in Distribution.Compat.Graph

Methods

(==) :: Graph a -> Graph a -> Bool

(/=) :: Graph a -> Graph a -> Bool

(IsNode a, Read a, Show (Key a)) => Read (Graph a)

Defined in Distribution.Compat.Graph

Methods

readsPrec :: Int -> ReadS (Graph a)

readList :: ReadS [Graph a]

readPrec :: ReadPrec (Graph a)

readListPrec :: ReadPrec [Graph a]

Show a => Show (Graph a)

Defined in Distribution.Compat.Graph

Methods

showsPrec :: Int -> Graph a -> ShowS

show :: Graph a -> String

showList :: [Graph a] -> ShowS

(IsNode a, Binary a, Show (Key a)) => Binary (Graph a)

Defined in Distribution.Compat.Graph

Methods

put :: Graph a -> Put

get :: Get (Graph a)

putList :: [Graph a] -> Put

(NFData a, NFData (Key a)) => NFData (Graph a)

Defined in Distribution.Compat.Graph

Methods

rnf :: Graph a -> ()

class 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 Key a

Methods

nodeKey :: a -> Key a

nodeNeighbors :: a -> [Key a]

Instances

IsNode InstalledPackageInfo

Defined in Distribution.Types.InstalledPackageInfo

Associated Types

type Key InstalledPackageInfo

Methods

nodeKey :: InstalledPackageInfo -> Key InstalledPackageInfo

nodeNeighbors :: InstalledPackageInfo -> [Key InstalledPackageInfo]

IsNode ComponentLocalBuildInfo

Defined in Distribution.Types.ComponentLocalBuildInfo

Associated Types

type Key ComponentLocalBuildInfo

Methods

nodeKey :: ComponentLocalBuildInfo -> Key ComponentLocalBuildInfo

nodeNeighbors :: ComponentLocalBuildInfo -> [Key ComponentLocalBuildInfo]

IsNode TargetInfo

Defined in Distribution.Types.TargetInfo

Associated Types

type Key TargetInfo

Methods

nodeKey :: TargetInfo -> Key TargetInfo

nodeNeighbors :: TargetInfo -> [Key TargetInfo]

(IsNode a, IsNode b, Key a ~ Key b) => IsNode (Either a b)

Defined in Distribution.Compat.Graph

Associated Types

type Key (Either a b)

Methods

nodeKey :: Either a b -> Key (Either a b)

nodeNeighbors :: Either a b -> [Key (Either a b)]

Ord k => IsNode (Node k a)

Defined in Distribution.Compat.Graph

Associated Types

type Key (Node k a)

Methods

nodeKey :: Node k a -> Key (Node k a)

nodeNeighbors :: Node k a -> [Key (Node k a)]

Query

null :: Graph a -> Bool

O(1). Is the graph empty?

size :: Graph a -> Int

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

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

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

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

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

Construction

empty :: IsNode a => Graph a

O(1). The empty graph.

insert :: IsNode a => a -> Graph a -> Graph a

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

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

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

deleteLookup :: 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

unionLeft :: IsNode a => Graph a -> Graph a -> Graph a

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

unionRight :: 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

stronglyConnComp :: Graph a -> [SCC a]

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

data SCC vertex

Strongly connected component.

Constructors

AcyclicSCC vertex

A single vertex that is not in any cycle.

CyclicSCC [vertex]

A maximal set of mutually reachable vertices.

Instances

Functor SCC

Since: containers-0.5.4

Defined in Data.Graph

Methods

fmap :: (a -> b) -> SCC a -> SCC b

(<$) :: a -> SCC b -> SCC a

Foldable SCC

Since: containers-0.5.9

Defined in Data.Graph

Methods

fold :: Monoid m => SCC m -> m

foldMap :: Monoid m => (a -> m) -> SCC a -> m

foldMap' :: Monoid m => (a -> m) -> SCC a -> m

foldr :: (a -> b -> b) -> b -> SCC a -> b

foldr' :: (a -> b -> b) -> b -> SCC a -> b

foldl :: (b -> a -> b) -> b -> SCC a -> b

foldl' :: (b -> a -> b) -> b -> SCC a -> b

foldr1 :: (a -> a -> a) -> SCC a -> a

foldl1 :: (a -> a -> a) -> SCC a -> a

toList :: SCC a -> [a]

null :: SCC a -> Bool

length :: SCC a -> Int

elem :: Eq a => a -> SCC a -> Bool

maximum :: Ord a => SCC a -> a

minimum :: Ord a => SCC a -> a

sum :: Num a => SCC a -> a

product :: Num a => SCC a -> a

Traversable SCC

Since: containers-0.5.9

Defined in Data.Graph

Methods

traverse :: Applicative f => (a -> f b) -> SCC a -> f (SCC b)

sequenceA :: Applicative f => SCC (f a) -> f (SCC a)

mapM :: Monad m => (a -> m b) -> SCC a -> m (SCC b)

sequence :: Monad m => SCC (m a) -> m (SCC a)

Eq1 SCC

Since: containers-0.5.9

Defined in Data.Graph

Methods

liftEq :: (a -> b -> Bool) -> SCC a -> SCC b -> Bool

Read1 SCC

Since: containers-0.5.9

Defined in Data.Graph

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (SCC a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [SCC a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (SCC a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [SCC a]

Show1 SCC

Since: containers-0.5.9

Defined in Data.Graph

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> SCC a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SCC a] -> ShowS

Eq vertex => Eq (SCC vertex)

Since: containers-0.5.9

Defined in Data.Graph

Methods

(==) :: SCC vertex -> SCC vertex -> Bool

(/=) :: SCC vertex -> SCC vertex -> Bool

Data vertex => Data (SCC vertex)

Since: containers-0.5.9

Defined in Data.Graph

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SCC vertex -> c (SCC vertex)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SCC vertex)

toConstr :: SCC vertex -> Constr

dataTypeOf :: SCC vertex -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SCC vertex))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SCC vertex))

gmapT :: (forall b. Data b => b -> b) -> SCC vertex -> SCC vertex

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r

gmapQ :: (forall d. Data d => d -> u) -> SCC vertex -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> SCC vertex -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex)

Read vertex => Read (SCC vertex)

Since: containers-0.5.9

Defined in Data.Graph

Methods

readsPrec :: Int -> ReadS (SCC vertex)

readList :: ReadS [SCC vertex]

readPrec :: ReadPrec (SCC vertex)

readListPrec :: ReadPrec [SCC vertex]

Show vertex => Show (SCC vertex)

Since: containers-0.5.9

Defined in Data.Graph

Methods

showsPrec :: Int -> SCC vertex -> ShowS

show :: SCC vertex -> String

showList :: [SCC vertex] -> ShowS

Generic (SCC vertex)

Since: containers-0.5.9

Defined in Data.Graph

Associated Types

type Rep (SCC vertex) :: Type -> Type

Methods

from :: SCC vertex -> Rep (SCC vertex) x

to :: Rep (SCC vertex) x -> SCC vertex

NFData a => NFData (SCC a)

Defined in Data.Graph

Methods

rnf :: SCC a -> ()

Generic1 SCC

Since: containers-0.5.9

Defined in Data.Graph

Associated Types

type Rep1 SCC :: k -> Type

Methods

from1 :: forall (a :: k). SCC a -> Rep1 SCC a

to1 :: forall (a :: k). Rep1 SCC a -> SCC a

type Rep (SCC vertex)

Defined in Data.Graph

type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers-0.6.2.1" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 vertex)) :+: C1 ('MetaCons "CyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [vertex])))

type Rep1 SCC

Defined in Data.Graph

type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.6.2.1" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "CyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 [])))

cycles :: Graph a -> [[a]]

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

broken :: 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.

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

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

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

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

closure :: 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.

revClosure :: 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.

topSort :: Graph a -> [a]

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

revTopSort :: Graph a -> [a]

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

Conversions

Maps

toMap :: 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) (toList m).

Lists

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

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

toList :: Graph a -> [a]

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

keys :: Graph a -> [Key a]

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

Sets

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

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

Graphs

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

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

Node type

data Node k a

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

Constructors

N a k [k]

Instances

Functor (Node k)

Defined in Distribution.Compat.Graph

Methods

fmap :: (a -> b) -> Node k a -> Node k b

(<$) :: a -> Node k b -> Node k a

(Eq a, Eq k) => Eq (Node k a)

Defined in Distribution.Compat.Graph

Methods

(==) :: Node k a -> Node k a -> Bool

(/=) :: Node k a -> Node k a -> Bool

(Show a, Show k) => Show (Node k a)

Defined in Distribution.Compat.Graph

Methods

showsPrec :: Int -> Node k a -> ShowS

show :: Node k a -> String

showList :: [Node k a] -> ShowS

Ord k => IsNode (Node k a)

Defined in Distribution.Compat.Graph

Associated Types

type Key (Node k a)

Methods

nodeKey :: Node k a -> Key (Node k a)

nodeNeighbors :: Node k a -> [Key (Node k a)]

type Key (Node k a)

Defined in Distribution.Compat.Graph

type Key (Node k a) = k

nodeValue :: Node k a -> a

Get the value from a Node.