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

Safe Haskell | Safe
Language | Haskell98

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

- data Digraph v = DG [v] [(v, v)]
- nf :: Ord v => Digraph v -> Digraph v
- vertices :: Digraph v -> [v]
- edges :: Digraph v -> [(v, v)]
- predecessors :: Eq a => Digraph a -> a -> [a]
- successors :: Eq a => Digraph a -> a -> [a]
- adjLists :: Ord a => Digraph a -> (Map a [a], Map a [a])
- digraphIsos1 :: (Eq a1, Eq a2) => Digraph a1 -> Digraph a2 -> [[(a1, a2)]]
- digraphIsos2 :: (Ord k2, Ord k1) => Digraph k2 -> Digraph k1 -> [[(k2, k1)]]
- heightPartitionDAG :: Ord k => Digraph k -> [[k]]
- isDAG :: Ord a => Digraph a -> Bool
- dagIsos :: (Ord a1, Ord a2) => Digraph a2 -> Digraph a1 -> [[(a2, a1)]]
- isDagIso :: (Ord a, Ord b) => Digraph a -> Digraph b -> Bool
- perms :: [a] -> [[a]]
- isoRepDAG1 :: Ord k => Digraph k -> Digraph Int
- isoRepDAG2 :: (Ord b, Num b, Enum b, Ord a) => Digraph a -> [(a, b)]
- isoRepDAG3 :: Ord v => Digraph v -> Digraph Int
- isoRepDAG :: Ord a => Digraph a -> Digraph Int

# 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 Source # |
Instance details Defined in Math.Combinatorics.Digraph Methods fmap :: (a -> b) -> Digraph a -> Digraph b Source # (<$) :: a -> Digraph b -> Digraph a Source #
Eq v => Eq (Digraph v) Source # |
Instance details Defined in Math.Combinatorics.Digraph Methods (==) :: Digraph v -> Digraph v -> Bool Source # (/=) :: Digraph v -> Digraph v -> Bool Source #
Ord v => Ord (Digraph v) Source # |

Instance details

Defined in Math.Combinatorics.Digraph

Methods

compare :: Digraph v -> Digraph v -> Ordering Source #

(<) :: Digraph v -> Digraph v -> Bool Source #

(<=) :: Digraph v -> Digraph v -> Bool Source #

(>) :: Digraph v -> Digraph v -> Bool Source #

(>=) :: Digraph v -> Digraph v -> Bool Source #

max :: Digraph v -> Digraph v -> Digraph v Source #

min :: Digraph v -> Digraph v -> Digraph v Source #

Show v => Show (Digraph v) Source # |
Instance details Defined in Math.Combinatorics.Digraph Methods showsPrec :: Int -> Digraph v -> ShowS Source # show :: Digraph v -> String Source # showList :: [Digraph v] -> ShowS Source #

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

vertices :: Digraph v -> [v] Source #

edges :: Digraph v -> [(v, v)] Source #

predecessors :: Eq a => Digraph a -> a -> [a] Source #

successors :: Eq a => Digraph a -> a -> [a] Source #

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

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

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

heightPartitionDAG :: Ord k => Digraph k -> [[k]] Source #

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

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

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

Are the two DAGs isomorphic?

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

isoRepDAG1 :: Ord k => Digraph k -> Digraph Int Source #

isoRepDAG2 :: (Ord b, Num b, Enum b, Ord a) => Digraph a -> [(a, b)] Source #

isoRepDAG3 :: Ord v => Digraph v -> Digraph Int 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).