Copyright	(c) Immanuel Albrecht 2020-202x
License	BSD-3
Maintainer	mail@immanuel-albrecht.de
Stability	experimental
Portability	POSIX
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Matroid.Graphic.Internal

Description

This module provides internal helpers used by the graphic matroid module.

Although it is exported, using anything from this module that is not re-exported by another module may (and eventually will) break client side code. The main reason for exporting this is so anyone can inspect internals using haddock; it's a little bit like an open door policy for code.

Synopsis

data Forrest v a = F Int (Map v Int) (Map Int (Set a))
emptyForrest :: Forrest v a
insertEdgeOrGetCycleComponent :: (Ord v, Ord a) => Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)

Documentation

data Forrest v a Source #

data type to keep track of forrests in a (multi-)graph

Constructors

F
Fields Int fresh component id counter (Map v Int) tracks which vertex belongs to which component (Map Int (Set a)) tracks which edges belong to which component

Instances

Instances details

(Eq v, Eq a) => Eq (Forrest v a) Source #
Instance details Defined in Data.Matroid.Graphic.Internal Methods (==) :: Forrest v a -> Forrest v a -> Bool # (/=) :: Forrest v a -> Forrest v a -> Bool #
(Ord v, Ord a) => Ord (Forrest v a) Source #
Instance details Defined in Data.Matroid.Graphic.Internal Methods compare :: Forrest v a -> Forrest v a -> Ordering # (<) :: Forrest v a -> Forrest v a -> Bool # (<=) :: Forrest v a -> Forrest v a -> Bool # (>) :: Forrest v a -> Forrest v a -> Bool # (>=) :: Forrest v a -> Forrest v a -> Bool # max :: Forrest v a -> Forrest v a -> Forrest v a # min :: Forrest v a -> Forrest v a -> Forrest v a #
(Show v, Show a) => Show (Forrest v a) Source #
Instance details Defined in Data.Matroid.Graphic.Internal Methods showsPrec :: Int -> Forrest v a -> ShowS # show :: Forrest v a -> String # showList :: [Forrest v a] -> ShowS #

emptyForrest :: Forrest v a Source #

obtain an empty forrest

insertEdgeOrGetCycleComponent Source #

Arguments

:: (Ord v, Ord a)
=> Forrest v a	forrest to insert into / find the cycle
-> a	name of the edge
-> (v, v)	incidence tuple of the edge; `(x,x)` represents a loop around the vertex `x`
-> Either (Set a) (Forrest v a)

Takes a forrest and tries to add another edge to it.

If possible (Right), then it returns the forrest with the edge added otherwise (Left) returns the component with a cycle after adding e. Please note that for a result Left x, the set x contains a cycle, but it is not necessarily a cycle itself. (It's a cycle with trees on it)