HaskellForMaths-0.4.8: Combinatorics, group theory, commutative algebra, non-commutative algebra

Safe HaskellSafe-Inferred
LanguageHaskell98

Math.Combinatorics.Digraph

Description

A module for working with directed graphs (digraphs). Some of the functions are specifically for working with directed acyclic graphs (DAGs), that is, directed graphs containing no cycles.

Synopsis

Documentation

data Digraph v Source

A digraph is represented as DG vs es, where vs is the list of vertices, and es is the list of edges. Edges are directed: an edge (u,v) means an edge from u to v. A digraph is considered to be in normal form if both es and vs are in ascending order. This is the preferred form, and some functions will only work for digraphs in normal form.

Constructors

DG [v] [(v, v)] 

Instances

Functor Digraph 
Eq v => Eq (Digraph v) 
Ord v => Ord (Digraph v) 
Show v => Show (Digraph v) 

nf :: Ord v => Digraph v -> Digraph v Source

vertices :: Digraph t -> [t] Source

edges :: Digraph t -> [(t, t)] Source

predecessors :: Eq t => Digraph t -> t -> [t] Source

successors :: Eq t => Digraph t -> t -> [t] Source

adjLists :: Ord a => Digraph a -> (Map a [a], Map a [a]) Source

digraphIsos1 :: (Eq a1, Eq a) => Digraph a -> Digraph a1 -> [[(a, a1)]] Source

digraphIsos2 :: (Ord k1, Ord k) => Digraph k -> Digraph k1 -> [[(k, k1)]] Source

isDAG :: Ord a => Digraph a -> Bool Source

dagIsos :: (Ord a1, Ord a) => Digraph a -> Digraph a1 -> [[(a, a1)]] Source

isDagIso :: (Ord a, Ord b) => Digraph a -> Digraph b -> Bool Source

Are the two DAGs isomorphic?

perms :: [a] -> [[a]] Source

isoRepDAG2 :: (Ord t1, Ord t, Num t1, Enum t1) => Digraph t -> [(t, t1)] Source

isoRepDAG :: Ord a => Digraph a -> Digraph Int Source

Given a directed acyclic graph (DAG), return a canonical representative for its isomorphism class. isoRepDAG dag is isomorphic to dag. It follows that if isoRepDAG dagA == isoRepDAG dagB then dagA is isomorphic to dagB. Conversely, isoRepDAG dag is the minimal element in the isomorphism class, subject to some constraints. It follows that if dagA is isomorphic to dagB, then isoRepDAG dagA == isoRepDAG dagB.

The algorithm of course is faster on some DAGs than others: roughly speaking, it prefers "tall" DAGs (long chains) to "wide" DAGs (long antichains), and it prefers asymmetric DAGs (ie those with smaller automorphism groups).