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

Safe Haskell | None
Language | Haskell98

Math.Combinatorics.Graph

Description

A module defining a polymorphic data type for (simple, undirected) graphs, together with constructions of some common families of graphs, new from old constructions, and calculation of simple properties of graphs.

Synopsis

- set :: Ord b => [b] -> [b]
- powerset :: [a] -> [[a]]
- data Graph a = G [a] [[a]]
- nf :: Ord a => Graph a -> Graph a
- isSetSystem :: Ord a => [a] -> [[a]] -> Bool
- isGraph :: Ord a => [a] -> [[a]] -> Bool
- graph :: Ord t => ([t], [[t]]) -> Graph t
- toGraph :: Ord a => ([a], [[a]]) -> Graph a
- vertices :: Graph a -> [a]
- edges :: Graph a -> [[a]]
- incidenceMatrix :: (Eq a1, Num a2) => Graph a1 -> [[a2]]
- fromIncidenceMatrix :: (Num t, Enum t, Ord t, Num a, Eq a) => [[a]] -> Graph t
- adjacencyMatrix :: forall a1 a2. (Num a2, Ord a1) => Graph a1 -> [[a2]]
- fromAdjacencyMatrix :: (Eq a, Num a) => [[a]] -> Graph Int
- nullGraph :: Integral t => t -> Graph t
- nullGraph' :: Graph Int
- c :: Integral t => t -> Graph t
- k :: Integral t => t -> Graph t
- kb :: Integral t => t -> t -> Graph t
- kb' :: Integral t => t -> t -> Graph (Either t t)
- q :: Integral t => Int -> Graph t
- q' :: Integral t => Int -> Graph [t]
- tetrahedron :: Graph Integer
- cube :: Graph Integer
- octahedron :: Graph Integer
- dodecahedron :: Graph Integer
- icosahedron :: Graph Integer
- prism :: Int -> Graph (Int, Int)
- to1n :: (Ord t, Num t, Enum t, Ord a) => Graph a -> Graph t
- fromDigits :: Integral a => Graph [a] -> Graph a
- fromBinary :: Integral a => Graph [a] -> Graph a
- petersen :: Graph [Integer]
- complement :: Ord t => Graph t -> Graph t
- restriction :: Eq a => Graph a -> [a] -> Graph a
- inducedSubgraph :: Eq a => Graph a -> [a] -> Graph a
- lineGraph :: (Num t, Enum t, Ord t, Ord a) => Graph a -> Graph t
- lineGraph' :: Ord a => Graph a -> Graph [a]
- cartProd :: (Ord a1, Ord a2) => Graph a2 -> Graph a1 -> Graph (a2, a1)
- order :: Graph a -> Int
- size :: Graph a -> Int
- valency :: Eq a => Graph a -> a -> Int
- valencies :: Eq a => Graph a -> [(Int, Int)]
- valencyPartition :: Eq b => Graph b -> [[b]]
- regularParam :: Eq a => Graph a -> Maybe Int
- isRegular :: Eq t => Graph t -> Bool
- isCubic :: Eq t => Graph t -> Bool
- nbrs :: Eq a => Graph a -> a -> [a]
- findPaths :: Eq a => Graph a -> a -> a -> [[a]]
- distance :: Eq a => Graph a -> a -> a -> Int
- diameter :: Ord t => Graph t -> Int
- findCycles :: Eq a => Graph a -> a -> [[a]]
- girth :: Eq t => Graph t -> Int
- distancePartition :: Ord a => Graph a -> a -> [[a]]
- distancePartitionS :: Ord a => [a] -> Set [a] -> a -> [[a]]
- component :: Ord a => Graph a -> a -> [a]
- isConnected :: Ord t => Graph t -> Bool
- components :: Ord a => Graph a -> [[a]]
- j :: Int -> Int -> Int -> Graph [Int]
- kneser :: Int -> Int -> Graph [Int]
- johnson :: Int -> Int -> Graph [Int]
- bipartiteKneser :: Int -> Int -> Graph (Either [Int] [Int])
- desargues1 :: Graph (Either [Int] [Int])
- gp :: Integral b => b -> b -> Graph (Either b b)
- petersen2 :: Graph (Either Integer Integer)
- prism' :: Integral b => b -> Graph (Either b b)
- durer :: Graph (Either Integer Integer)
- mobiusKantor :: Graph (Either Integer Integer)
- dodecahedron2 :: Graph (Either Integer Integer)
- desargues2 :: Graph (Either Integer Integer)

# Documentation

set :: Ord b => [b] -> [b] Source #

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

data Graph a Source #

Datatype for graphs, represented as a list of vertices and a list of edges. For most purposes, graphs are required to be in normal form. A graph G vs es is in normal form if (i) vs is in ascending order without duplicates, (ii) es is in ascending order without duplicates, (iii) each e in es is a 2-element list [x,y], x<y

Constructors

G [a] [[a]] |

#### Instances

Instances details

Functor Graph Source # |
Instance details Defined in Math.Combinatorics.Graph Methods fmap :: (a -> b) -> Graph a -> Graph b (<$) :: a -> Graph b -> Graph a
Eq a => Eq (Graph a) Source # |
Instance details Defined in Math.Combinatorics.Graph Methods (==) :: Graph a -> Graph a -> Bool (/=) :: Graph a -> Graph a -> Bool
Ord a => Ord (Graph a) Source # |
Instance details Defined in Math.Combinatorics.Graph Methods compare :: Graph a -> Graph a -> Ordering (<) :: Graph a -> Graph a -> Bool (<=) :: Graph a -> Graph a -> Bool (>) :: Graph a -> Graph a -> Bool (>=) :: Graph a -> Graph a -> Bool max :: Graph a -> Graph a -> Graph a min :: Graph a -> Graph a -> Graph a
Show a => Show (Graph a) Source # |
Instance details Defined in Math.Combinatorics.Graph Methods showsPrec :: Int -> Graph a -> ShowS show :: Graph a -> String showList :: [Graph a] -> ShowS

nf :: Ord a => Graph a -> Graph a Source #

Convert a graph to normal form. The input is assumed to be a valid graph apart from order

isSetSystem :: Ord a => [a] -> [[a]] -> Bool Source #

isGraph :: Ord a => [a] -> [[a]] -> Bool Source #

graph :: Ord t => ([t], [[t]]) -> Graph t Source #

Safe constructor for graph from lists of vertices and edges. graph (vs,es) checks that vs and es are valid before returning the graph.

toGraph :: Ord a => ([a], [[a]]) -> Graph a Source #

vertices :: Graph a -> [a] Source #

edges :: Graph a -> [[a]] Source #

incidenceMatrix :: (Eq a1, Num a2) => Graph a1 -> [[a2]] Source #

fromIncidenceMatrix :: (Num t, Enum t, Ord t, Num a, Eq a) => [[a]] -> Graph t Source #

adjacencyMatrix :: forall a1 a2. (Num a2, Ord a1) => Graph a1 -> [[a2]] Source #

fromAdjacencyMatrix :: (Eq a, Num a) => [[a]] -> Graph Int Source #

nullGraph :: Integral t => t -> Graph t Source #

The null graph on n vertices is the graph with no edges

nullGraph' :: Graph Int Source #

The null graph, with no vertices or edges

c :: Integral t => t -> Graph t Source #

c n is the cyclic graph on n vertices

k :: Integral t => t -> Graph t Source #

k n is the complete graph on n vertices

kb :: Integral t => t -> t -> Graph t Source #

kb m n is the complete bipartite graph on m and n vertices

kb' :: Integral t => t -> t -> Graph (Either t t) Source #

kb' m n is the complete bipartite graph on m left and n right vertices

q :: Integral t => Int -> Graph t Source #

q k is the graph of the k-cube

q' :: Integral t => Int -> Graph [t] Source #

tetrahedron :: Graph Integer Source #

cube :: Graph Integer Source #

octahedron :: Graph Integer Source #

dodecahedron :: Graph Integer Source #

icosahedron :: Graph Integer Source #

prism :: Int -> Graph (Int, Int) Source #

to1n :: (Ord t, Num t, Enum t, Ord a) => Graph a -> Graph t Source #

fromDigits :: Integral a => Graph [a] -> Graph a Source #

Given a graph with vertices which are lists of small integers, eg [1,2,3], return a graph with vertices which are the numbers obtained by interpreting these as digits, eg 123. The caller is responsible for ensuring that this makes sense (eg that the small integers are all < 10)

fromBinary :: Integral a => Graph [a] -> Graph a Source #

Given a graph with vertices which are lists of 0s and 1s, return a graph with vertices which are the numbers obtained by interpreting these as binary digits. For example, [1,1,0] -> 6.

petersen :: Graph [Integer] Source #

complement :: Ord t => Graph t -> Graph t Source #

restriction :: Eq a => Graph a -> [a] -> Graph a Source #

The restriction of a graph to a subset of the vertices

inducedSubgraph :: Eq a => Graph a -> [a] -> Graph a Source #

lineGraph :: (Num t, Enum t, Ord t, Ord a) => Graph a -> Graph t Source #

lineGraph' :: Ord a => Graph a -> Graph [a] Source #

cartProd :: (Ord a1, Ord a2) => Graph a2 -> Graph a1 -> Graph (a2, a1) Source #

order :: Graph a -> Int Source #

size :: Graph a -> Int Source #

valency :: Eq a => Graph a -> a -> Int Source #

valencies :: Eq a => Graph a -> [(Int, Int)] Source #

valencyPartition :: Eq b => Graph b -> [[b]] Source #

regularParam :: Eq a => Graph a -> Maybe Int Source #

isRegular :: Eq t => Graph t -> Bool Source #

A graph is regular if all vertices have the same valency (degree)

isCubic :: Eq t => Graph t -> Bool Source #

A 3-regular graph is called a cubic graph

nbrs :: Eq a => Graph a -> a -> [a] Source #

findPaths :: Eq a => Graph a -> a -> a -> [[a]] Source #

distance :: Eq a => Graph a -> a -> a -> Int Source #

Within a graph G, the distance d(u,v) between vertices u, v is length of the shortest path from u to v

diameter :: Ord t => Graph t -> Int Source #

The diameter of a graph is maximum distance between two distinct vertices

findCycles :: Eq a => Graph a -> a -> [[a]] Source #

girth :: Eq t => Graph t -> Int Source #

The girth of a graph is the size of the smallest cycle that it contains. Note: If the graph contains no cycles, we return -1, representing infinity.

distancePartition :: Ord a => Graph a -> a -> [[a]] Source #

distancePartitionS :: Ord a => [a] -> Set [a] -> a -> [[a]] Source #

component :: Ord a => Graph a -> a -> [a] Source #

isConnected :: Ord t => Graph t -> Bool Source #

Is the graph connected?

components :: Ord a => Graph a -> [[a]] Source #

j :: Int -> Int -> Int -> Graph [Int] Source #

kneser :: Int -> Int -> Graph [Int] Source #

kneser n k returns the kneser graph KG n,k - whose vertices are the k-element subsets of [1..n], with edges between disjoint subsets

johnson :: Int -> Int -> Graph [Int] Source #

bipartiteKneser :: Int -> Int -> Graph (Either [Int] [Int]) Source #

desargues1 :: Graph (Either [Int] [Int]) Source #

gp :: Integral b => b -> b -> Graph (Either b b) Source #

petersen2 :: Graph (Either Integer Integer) Source #

prism' :: Integral b => b -> Graph (Either b b) Source #

durer :: Graph (Either Integer Integer) Source #

mobiusKantor :: Graph (Either Integer Integer) Source #

dodecahedron2 :: Graph (Either Integer Integer) Source #

desargues2 :: Graph (Either Integer Integer) Source #