{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

{-|
Module      : Data.Matroid.Graphic
Description : 
Copyright   : (c) Immanuel Albrecht, 2020-202x
License     : BSD-3
Maintainer  : mail@immanuel-albrecht.de
Stability   : experimental
Portability : POSIX

This module provides implementations of graphic matroids.

-}

module Data.Matroid.Graphic
  ( GraphicMatroid
  , fromGraph
  , namedFromGraph
  , fromGraph'
  , mK
  ) where 

import Data.Set (Set)
import qualified Data.Set as S

import Data.Map (Map)
import qualified Data.Map as M

import Data.Matroid.Typeclass

-- | data type representing the cycle matroid (aka. polygon matroid) of a (multi-)graph
data GraphicMatroid v a = 
    MG String
       -- ^ given name of the matroid
       (Set a) 
       -- ^ ground set of M(G) = E for a (multi-)graph G = (V,E)
       (a -> (v,v)) 
       {- ^ map that maps the edge e to the set of its incident vertices {u,v}; 
            the order is ignored, and {v} is represented by (v,v) -}
         

instance Show a => Show (GraphicMatroid v a) where
    show :: GraphicMatroid v a -> String
show (MG String
name Set a
_ a -> (v, v)
_) = String
name
            
-- | data type to keep track of forrests in a (multi-)graph
data Forrest v a = F 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 -}
            deriving (Int -> Forrest v a -> ShowS
[Forrest v a] -> ShowS
Forrest v a -> String
(Int -> Forrest v a -> ShowS)
-> (Forrest v a -> String)
-> ([Forrest v a] -> ShowS)
-> Show (Forrest v a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v a. (Show v, Show a) => Int -> Forrest v a -> ShowS
forall v a. (Show v, Show a) => [Forrest v a] -> ShowS
forall v a. (Show v, Show a) => Forrest v a -> String
showList :: [Forrest v a] -> ShowS
$cshowList :: forall v a. (Show v, Show a) => [Forrest v a] -> ShowS
show :: Forrest v a -> String
$cshow :: forall v a. (Show v, Show a) => Forrest v a -> String
showsPrec :: Int -> Forrest v a -> ShowS
$cshowsPrec :: forall v a. (Show v, Show a) => Int -> Forrest v a -> ShowS
Show, Forrest v a -> Forrest v a -> Bool
(Forrest v a -> Forrest v a -> Bool)
-> (Forrest v a -> Forrest v a -> Bool) -> Eq (Forrest v a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v a. (Eq v, Eq a) => Forrest v a -> Forrest v a -> Bool
/= :: Forrest v a -> Forrest v a -> Bool
$c/= :: forall v a. (Eq v, Eq a) => Forrest v a -> Forrest v a -> Bool
== :: Forrest v a -> Forrest v a -> Bool
$c== :: forall v a. (Eq v, Eq a) => Forrest v a -> Forrest v a -> Bool
Eq, Eq (Forrest v a)
Eq (Forrest v a)
-> (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)
-> (Forrest v a -> Forrest v a -> Forrest v a)
-> (Forrest v a -> Forrest v a -> Forrest v a)
-> Ord (Forrest v a)
Forrest v a -> Forrest v a -> Bool
Forrest v a -> Forrest v a -> Ordering
Forrest v a -> Forrest v a -> Forrest v a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall v a. (Ord v, Ord a) => Eq (Forrest v a)
forall v a. (Ord v, Ord a) => Forrest v a -> Forrest v a -> Bool
forall v a.
(Ord v, Ord a) =>
Forrest v a -> Forrest v a -> Ordering
forall v a.
(Ord v, Ord a) =>
Forrest v a -> Forrest v a -> Forrest v a
min :: Forrest v a -> Forrest v a -> Forrest v a
$cmin :: forall v a.
(Ord v, Ord a) =>
Forrest v a -> Forrest v a -> Forrest v a
max :: Forrest v a -> Forrest v a -> Forrest v a
$cmax :: forall v a.
(Ord v, Ord a) =>
Forrest v a -> Forrest v a -> Forrest v a
>= :: Forrest v a -> Forrest v a -> Bool
$c>= :: forall v a. (Ord v, Ord a) => Forrest v a -> Forrest v a -> Bool
> :: Forrest v a -> Forrest v a -> Bool
$c> :: forall v a. (Ord v, Ord a) => Forrest v a -> Forrest v a -> Bool
<= :: Forrest v a -> Forrest v a -> Bool
$c<= :: forall v a. (Ord v, Ord a) => Forrest v a -> Forrest v a -> Bool
< :: Forrest v a -> Forrest v a -> Bool
$c< :: forall v a. (Ord v, Ord a) => Forrest v a -> Forrest v a -> Bool
compare :: Forrest v a -> Forrest v a -> Ordering
$ccompare :: forall v a.
(Ord v, Ord a) =>
Forrest v a -> Forrest v a -> Ordering
$cp1Ord :: forall v a. (Ord v, Ord a) => Eq (Forrest v a)
Ord)

-- | obtain an empty forrest
emptyForrest :: Forrest v a
emptyForrest :: Forrest v a
emptyForrest = Int -> Map v Int -> Map Int (Set a) -> Forrest v a
forall v a. Int -> Map v Int -> Map Int (Set a) -> Forrest v a
F Int
1 Map v Int
forall k a. Map k a
M.empty Map Int (Set a)
forall k a. Map k a
M.empty

{- | 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)
-}
insertEdgeOrGetCycleComponent :: (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; (v,v) represents a loop -} 
                     -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent :: Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent (F Int
n Map v Int
c Map Int (Set a)
t) a
e (v
u,v
v) -- e is a non-loop edge
           | v
u v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v =  Set a -> Either (Set a) (Forrest v a)
forall a b. a -> Either a b
Left (Set a -> Either (Set a) (Forrest v a))
-> Set a -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ a -> Set a
forall a. a -> Set a
S.singleton a
e -- a loop is a single edge cycle
           | Bool -> Bool
not (Bool
udef Bool -> Bool -> Bool
|| Bool
vdef) =           -- e is a new single-edge tree component
                                  let n1 :: Int
n1 = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 
                                      c1 :: Map v Int
c1 = v -> Int -> Map v Int -> Map v Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert v
u Int
n (Map v Int -> Map v Int) -> Map v Int -> Map v Int
forall a b. (a -> b) -> a -> b
$ v -> Int -> Map v Int -> Map v Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert v
v Int
n Map v Int
c
                                      t1 :: Map Int (Set a)
t1 = Int -> Set a -> Map Int (Set a) -> Map Int (Set a)
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
n (a -> Set a
forall a. a -> Set a
S.singleton a
e) Map Int (Set a)
t
                                   in Forrest v a -> Either (Set a) (Forrest v a)
forall a b. b -> Either a b
Right (Forrest v a -> Either (Set a) (Forrest v a))
-> Forrest v a -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ Int -> Map v Int -> Map Int (Set a) -> Forrest v a
forall v a. Int -> Map v Int -> Map Int (Set a) -> Forrest v a
F Int
n1 Map v Int
c1 Map Int (Set a)
t1
            -- at this point, at least udef or vdef is True
           | Maybe Int
uc Maybe Int -> Maybe Int -> Bool
forall a. Eq a => a -> a -> Bool
== Maybe Int
vc =                     -- this edge closes a loop with the tree; udef==vdef==True
                         let Just Int
cid = Maybe Int
uc
                             Just Set a
comp = Int -> Map Int (Set a) -> Maybe (Set a)
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Int
cid Map Int (Set a)
t
                          in Set a -> Either (Set a) (Forrest v a)
forall a b. a -> Either a b
Left (Set a -> Either (Set a) (Forrest v a))
-> Set a -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
e Set a
comp
           | Bool
udef Bool -> Bool -> Bool
&& Bool
vdef =                 -- the edge e connects two components of the forrest
                            let Just Int
uid = Maybe Int
uc
                                Just Int
vid = Maybe Int
vc
                                Just Set a
ut = Int -> Map Int (Set a) -> Maybe (Set a)
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Int
uid Map Int (Set a)
t
                                Just Set a
vt = Int -> Map Int (Set a) -> Maybe (Set a)
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Int
vid Map Int (Set a)
t
                                prj :: Int -> Int
prj Int
xid 
                                    | Int
xid Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
vid = Int
uid -- map the component id of v to u
                                    | Bool
otherwise = Int
xid
                                c1 :: Map v Int
c1 = (Int -> Int) -> Map v Int -> Map v Int
forall a b k. (a -> b) -> Map k a -> Map k b
M.map Int -> Int
prj Map v Int
c 
                                uvt :: Set a
uvt = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
e (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a
ut Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set a
vt
                                t1 :: Map Int (Set a)
t1 = Int -> Set a -> Map Int (Set a) -> Map Int (Set a)
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
uid Set a
uvt (Map Int (Set a) -> Map Int (Set a))
-> Map Int (Set a) -> Map Int (Set a)
forall a b. (a -> b) -> a -> b
$ Int -> Map Int (Set a) -> Map Int (Set a)
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Int
vid Map Int (Set a)
t
                             in Forrest v a -> Either (Set a) (Forrest v a)
forall a b. b -> Either a b
Right (Forrest v a -> Either (Set a) (Forrest v a))
-> Forrest v a -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ Int -> Map v Int -> Map Int (Set a) -> Forrest v a
forall v a. Int -> Map v Int -> Map Int (Set a) -> Forrest v a
F Int
n Map v Int
c1 Map Int (Set a)
t1
            -- at this point, either vdef or udef is True, the other is False
           | Bool
vdef = Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
forall v a.
(Ord v, Ord a) =>
Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent (Int -> Map v Int -> Map Int (Set a) -> Forrest v a
forall v a. Int -> Map v Int -> Map Int (Set a) -> Forrest v a
F Int
n Map v Int
c Map Int (Set a)
t) a
e (v
v,v
u) -- bounce to next case
           | Bool
otherwise =  -- e connects the component of u with the new vertex v
                    let Just Int
uid = Maybe Int
uc
                        Just Set a
ut = Int -> Map Int (Set a) -> Maybe (Set a)
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Int
uid Map Int (Set a)
t
                        c1 :: Map v Int
c1 = v -> Int -> Map v Int -> Map v Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert v
v Int
uid Map v Int
c
                        ut1 :: Set a
ut1 = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
e Set a
ut
                        t1 :: Map Int (Set a)
t1 = Int -> Set a -> Map Int (Set a) -> Map Int (Set a)
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
uid Set a
ut1 Map Int (Set a)
t
                     in Forrest v a -> Either (Set a) (Forrest v a)
forall a b. b -> Either a b
Right (Forrest v a -> Either (Set a) (Forrest v a))
-> Forrest v a -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ Int -> Map v Int -> Map Int (Set a) -> Forrest v a
forall v a. Int -> Map v Int -> Map Int (Set a) -> Forrest v a
F Int
n Map v Int
c1 Map Int (Set a)
t1
           where uc :: Maybe Int
uc = v -> Map v Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup v
u Map v Int
c
                 vc :: Maybe Int
vc = v -> Map v Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup v
v Map v Int
c
                 udef :: Bool
udef = Maybe Int
uc Maybe Int -> Maybe Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Maybe Int
forall a. Maybe a
Nothing
                 vdef :: Bool
vdef = Maybe Int
vc Maybe Int -> Maybe Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Maybe Int
forall a. Maybe a
Nothing

instance (Ord a, Ord v, Show a) => Matroid (GraphicMatroid v) a where
    groundset :: GraphicMatroid v a -> Set a
groundset (MG String
_ Set a
e a -> (v, v)
_) = Set a
e
    showName :: GraphicMatroid v a -> String
showName (MG String
name Set a
_ a -> (v, v)
_) = String
name
    -- | A set of edges of G=(V,E) is independent, if it contains no cycle. 
    indep :: GraphicMatroid v a -> Set a -> Bool
indep (MG String
_ Set a
_ a -> (v, v)
inc) Set a
x = Bool
result
         where (Bool
result,Forrest v a
_) = ((Bool, Forrest v a) -> a -> (Bool, Forrest v a))
-> (Bool, Forrest v a) -> Set a -> (Bool, Forrest v a)
forall a b. (a -> b -> a) -> a -> Set b -> a
S.foldl' (Bool, Forrest v a) -> a -> (Bool, Forrest v a)
step (Bool
True, Forrest v a
forall v a. Forrest v a
emptyForrest) Set a
x
               step :: (Bool, Forrest v a) -> a -> (Bool, Forrest v a)
step (Bool
False, Forrest v a
f) a
_ = (Bool
False, Forrest v a
f) -- propagate failure
               step (Bool
True, Forrest v a
f)  a
e = Forrest v a -> Either (Set a) (Forrest v a) -> (Bool, Forrest v a)
forall b a. b -> Either a b -> (Bool, b)
maybeContinue Forrest v a
f (Either (Set a) (Forrest v a) -> (Bool, Forrest v a))
-> Either (Set a) (Forrest v a) -> (Bool, Forrest v a)
forall a b. (a -> b) -> a -> b
$ Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
forall v a.
(Ord v, Ord a) =>
Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent Forrest v a
f a
e ((v, v) -> Either (Set a) (Forrest v a))
-> (v, v) -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ a -> (v, v)
inc a
e
               maybeContinue :: b -> Either a b -> (Bool, b)
maybeContinue b
f (Left a
_) = (Bool
False, b
f) -- edge e closes a cycle
               maybeContinue b
_ (Right b
f) = (Bool
True, b
f) -- edge e added to the forrest f
    -- | determine a spanning forrest of the vertices incident with the edges x
    basis :: GraphicMatroid v a -> Set a -> Set a
basis (MG String
_ Set a
_ a -> (v, v)
inc) Set a
x = (Set a -> Set a -> Set a) -> Set a -> Map Int (Set a) -> Set a
forall a b k. (a -> b -> a) -> a -> Map k b -> a
M.foldl' Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.union Set a
forall a. Set a
S.empty Map Int (Set a)
component_map
         where F Int
_ Map v Int
_ Map Int (Set a)
component_map = (Forrest v a -> a -> Forrest v a)
-> Forrest v a -> Set a -> Forrest v a
forall a b. (a -> b -> a) -> a -> Set b -> a
S.foldl' Forrest v a -> a -> Forrest v a
step Forrest v a
forall v a. Forrest v a
emptyForrest Set a
x 
               step :: Forrest v a -> a -> Forrest v a
step Forrest v a
f a
e = Forrest v a -> Either (Set a) (Forrest v a) -> Forrest v a
forall p a. p -> Either a p -> p
doContinue Forrest v a
f (Either (Set a) (Forrest v a) -> Forrest v a)
-> Either (Set a) (Forrest v a) -> Forrest v a
forall a b. (a -> b) -> a -> b
$ Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
forall v a.
(Ord v, Ord a) =>
Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent Forrest v a
f a
e ((v, v) -> Either (Set a) (Forrest v a))
-> (v, v) -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ a -> (v, v)
inc a
e
               doContinue :: p -> Either a p -> p
doContinue p
f (Left a
_) = p
f -- edge e closes a cycle, continue with previous forrest
               doContinue p
_ (Right p
f) = p
f -- edge e added to the forrest f
    -- | count the size while determining the spanning forrest
    rk :: GraphicMatroid v a -> Set a -> Int
rk (MG String
_ Set a
_ a -> (v, v)
inc) Set a
x = Int
result
       where (Forrest v a
_,Int
result) = ((Forrest v a, Int) -> a -> (Forrest v a, Int))
-> (Forrest v a, Int) -> Set a -> (Forrest v a, Int)
forall a b. (a -> b -> a) -> a -> Set b -> a
S.foldl' (Forrest v a, Int) -> a -> (Forrest v a, Int)
forall a. Num a => (Forrest v a, a) -> a -> (Forrest v a, a)
step (Forrest v a
forall v a. Forrest v a
emptyForrest, Int
0) Set a
x 
             step :: (Forrest v a, a) -> a -> (Forrest v a, a)
step (Forrest v a
f,a
r) a
e = Forrest v a
-> a -> Either (Set a) (Forrest v a) -> (Forrest v a, a)
forall a a a. Num a => a -> a -> Either a a -> (a, a)
doContinue Forrest v a
f a
r (Either (Set a) (Forrest v a) -> (Forrest v a, a))
-> Either (Set a) (Forrest v a) -> (Forrest v a, a)
forall a b. (a -> b) -> a -> b
$ Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
forall v a.
(Ord v, Ord a) =>
Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent Forrest v a
f a
e ((v, v) -> Either (Set a) (Forrest v a))
-> (v, v) -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ a -> (v, v)
inc a
e
             doContinue :: a -> a -> Either a a -> (a, a)
doContinue a
f a
r (Left a
_) = (a
f,a
r) -- edge e closes a cycle, continue with previous forrest
             doContinue a
_ a
r (Right a
f) = (a
f,a
ra -> a -> a
forall a. Num a => a -> a -> a
+a
1) -- edge e added to the forrest f
    -- | determine a spanning forrest of x, then add all elements from e\x that are either loops or stay within a single component
    cl :: GraphicMatroid v a -> Set a -> Set a
cl (MG String
_ Set a
e a -> (v, v)
inc) Set a
x = Set a
x Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set a
cx
         where F Int
_ Map v Int
component_map Map Int (Set a)
_ = (Forrest v a -> a -> Forrest v a)
-> Forrest v a -> Set a -> Forrest v a
forall a b. (a -> b -> a) -> a -> Set b -> a
S.foldl' Forrest v a -> a -> Forrest v a
step Forrest v a
forall v a. Forrest v a
emptyForrest Set a
x 
               step :: Forrest v a -> a -> Forrest v a
step Forrest v a
f a
g = Forrest v a -> Either (Set a) (Forrest v a) -> Forrest v a
forall p a. p -> Either a p -> p
doContinue Forrest v a
f (Either (Set a) (Forrest v a) -> Forrest v a)
-> Either (Set a) (Forrest v a) -> Forrest v a
forall a b. (a -> b) -> a -> b
$ Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
forall v a.
(Ord v, Ord a) =>
Forrest v a -> a -> (v, v) -> Either (Set a) (Forrest v a)
insertEdgeOrGetCycleComponent Forrest v a
f a
g ((v, v) -> Either (Set a) (Forrest v a))
-> (v, v) -> Either (Set a) (Forrest v a)
forall a b. (a -> b) -> a -> b
$ a -> (v, v)
inc a
g
               doContinue :: p -> Either a p -> p
doContinue p
f (Left a
_) = p
f -- edge e closes a cycle, continue with previous forrest
               doContinue p
_ (Right p
f) = p
f -- edge e added to the forrest f
               cx :: Set a
cx = (a -> Bool) -> Set a -> Set a
forall a. (a -> Bool) -> Set a -> Set a
S.filter a -> Bool
inClosure (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.difference Set a
e Set a
x
               inClosure :: a -> Bool
inClosure a
y = let (v
u,v
v) = a -> (v, v)
inc a
y
                                 loop :: Bool
loop = v
u v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v
                                 uc :: Maybe Int
uc = v -> Map v Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup v
u Map v Int
component_map
                                 vc :: Maybe Int
vc = v -> Map v Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup v
v Map v Int
component_map
                                 single_component :: Bool
single_component = Maybe Int
uc Maybe Int -> Maybe Int -> Bool
forall a. Eq a => a -> a -> Bool
== Maybe Int
vc Bool -> Bool -> Bool
&& (Maybe Int
uc Maybe Int -> Maybe Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Maybe Int
forall a. Maybe a
Nothing)
                             in Bool
loop Bool -> Bool -> Bool
|| Bool
single_component

-- | constructs a GraphicMatroid from a set of (abstract) edges and the incident-vertex map
fromGraph :: (Ord a, Show a) => Set a -- ^ set of edges of the (multi-)graph
                   -> (a -> (v,v))
                   {- ^ map that maps the edge e to the set of its incident vertices {u,v}; 
                        the order is ignored, and {v} is represented by (v,v) -}
                   -> GraphicMatroid v a
fromGraph :: Set a -> (a -> (v, v)) -> GraphicMatroid v a
fromGraph Set a
e = String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
forall a v.
Ord a =>
String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
namedFromGraph (String
"fromGraph (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Set a -> String
forall a. Show a => a -> String
show Set a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") (incidence)") Set a
e

-- | constructs an unnamed GraphicMatroid from a set of (abstract) edges and the incident-vertex map
fromGraph' :: (Ord a) => Set a -- ^ set of edges of the (multi-)graph
                   -> (a -> (v,v))
                   {- ^ map that maps the edge e to the set of its incident vertices {u,v}; 
                        the order is ignored, and {v} is represented by (v,v) -}
                   -> GraphicMatroid v a
fromGraph' :: Set a -> (a -> (v, v)) -> GraphicMatroid v a
fromGraph' = String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
forall a v.
Ord a =>
String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
namedFromGraph String
"M(G)"

-- | constructs a named GraphicMatroid from a set of (abstract) edges and the incident-vertex map
namedFromGraph :: Ord a => 
                      String
                   -- ^ name of the matroid  
                   -> Set a 
                   -- ^ set of edges of the (multi-)graph
                   -> (a -> (v,v))
                   {- ^ map that maps the edge e to the set of its incident vertices {u,v}; 
                        the order is ignored, and {v} is represented by (v,v) -}
                   -> GraphicMatroid v a
namedFromGraph :: String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
namedFromGraph = String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
forall v a. String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
MG


-- | constructs the graphic matroid M(K_n) where K_n is the complete graph on n vertices
mK :: Int -- ^ n = number of vertices in K_n
      -> GraphicMatroid Int (Int,Int)
mK :: Int -> GraphicMatroid Int (Int, Int)
mK Int
n = String
-> Set (Int, Int)
-> ((Int, Int) -> (Int, Int))
-> GraphicMatroid Int (Int, Int)
forall a v.
Ord a =>
String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a
namedFromGraph String
name Set (Int, Int)
e (Int, Int) -> (Int, Int)
forall a. a -> a
id
  where e :: Set (Int, Int)
e = [(Int, Int)] -> Set (Int, Int)
forall a. Ord a => [a] -> Set a
S.fromList [(Int
u,Int
v) | Int
u <- [Int
1..Int
n]
                              , Int
v <- [Int
1..Int
n]
                              , Int
u Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
v]
        name :: String
name = String
"mK " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n