{-# LANGUAGE DeriveGeneric #-}
module Algebra.Graph.Undirected (
Graph, fromUndirected, toUndirected,
empty, vertex, edge, overlay, connect, vertices, edges, overlays, connects,
foldg,
isSubgraphOf, toRelation,
isEmpty, size, hasVertex, hasEdge, vertexCount, edgeCount, vertexList,
edgeList, vertexSet, edgeSet, adjacencyList, neighbours,
path, circuit, clique, biclique, star, stars, tree, forest,
removeVertex, removeEdge, replaceVertex, mergeVertices, induce, induceJust,
complement
) where
import Algebra.Graph.Internal
import Algebra.Graph.ToGraph (toGraph)
import Control.Applicative (Alternative)
import Control.DeepSeq
import Control.Monad
import Data.Coerce
import Data.List
import GHC.Generics
import Data.Set (Set)
import Data.Tree (Tree, Forest)
import qualified Algebra.Graph as G
import qualified Algebra.Graph.Relation.Symmetric as R
import qualified Data.Set as Set
newtype Graph a = UG (G.Graph a)
deriving (Applicative Graph
Graph a
Applicative Graph
-> (forall a. Graph a)
-> (forall a. Graph a -> Graph a -> Graph a)
-> (forall a. Graph a -> Graph [a])
-> (forall a. Graph a -> Graph [a])
-> Alternative Graph
Graph a -> Graph a -> Graph a
Graph a -> Graph [a]
Graph a -> Graph [a]
forall a. Graph a
forall a. Graph a -> Graph [a]
forall a. Graph a -> Graph a -> Graph a
forall (f :: * -> *).
Applicative f
-> (forall a. f a)
-> (forall a. f a -> f a -> f a)
-> (forall a. f a -> f [a])
-> (forall a. f a -> f [a])
-> Alternative f
many :: Graph a -> Graph [a]
$cmany :: forall a. Graph a -> Graph [a]
some :: Graph a -> Graph [a]
$csome :: forall a. Graph a -> Graph [a]
<|> :: Graph a -> Graph a -> Graph a
$c<|> :: forall a. Graph a -> Graph a -> Graph a
empty :: Graph a
$cempty :: forall a. Graph a
$cp1Alternative :: Applicative Graph
Alternative, Functor Graph
a -> Graph a
Functor Graph
-> (forall a. a -> Graph a)
-> (forall a b. Graph (a -> b) -> Graph a -> Graph b)
-> (forall a b c. (a -> b -> c) -> Graph a -> Graph b -> Graph c)
-> (forall a b. Graph a -> Graph b -> Graph b)
-> (forall a b. Graph a -> Graph b -> Graph a)
-> Applicative Graph
Graph a -> Graph b -> Graph b
Graph a -> Graph b -> Graph a
Graph (a -> b) -> Graph a -> Graph b
(a -> b -> c) -> Graph a -> Graph b -> Graph c
forall a. a -> Graph a
forall a b. Graph a -> Graph b -> Graph a
forall a b. Graph a -> Graph b -> Graph b
forall a b. Graph (a -> b) -> Graph a -> Graph b
forall a b c. (a -> b -> c) -> Graph a -> Graph b -> Graph c
forall (f :: * -> *).
Functor f
-> (forall a. a -> f a)
-> (forall a b. f (a -> b) -> f a -> f b)
-> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
-> (forall a b. f a -> f b -> f b)
-> (forall a b. f a -> f b -> f a)
-> Applicative f
<* :: Graph a -> Graph b -> Graph a
$c<* :: forall a b. Graph a -> Graph b -> Graph a
*> :: Graph a -> Graph b -> Graph b
$c*> :: forall a b. Graph a -> Graph b -> Graph b
liftA2 :: (a -> b -> c) -> Graph a -> Graph b -> Graph c
$cliftA2 :: forall a b c. (a -> b -> c) -> Graph a -> Graph b -> Graph c
<*> :: Graph (a -> b) -> Graph a -> Graph b
$c<*> :: forall a b. Graph (a -> b) -> Graph a -> Graph b
pure :: a -> Graph a
$cpure :: forall a. a -> Graph a
$cp1Applicative :: Functor Graph
Applicative, a -> Graph b -> Graph a
(a -> b) -> Graph a -> Graph b
(forall a b. (a -> b) -> Graph a -> Graph b)
-> (forall a b. a -> Graph b -> Graph a) -> Functor Graph
forall a b. a -> Graph b -> Graph a
forall a b. (a -> b) -> Graph a -> Graph b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Graph b -> Graph a
$c<$ :: forall a b. a -> Graph b -> Graph a
fmap :: (a -> b) -> Graph a -> Graph b
$cfmap :: forall a b. (a -> b) -> Graph a -> Graph b
Functor, (forall x. Graph a -> Rep (Graph a) x)
-> (forall x. Rep (Graph a) x -> Graph a) -> Generic (Graph a)
forall x. Rep (Graph a) x -> Graph a
forall x. Graph a -> Rep (Graph a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Graph a) x -> Graph a
forall a x. Graph a -> Rep (Graph a) x
$cto :: forall a x. Rep (Graph a) x -> Graph a
$cfrom :: forall a x. Graph a -> Rep (Graph a) x
Generic, Applicative Graph
a -> Graph a
Applicative Graph
-> (forall a b. Graph a -> (a -> Graph b) -> Graph b)
-> (forall a b. Graph a -> Graph b -> Graph b)
-> (forall a. a -> Graph a)
-> Monad Graph
Graph a -> (a -> Graph b) -> Graph b
Graph a -> Graph b -> Graph b
forall a. a -> Graph a
forall a b. Graph a -> Graph b -> Graph b
forall a b. Graph a -> (a -> Graph b) -> Graph b
forall (m :: * -> *).
Applicative m
-> (forall a b. m a -> (a -> m b) -> m b)
-> (forall a b. m a -> m b -> m b)
-> (forall a. a -> m a)
-> Monad m
return :: a -> Graph a
$creturn :: forall a. a -> Graph a
>> :: Graph a -> Graph b -> Graph b
$c>> :: forall a b. Graph a -> Graph b -> Graph b
>>= :: Graph a -> (a -> Graph b) -> Graph b
$c>>= :: forall a b. Graph a -> (a -> Graph b) -> Graph b
$cp1Monad :: Applicative Graph
Monad, Monad Graph
Alternative Graph
Graph a
Alternative Graph
-> Monad Graph
-> (forall a. Graph a)
-> (forall a. Graph a -> Graph a -> Graph a)
-> MonadPlus Graph
Graph a -> Graph a -> Graph a
forall a. Graph a
forall a. Graph a -> Graph a -> Graph a
forall (m :: * -> *).
Alternative m
-> Monad m
-> (forall a. m a)
-> (forall a. m a -> m a -> m a)
-> MonadPlus m
mplus :: Graph a -> Graph a -> Graph a
$cmplus :: forall a. Graph a -> Graph a -> Graph a
mzero :: Graph a
$cmzero :: forall a. Graph a
$cp2MonadPlus :: Monad Graph
$cp1MonadPlus :: Alternative Graph
MonadPlus, Graph a -> ()
(Graph a -> ()) -> NFData (Graph a)
forall a. NFData a => Graph a -> ()
forall a. (a -> ()) -> NFData a
rnf :: Graph a -> ()
$crnf :: forall a. NFData a => Graph a -> ()
NFData)
instance (Show a, Ord a) => Show (Graph a) where
show :: Graph a -> String
show = Relation a -> String
forall a. Show a => a -> String
show (Relation a -> String)
-> (Graph a -> Relation a) -> Graph a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
instance Num a => Num (Graph a) where
fromInteger :: Integer -> Graph a
fromInteger = a -> Graph a
forall a. a -> Graph a
vertex (a -> Graph a) -> (Integer -> a) -> Integer -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> a
forall a. Num a => Integer -> a
fromInteger
+ :: Graph a -> Graph a -> Graph a
(+) = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay
* :: Graph a -> Graph a -> Graph a
(*) = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
connect
signum :: Graph a -> Graph a
signum = Graph a -> Graph a -> Graph a
forall a b. a -> b -> a
const Graph a
forall a. Graph a
empty
abs :: Graph a -> Graph a
abs = Graph a -> Graph a
forall a. a -> a
id
negate :: Graph a -> Graph a
negate = Graph a -> Graph a
forall a. a -> a
id
instance Ord a => Eq (Graph a) where
== :: Graph a -> Graph a -> Bool
(==) = Graph a -> Graph a -> Bool
forall a. Ord a => Graph a -> Graph a -> Bool
eqR
instance Ord a => Ord (Graph a) where
compare :: Graph a -> Graph a -> Ordering
compare = Graph a -> Graph a -> Ordering
forall a. Ord a => Graph a -> Graph a -> Ordering
ordR
eqR :: Ord a => Graph a -> Graph a -> Bool
eqR :: Graph a -> Graph a -> Bool
eqR Graph a
x Graph a
y = Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation Graph a
x Relation a -> Relation a -> Bool
forall a. Eq a => a -> a -> Bool
== Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation Graph a
y
ordR :: Ord a => Graph a -> Graph a -> Ordering
ordR :: Graph a -> Graph a -> Ordering
ordR Graph a
x Graph a
y = Relation a -> Relation a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation Graph a
x) (Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation Graph a
y)
toUndirected :: G.Graph a -> Graph a
toUndirected :: Graph a -> Graph a
toUndirected = Graph a -> Graph a
coerce
fromUndirected :: Ord a => Graph a -> G.Graph a
fromUndirected :: Graph a -> Graph a
fromUndirected = Relation a -> Graph a
forall t. ToGraph t => t -> Graph (ToVertex t)
toGraph (Relation a -> Graph a)
-> (Graph a -> Relation a) -> Graph a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
empty :: Graph a
empty :: Graph a
empty = Graph a -> Graph a
forall (f :: * -> *) (g :: * -> *) x. Coercible f g => f x -> g x
coerce00 Graph a
forall a. Graph a
G.empty
{-# INLINE empty #-}
vertex :: a -> Graph a
vertex :: a -> Graph a
vertex = (a -> Graph a) -> a -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 a -> Graph a
forall a. a -> Graph a
G.vertex
{-# INLINE vertex #-}
edge :: a -> a -> Graph a
edge :: a -> a -> Graph a
edge = (a -> a -> Graph a) -> a -> a -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> c -> f x) -> b -> d -> g x
coerce20 a -> a -> Graph a
forall a. a -> a -> Graph a
G.edge
{-# INLINE edge #-}
overlay :: Graph a -> Graph a -> Graph a
overlay :: Graph a -> Graph a -> Graph a
overlay = (Graph a -> Graph a -> Graph a) -> Graph a -> Graph a -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> c -> f x) -> b -> d -> g x
coerce20 Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
G.overlay
{-# INLINE overlay #-}
connect :: Graph a -> Graph a -> Graph a
connect :: Graph a -> Graph a -> Graph a
connect = (Graph a -> Graph a -> Graph a) -> Graph a -> Graph a -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> c -> f x) -> b -> d -> g x
coerce20 Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
G.connect
{-# INLINE connect #-}
vertices :: [a] -> Graph a
vertices :: [a] -> Graph a
vertices = ([a] -> Graph a) -> [a] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [a] -> Graph a
forall a. [a] -> Graph a
G.vertices
{-# INLINE vertices #-}
edges :: [(a, a)] -> Graph a
edges :: [(a, a)] -> Graph a
edges = ([(a, a)] -> Graph a) -> [(a, a)] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [(a, a)] -> Graph a
forall a. [(a, a)] -> Graph a
G.edges
{-# INLINE edges #-}
overlays :: [Graph a] -> Graph a
overlays :: [Graph a] -> Graph a
overlays = ([Graph a] -> Graph a) -> [Graph a] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [Graph a] -> Graph a
forall a. [Graph a] -> Graph a
G.overlays
{-# INLINE overlays #-}
connects :: [Graph a] -> Graph a
connects :: [Graph a] -> Graph a
connects = ([Graph a] -> Graph a) -> [Graph a] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [Graph a] -> Graph a
forall a. [Graph a] -> Graph a
G.connects
{-# INLINE connects #-}
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg = (b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b)
-> b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
forall b a.
(b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b)
-> b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
coerce b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
G.foldg
where
coerce :: (b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> G.Graph a -> b)
-> (b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b)
coerce :: (b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b)
-> b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
coerce = (b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b)
-> b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
Data.Coerce.coerce
{-# INLINE foldg #-}
isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool
isSubgraphOf :: Graph a -> Graph a -> Bool
isSubgraphOf Graph a
x Graph a
y = Relation a -> Relation a -> Bool
forall a. Ord a => Relation a -> Relation a -> Bool
R.isSubgraphOf (Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation Graph a
x) (Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation Graph a
y)
{-# NOINLINE [1] isSubgraphOf #-}
toRelation :: Ord a => Graph a -> R.Relation a
toRelation :: Graph a -> Relation a
toRelation = Relation a
-> (a -> Relation a)
-> (Relation a -> Relation a -> Relation a)
-> (Relation a -> Relation a -> Relation a)
-> Graph a
-> Relation a
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Relation a
forall a. Relation a
R.empty a -> Relation a
forall a. a -> Relation a
R.vertex Relation a -> Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a -> Relation a
R.overlay Relation a -> Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a -> Relation a
R.connect
{-# INLINE toRelation #-}
isEmpty :: Graph a -> Bool
isEmpty :: Graph a -> Bool
isEmpty = (Graph a -> Bool) -> Graph a -> Bool
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(f x -> a) -> g x -> b
coerce01 Graph a -> Bool
forall a. Graph a -> Bool
G.isEmpty
{-# INLINE isEmpty #-}
size :: Graph a -> Int
size :: Graph a -> Int
size = (Graph a -> Int) -> Graph a -> Int
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(f x -> a) -> g x -> b
coerce01 Graph a -> Int
forall a. Graph a -> Int
G.size
{-# INLINE size #-}
hasVertex :: Eq a => a -> Graph a -> Bool
hasVertex :: a -> Graph a -> Bool
hasVertex = (a -> Graph a -> Bool) -> a -> Graph a -> Bool
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> f x -> c) -> b -> g x -> d
coerce11 a -> Graph a -> Bool
forall a. Eq a => a -> Graph a -> Bool
G.hasVertex
{-# INLINE hasVertex #-}
{-# SPECIALISE hasVertex :: Int -> Graph Int -> Bool #-}
hasEdge :: Eq a => a -> a -> Graph a -> Bool
hasEdge :: a -> a -> Graph a -> Bool
hasEdge a
s a
t (UG Graph a
g) = a -> a -> Graph a -> Bool
forall a. Eq a => a -> a -> Graph a -> Bool
G.hasEdge a
s a
t Graph a
g Bool -> Bool -> Bool
|| a -> a -> Graph a -> Bool
forall a. Eq a => a -> a -> Graph a -> Bool
G.hasEdge a
t a
s Graph a
g
{-# INLINE hasEdge #-}
{-# SPECIALISE hasEdge :: Int -> Int -> Graph Int -> Bool #-}
vertexCount :: Ord a => Graph a -> Int
vertexCount :: Graph a -> Int
vertexCount = (Graph a -> Int) -> Graph a -> Int
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(f x -> a) -> g x -> b
coerce01 Graph a -> Int
forall a. Ord a => Graph a -> Int
G.vertexCount
{-# INLINE [1] vertexCount #-}
edgeCount :: Ord a => Graph a -> Int
edgeCount :: Graph a -> Int
edgeCount = Relation a -> Int
forall a. Ord a => Relation a -> Int
R.edgeCount (Relation a -> Int) -> (Graph a -> Relation a) -> Graph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
{-# INLINE [1] edgeCount #-}
vertexList :: Ord a => Graph a -> [a]
vertexList :: Graph a -> [a]
vertexList = (Graph a -> [a]) -> Graph a -> [a]
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(f x -> a) -> g x -> b
coerce01 Graph a -> [a]
forall a. Ord a => Graph a -> [a]
G.vertexList
{-# INLINE [1] vertexList #-}
edgeList :: Ord a => Graph a -> [(a, a)]
edgeList :: Graph a -> [(a, a)]
edgeList = Relation a -> [(a, a)]
forall a. Ord a => Relation a -> [(a, a)]
R.edgeList (Relation a -> [(a, a)])
-> (Graph a -> Relation a) -> Graph a -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
{-# INLINE [1] edgeList #-}
vertexSet :: Ord a => Graph a -> Set a
vertexSet :: Graph a -> Set a
vertexSet = (Graph a -> Set a) -> Graph a -> Set a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(f x -> a) -> g x -> b
coerce01 Graph a -> Set a
forall a. Ord a => Graph a -> Set a
G.vertexSet
{-# INLINE vertexSet #-}
edgeSet :: Ord a => Graph a -> Set (a, a)
edgeSet :: Graph a -> Set (a, a)
edgeSet = Relation a -> Set (a, a)
forall a. Ord a => Relation a -> Set (a, a)
R.edgeSet (Relation a -> Set (a, a))
-> (Graph a -> Relation a) -> Graph a -> Set (a, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
{-# INLINE [1] edgeSet #-}
adjacencyList :: Ord a => Graph a -> [(a, [a])]
adjacencyList :: Graph a -> [(a, [a])]
adjacencyList = Relation a -> [(a, [a])]
forall a. Eq a => Relation a -> [(a, [a])]
R.adjacencyList (Relation a -> [(a, [a])])
-> (Graph a -> Relation a) -> Graph a -> [(a, [a])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
{-# INLINE adjacencyList #-}
{-# SPECIALISE adjacencyList :: Graph Int -> [(Int, [Int])] #-}
neighbours :: Ord a => a -> Graph a -> Set a
neighbours :: a -> Graph a -> Set a
neighbours a
x = a -> Relation a -> Set a
forall a. Ord a => a -> Relation a -> Set a
R.neighbours a
x (Relation a -> Set a)
-> (Graph a -> Relation a) -> Graph a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Relation a
forall a. Ord a => Graph a -> Relation a
toRelation
{-# INLINE neighbours #-}
path :: [a] -> Graph a
path :: [a] -> Graph a
path = ([a] -> Graph a) -> [a] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [a] -> Graph a
forall a. [a] -> Graph a
G.path
{-# INLINE path #-}
circuit :: [a] -> Graph a
circuit :: [a] -> Graph a
circuit = ([a] -> Graph a) -> [a] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [a] -> Graph a
forall a. [a] -> Graph a
G.circuit
{-# INLINE circuit #-}
clique :: [a] -> Graph a
clique :: [a] -> Graph a
clique = ([a] -> Graph a) -> [a] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [a] -> Graph a
forall a. [a] -> Graph a
G.clique
{-# INLINE clique #-}
biclique :: [a] -> [a] -> Graph a
biclique :: [a] -> [a] -> Graph a
biclique = ([a] -> [a] -> Graph a) -> [a] -> [a] -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> c -> f x) -> b -> d -> g x
coerce20 [a] -> [a] -> Graph a
forall a. [a] -> [a] -> Graph a
G.biclique
{-# INLINE biclique #-}
star :: a -> [a] -> Graph a
star :: a -> [a] -> Graph a
star = (a -> [a] -> Graph a) -> a -> [a] -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> c -> f x) -> b -> d -> g x
coerce20 a -> [a] -> Graph a
forall a. a -> [a] -> Graph a
G.star
{-# INLINE star #-}
stars :: [(a, [a])] -> Graph a
stars :: [(a, [a])] -> Graph a
stars = ([(a, [a])] -> Graph a) -> [(a, [a])] -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 [(a, [a])] -> Graph a
forall a. [(a, [a])] -> Graph a
G.stars
{-# INLINE stars #-}
tree :: Tree a -> Graph a
tree :: Tree a -> Graph a
tree = (Tree a -> Graph a) -> Tree a -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 Tree a -> Graph a
forall a. Tree a -> Graph a
G.tree
{-# INLINE tree #-}
forest :: Forest a -> Graph a
forest :: Forest a -> Graph a
forest = (Forest a -> Graph a) -> Forest a -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 Forest a -> Graph a
forall a. Forest a -> Graph a
G.forest
{-# INLINE forest #-}
removeVertex :: Eq a => a -> Graph a -> Graph a
removeVertex :: a -> Graph a -> Graph a
removeVertex = (a -> Graph a -> Graph a) -> a -> Graph a -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> f x -> c) -> b -> g x -> d
coerce11 a -> Graph a -> Graph a
forall a. Eq a => a -> Graph a -> Graph a
G.removeVertex
{-# INLINE removeVertex #-}
{-# SPECIALISE removeVertex :: Int -> Graph Int -> Graph Int #-}
removeEdge :: Eq a => a -> a -> Graph a -> Graph a
removeEdge :: a -> a -> Graph a -> Graph a
removeEdge a
s a
t = (Graph a -> Graph a) -> Graph a -> Graph a
Data.Coerce.coerce ((Graph a -> Graph a) -> Graph a -> Graph a)
-> (Graph a -> Graph a) -> Graph a -> Graph a
forall a b. (a -> b) -> a -> b
$ a -> a -> Graph a -> Graph a
forall a. Eq a => a -> a -> Graph a -> Graph a
G.removeEdge a
s a
t (Graph a -> Graph a) -> (Graph a -> Graph a) -> Graph a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> Graph a -> Graph a
forall a. Eq a => a -> a -> Graph a -> Graph a
G.removeEdge a
t a
s
{-# INLINE removeEdge #-}
{-# SPECIALISE removeEdge :: Int -> Int -> Graph Int -> Graph Int #-}
replaceVertex :: Eq a => a -> a -> Graph a -> Graph a
replaceVertex :: a -> a -> Graph a -> Graph a
replaceVertex = (a -> a -> Graph a -> Graph a) -> a -> a -> Graph a -> Graph a
forall a b c d p q (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible p q, Coercible f g) =>
(a -> c -> f x -> p) -> b -> d -> g x -> q
coerce21 a -> a -> Graph a -> Graph a
forall a. Eq a => a -> a -> Graph a -> Graph a
G.replaceVertex
{-# INLINE replaceVertex #-}
{-# SPECIALISE replaceVertex :: Int -> Int -> Graph Int -> Graph Int #-}
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a
mergeVertices = ((a -> Bool) -> a -> Graph a -> Graph a)
-> (a -> Bool) -> a -> Graph a -> Graph a
forall a b c d p q (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible p q, Coercible f g) =>
(a -> c -> f x -> p) -> b -> d -> g x -> q
coerce21 (a -> Bool) -> a -> Graph a -> Graph a
forall a. (a -> Bool) -> a -> Graph a -> Graph a
G.mergeVertices
{-# INLINE mergeVertices #-}
induce :: (a -> Bool) -> Graph a -> Graph a
induce :: (a -> Bool) -> Graph a -> Graph a
induce = ((a -> Bool) -> Graph a -> Graph a)
-> (a -> Bool) -> Graph a -> Graph a
forall a b c d (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible c d, Coercible f g) =>
(a -> c -> f x) -> b -> d -> g x
coerce20 (a -> Bool) -> Graph a -> Graph a
forall a. (a -> Bool) -> Graph a -> Graph a
G.induce
{-# INLINE induce #-}
induceJust :: Graph (Maybe a) -> Graph a
induceJust :: Graph (Maybe a) -> Graph a
induceJust = (Graph (Maybe a) -> Graph a) -> Graph (Maybe a) -> Graph a
forall a b (f :: * -> *) (g :: * -> *) x.
(Coercible a b, Coercible f g) =>
(a -> f x) -> b -> g x
coerce10 Graph (Maybe a) -> Graph a
forall a. Graph (Maybe a) -> Graph a
G.induceJust
{-# INLINE induceJust #-}
complement :: Ord a => Graph a -> Graph a
complement :: Graph a -> Graph a
complement Graph a
g = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay ([a] -> Graph a
forall a. [a] -> Graph a
vertices [a]
vsOld) ([(a, a)] -> Graph a
forall a. [(a, a)] -> Graph a
edges ([(a, a)] -> Graph a) -> [(a, a)] -> Graph a
forall a b. (a -> b) -> a -> b
$ Set (a, a) -> [(a, a)]
forall a. Set a -> [a]
Set.toAscList Set (a, a)
esNew)
where
vsOld :: [a]
vsOld = Graph a -> [a]
forall a. Ord a => Graph a -> [a]
vertexList Graph a
g
esOld :: Set (a, a)
esOld = Graph a -> Set (a, a)
forall a. Ord a => Graph a -> Set (a, a)
edgeSet Graph a
g
loops :: Set (a, a)
loops = ((a, a) -> Bool) -> Set (a, a) -> Set (a, a)
forall a. (a -> Bool) -> Set a -> Set a
Set.filter ((a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)) Set (a, a)
esOld
esAll :: Set (a, a)
esAll = [(a, a)] -> Set (a, a)
forall a. Eq a => [a] -> Set a
Set.fromAscList [ (a
x, a
y) | a
x:[a]
ys <- [a] -> [[a]]
forall a. [a] -> [[a]]
tails [a]
vsOld, a
y <- [a]
ys ]
esNew :: Set (a, a)
esNew = Set (a, a) -> Set (a, a) -> Set (a, a)
forall a. Ord a => Set a -> Set a -> Set a
Set.union Set (a, a)
loops (Set (a, a) -> Set (a, a) -> Set (a, a)
forall a. Ord a => Set a -> Set a -> Set a
Set.difference Set (a, a)
esAll Set (a, a)
esOld)