Data.Matroid.Graphic.Internal

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.

Documentation

data Forrest v a

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

(Eq v, Eq a) => Eq (Forrest v a)

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)

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)

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

obtain an empty forrest

insertEdgeOrGetCycleComponent

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)