1{-# LANGUAGE ConstrainedClassMethods #-} 2----------------------------------------------------------------------------- 3-- | 4-- Module : Algebra.Graph.ToGraph 5-- Copyright : (c) Andrey Mokhov 2016-2019 6-- License : MIT (see the file LICENSE) 7-- Maintainer : andrey.mokhov@gmail.com 8-- Stability : experimental 9-- 10-- __Alga__ is a library for algebraic construction and manipulation of graphs 11-- in Haskell. See <https://github.com/snowleopard/alga-paper this paper> for the 12-- motivation behind the library, the underlying theory, and implementation details. 13-- 14-- This module defines the type class 'ToGraph' for capturing data types that 15-- can be converted to algebraic graphs. To make an instance of this class you 16-- need to define just a single method ('toGraph' or 'foldg'), which gives you 17-- access to many other useful methods for free (although note that the default 18-- implementations may be suboptimal performance-wise). 19-- 20-- This type class is similar to the standard type class 'Data.Foldable.Foldable' 21-- defined for lists. Furthermore, one can define 'Foldable' methods 'foldMap' 22-- and 'Data.Foldable.toList' using @ToGraph@.'foldg': 23-- 24-- @ 25-- 'foldMap' f = 'foldg' 'mempty' f ('<>') ('<>') 26-- 'Data.Foldable.toList' = 'foldg' [] 'pure' ('++') ('++') 27-- @ 28-- 29-- However, the resulting 'Foldable' instance is problematic. For example, 30-- folding equivalent algebraic graphs @1@ and @1@ + @1@ leads to different 31-- results: 32-- 33-- @ 34-- 'Data.Foldable.toList' (1 ) == [1] 35-- 'Data.Foldable.toList' (1 + 1) == [1, 1] 36-- @ 37-- 38-- To avoid such cases, we do not provide 'Foldable' instances for algebraic 39-- graph datatypes. Furthermore, we require that the four arguments passed to 40-- 'foldg' satisfy the laws of the algebra of graphs. The above definitions 41-- of 'foldMap' and 'Data.Foldable.toList' violate this requirement, for example 42-- @[1] ++ [1] /= [1]@, and are therefore disallowed. 43----------------------------------------------------------------------------- 44module Algebra.Graph.ToGraph ( 45 -- * Type class 46 ToGraph (..), 47 48 -- * Derived functions 49 adjacencyMap, adjacencyIntMap, adjacencyMapTranspose, adjacencyIntMapTranspose 50 ) where 51 52import Data.IntMap (IntMap) 53import Data.IntSet (IntSet) 54import Data.Map (Map) 55import Data.Set (Set) 56import Data.Tree 57 58import qualified Algebra.Graph as G 59import qualified Algebra.Graph.AdjacencyMap as AM 60import qualified Algebra.Graph.AdjacencyMap.Algorithm as AM 61import qualified Algebra.Graph.Labelled as LG 62import qualified Algebra.Graph.Labelled.AdjacencyMap as LAM 63import qualified Algebra.Graph.NonEmpty.AdjacencyMap as NAM 64import qualified Algebra.Graph.AdjacencyIntMap as AIM 65import qualified Algebra.Graph.AdjacencyIntMap.Algorithm as AIM 66import qualified Algebra.Graph.Relation as R 67import qualified Algebra.Graph.Relation.Symmetric as SR 68import qualified Data.IntMap as IntMap 69import qualified Data.IntSet as IntSet 70import qualified Data.Map as Map 71import qualified Data.Set as Set 72 73-- | The 'ToGraph' type class captures data types that can be converted to 74-- algebraic graphs. Instances of this type class should satisfy the laws 75-- specified by the default method definitions. 76class ToGraph t where 77 {-# MINIMAL toGraph | foldg #-} 78 -- | The type of vertices of the resulting graph. 79 type ToVertex t 80 81 -- | Convert a value to the corresponding algebraic graph, see "Algebra.Graph". 82 -- 83 -- @ 84 -- toGraph == 'foldg' 'G.Empty' 'G.Vertex' 'G.Overlay' 'G.Connect' 85 -- @ 86 toGraph :: t -> G.Graph (ToVertex t) 87 toGraph = foldg G.Empty G.Vertex G.Overlay G.Connect 88 89 -- | The method 'foldg' is used for generalised graph folding. It collapses 90 -- a given value by applying the provided graph construction primitives. The 91 -- order of arguments is: empty, vertex, overlay and connect, and it is 92 -- assumed that the arguments satisfy the axioms of the graph algebra. 93 -- 94 -- @ 95 -- foldg == Algebra.Graph.'G.foldg' . 'toGraph' 96 -- @ 97 foldg :: r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r 98 foldg e v o c = G.foldg e v o c . toGraph 99 100 -- | Check if a graph is empty. 101 -- 102 -- @ 103 -- isEmpty == 'foldg' True ('const' False) (&&) (&&) 104 -- @ 105 isEmpty :: t -> Bool 106 isEmpty = foldg True (const False) (&&) (&&) 107 108 -- | Check if a graph contains a given vertex. 109 -- 110 -- @ 111 -- hasVertex x == 'foldg' False (==x) (||) (||) 112 -- @ 113 hasVertex :: Eq (ToVertex t) => ToVertex t -> t -> Bool 114 hasVertex x = foldg False (==x) (||) (||) 115 116 -- | Check if a graph contains a given edge. 117 -- 118 -- @ 119 -- hasEdge x y == Algebra.Graph.'G.hasEdge' x y . 'toGraph' 120 -- @ 121 hasEdge :: Eq (ToVertex t) => ToVertex t -> ToVertex t -> t -> Bool 122 hasEdge x y = G.hasEdge x y . toGraph 123 124 -- | The number of vertices in a graph. 125 -- 126 -- @ 127 -- vertexCount == Set.'Set.size' . 'vertexSet' 128 -- @ 129 vertexCount :: Ord (ToVertex t) => t -> Int 130 vertexCount = Set.size . vertexSet 131 132 -- | The number of edges in a graph. 133 -- 134 -- @ 135 -- edgeCount == Set.'Set.size' . 'edgeSet' 136 -- @ 137 edgeCount :: Ord (ToVertex t) => t -> Int 138 edgeCount = AM.edgeCount . toAdjacencyMap 139 140 -- | The sorted list of vertices of a given graph. 141 -- 142 -- @ 143 -- vertexList == Set.'Set.toAscList' . 'vertexSet' 144 -- @ 145 vertexList :: Ord (ToVertex t) => t -> [ToVertex t] 146 vertexList = Set.toAscList . vertexSet 147 148 -- | The sorted list of edges of a graph. 149 -- 150 -- @ 151 -- edgeList == Set.'Set.toAscList' . 'edgeSet' 152 -- @ 153 edgeList :: Ord (ToVertex t) => t -> [(ToVertex t, ToVertex t)] 154 edgeList = AM.edgeList . toAdjacencyMap 155 156 -- | The set of vertices of a graph. 157 -- 158 -- @ 159 -- vertexSet == 'foldg' Set.'Set.empty' Set.'Set.singleton' Set.'Set.union' Set.'Set.union' 160 -- @ 161 vertexSet :: Ord (ToVertex t) => t -> Set (ToVertex t) 162 vertexSet = foldg Set.empty Set.singleton Set.union Set.union 163 164 -- | The set of vertices of a graph. Like 'vertexSet' but specialised for 165 -- graphs with vertices of type 'Int'. 166 -- 167 -- @ 168 -- vertexIntSet == 'foldg' IntSet.'IntSet.empty' IntSet.'IntSet.singleton' IntSet.'IntSet.union' IntSet.'IntSet.union' 169 -- @ 170 vertexIntSet :: ToVertex t ~ Int => t -> IntSet 171 vertexIntSet = foldg IntSet.empty IntSet.singleton IntSet.union IntSet.union 172 173 -- | The set of edges of a graph. 174 -- 175 -- @ 176 -- edgeSet == Algebra.Graph.AdjacencyMap.'AM.edgeSet' . 'toAdjacencyMap' 177 -- @ 178 edgeSet :: Ord (ToVertex t) => t -> Set (ToVertex t, ToVertex t) 179 edgeSet = AM.edgeSet . toAdjacencyMap 180 181 -- | The /preset/ of a vertex is the set of its /direct predecessors/. 182 -- 183 -- @ 184 -- preSet x == Algebra.Graph.AdjacencyMap.'AM.preSet' x . 'toAdjacencyMap' 185 -- @ 186 preSet :: Ord (ToVertex t) => ToVertex t -> t -> Set (ToVertex t) 187 preSet x = AM.postSet x . toAdjacencyMapTranspose 188 189 -- | The /preset/ (here @preIntSet@) of a vertex is the set of its 190 -- /direct predecessors/. Like 'preSet' but specialised for graphs with 191 -- vertices of type 'Int'. 192 -- 193 -- @ 194 -- preIntSet x == Algebra.Graph.AdjacencyIntMap.'AIM.preIntSet' x . 'toAdjacencyIntMap' 195 -- @ 196 preIntSet :: ToVertex t ~ Int => Int -> t -> IntSet 197 preIntSet x = AIM.postIntSet x . toAdjacencyIntMapTranspose 198 199 -- | The /postset/ of a vertex is the set of its /direct successors/. 200 -- 201 -- @ 202 -- postSet x == Algebra.Graph.AdjacencyMap.'AM.postSet' x . 'toAdjacencyMap' 203 -- @ 204 postSet :: Ord (ToVertex t) => ToVertex t -> t -> Set (ToVertex t) 205 postSet x = AM.postSet x . toAdjacencyMap 206 207 -- | The /postset/ (here @postIntSet@) of a vertex is the set of its 208 -- /direct successors/. Like 'postSet' but specialised for graphs with 209 -- vertices of type 'Int'. 210 -- 211 -- @ 212 -- postIntSet x == Algebra.Graph.AdjacencyIntMap.'AIM.postIntSet' x . 'toAdjacencyIntMap' 213 -- @ 214 postIntSet :: ToVertex t ~ Int => Int -> t -> IntSet 215 postIntSet x = AIM.postIntSet x . toAdjacencyIntMap 216 217 -- | The sorted /adjacency list/ of a graph. 218 -- 219 -- @ 220 -- adjacencyList == Algebra.Graph.AdjacencyMap.'AM.adjacencyList' . 'toAdjacencyMap' 221 -- @ 222 adjacencyList :: Ord (ToVertex t) => t -> [(ToVertex t, [ToVertex t])] 223 adjacencyList = AM.adjacencyList . toAdjacencyMap 224 225 -- | Compute the /depth-first search/ forest of a graph that corresponds to 226 -- searching from each of the graph vertices in the 'Ord' @a@ order. 227 -- 228 -- @ 229 -- dfsForest == Algebra.Graph.AdjacencyMap.'AM.dfsForest' . toAdjacencyMap 230 -- @ 231 dfsForest :: Ord (ToVertex t) => t -> Forest (ToVertex t) 232 dfsForest = AM.dfsForest . toAdjacencyMap 233 234 -- | Compute the /depth-first search/ forest of a graph, searching from each 235 -- of the given vertices in order. Note that the resulting forest does not 236 -- necessarily span the whole graph, as some vertices may be unreachable. 237 -- 238 -- @ 239 -- dfsForestFrom vs == Algebra.Graph.AdjacencyMap.'AM.dfsForestFrom' vs . toAdjacencyMap 240 -- @ 241 dfsForestFrom :: Ord (ToVertex t) => [ToVertex t] -> t -> Forest (ToVertex t) 242 dfsForestFrom vs = AM.dfsForestFrom vs . toAdjacencyMap 243 244 -- | Compute the list of vertices visited by the /depth-first search/ in a 245 -- graph, when searching from each of the given vertices in order. 246 -- 247 -- @ 248 -- dfs vs == Algebra.Graph.AdjacencyMap.'AM.dfs' vs . toAdjacencyMap 249 -- @ 250 dfs :: Ord (ToVertex t) => [ToVertex t] -> t -> [ToVertex t] 251 dfs vs = AM.dfs vs . toAdjacencyMap 252 253 -- | Compute the list of vertices that are /reachable/ from a given source 254 -- vertex in a graph. The vertices in the resulting list appear in the 255 -- /depth-first order/. 256 -- 257 -- @ 258 -- reachable x == Algebra.Graph.AdjacencyMap.'AM.reachable' x . toAdjacencyMap 259 -- @ 260 reachable :: Ord (ToVertex t) => ToVertex t -> t -> [ToVertex t] 261 reachable x = AM.reachable x . toAdjacencyMap 262 263 -- | Compute the /topological sort/ of a graph or a @AM.Cycle@ if the 264 -- graph is cyclic. 265 -- 266 -- @ 267 -- topSort == Algebra.Graph.AdjacencyMap.'AM.topSort' . toAdjacencyMap 268 -- @ 269 topSort :: Ord (ToVertex t) => t -> Either (AM.Cycle (ToVertex t)) [ToVertex t] 270 topSort = AM.topSort . toAdjacencyMap 271 272 -- | Check if a given graph is /acyclic/. 273 -- 274 -- @ 275 -- isAcyclic == Algebra.Graph.AdjacencyMap.'AM.isAcyclic' . toAdjacencyMap 276 -- @ 277 isAcyclic :: Ord (ToVertex t) => t -> Bool 278 isAcyclic = AM.isAcyclic . toAdjacencyMap 279 280 -- | Convert a value to the corresponding 'AM.AdjacencyMap'. 281 -- 282 -- @ 283 -- toAdjacencyMap == 'foldg' 'AM.empty' 'AM.vertex' 'AM.overlay' 'AM.connect' 284 -- @ 285 toAdjacencyMap :: Ord (ToVertex t) => t -> AM.AdjacencyMap (ToVertex t) 286 toAdjacencyMap = foldg AM.empty AM.vertex AM.overlay AM.connect 287 288 -- | Convert a value to the corresponding 'AM.AdjacencyMap' and transpose the 289 -- result. 290 -- 291 -- @ 292 -- toAdjacencyMapTranspose == 'foldg' 'AM.empty' 'AM.vertex' 'AM.overlay' ('flip' 'AM.connect') 293 -- @ 294 toAdjacencyMapTranspose :: Ord (ToVertex t) => t -> AM.AdjacencyMap (ToVertex t) 295 toAdjacencyMapTranspose = foldg AM.empty AM.vertex AM.overlay (flip AM.connect) 296 297 -- | Convert a value to the corresponding 'AIM.AdjacencyIntMap'. 298 -- 299 -- @ 300 -- toAdjacencyIntMap == 'foldg' 'AIM.empty' 'AIM.vertex' 'AIM.overlay' 'AIM.connect' 301 -- @ 302 toAdjacencyIntMap :: ToVertex t ~ Int => t -> AIM.AdjacencyIntMap 303 toAdjacencyIntMap = foldg AIM.empty AIM.vertex AIM.overlay AIM.connect 304 305 -- | Convert a value to the corresponding 'AIM.AdjacencyIntMap' and transpose 306 -- the result. 307 -- 308 -- @ 309 -- toAdjacencyIntMapTranspose == 'foldg' 'AIM.empty' 'AIM.vertex' 'AIM.overlay' ('flip' 'AIM.connect') 310 -- @ 311 toAdjacencyIntMapTranspose :: ToVertex t ~ Int => t -> AIM.AdjacencyIntMap 312 toAdjacencyIntMapTranspose = foldg AIM.empty AIM.vertex AIM.overlay (flip AIM.connect) 313 314 -- | Check if a given forest is a valid /depth-first search/ forest of a 315 -- graph. 316 -- 317 -- @ 318 -- isDfsForestOf f == Algebra.Graph.AdjacencyMap.'AM.isDfsForestOf' f . toAdjacencyMap 319 -- @ 320 isDfsForestOf :: Ord (ToVertex t) => Forest (ToVertex t) -> t -> Bool 321 isDfsForestOf f = AM.isDfsForestOf f . toAdjacencyMap 322 323 -- | Check if a given list of vertices is a valid /topological sort/ of a 324 -- graph. 325 -- 326 -- @ 327 -- isTopSortOf vs == Algebra.Graph.AdjacencyMap.'AM.isTopSortOf' vs . toAdjacencyMap 328 -- @ 329 isTopSortOf :: Ord (ToVertex t) => [ToVertex t] -> t -> Bool 330 isTopSortOf vs = AM.isTopSortOf vs . toAdjacencyMap 331 332instance Ord a => ToGraph (G.Graph a) where 333 type ToVertex (G.Graph a) = a 334 toGraph = id 335 foldg = G.foldg 336 hasEdge = G.hasEdge 337 338-- | See "Algebra.Graph.AdjacencyMap". 339instance Ord a => ToGraph (AM.AdjacencyMap a) where 340 type ToVertex (AM.AdjacencyMap a) = a 341 toGraph = G.stars 342 . map (fmap Set.toList) 343 . Map.toList 344 . AM.adjacencyMap 345 isEmpty = AM.isEmpty 346 hasVertex = AM.hasVertex 347 hasEdge = AM.hasEdge 348 vertexCount = AM.vertexCount 349 edgeCount = AM.edgeCount 350 vertexList = AM.vertexList 351 vertexSet = AM.vertexSet 352 vertexIntSet = IntSet.fromAscList . AM.vertexList 353 edgeList = AM.edgeList 354 edgeSet = AM.edgeSet 355 adjacencyList = AM.adjacencyList 356 preSet = AM.preSet 357 postSet = AM.postSet 358 dfsForest = AM.dfsForest 359 dfsForestFrom = AM.dfsForestFrom 360 dfs = AM.dfs 361 reachable = AM.reachable 362 topSort = AM.topSort 363 isAcyclic = AM.isAcyclic 364 toAdjacencyMap = id 365 toAdjacencyIntMap = AIM.fromAdjacencyMap 366 toAdjacencyMapTranspose = AM.transpose . toAdjacencyMap 367 toAdjacencyIntMapTranspose = AIM.transpose . toAdjacencyIntMap 368 isDfsForestOf = AM.isDfsForestOf 369 isTopSortOf = AM.isTopSortOf 370 371instance ToGraph AIM.AdjacencyIntMap where 372 type ToVertex AIM.AdjacencyIntMap = Int 373 toGraph = G.stars 374 . map (fmap IntSet.toList) 375 . IntMap.toList 376 . AIM.adjacencyIntMap 377 isEmpty = AIM.isEmpty 378 hasVertex = AIM.hasVertex 379 hasEdge = AIM.hasEdge 380 vertexCount = AIM.vertexCount 381 edgeCount = AIM.edgeCount 382 vertexList = AIM.vertexList 383 vertexSet = Set.fromAscList . IntSet.toAscList . AIM.vertexIntSet 384 vertexIntSet = AIM.vertexIntSet 385 edgeList = AIM.edgeList 386 edgeSet = AIM.edgeSet 387 adjacencyList = AIM.adjacencyList 388 preIntSet = AIM.preIntSet 389 postIntSet = AIM.postIntSet 390 dfsForest = AIM.dfsForest 391 dfsForestFrom = AIM.dfsForestFrom 392 dfs = AIM.dfs 393 reachable = AIM.reachable 394 topSort = AIM.topSort 395 isAcyclic = AIM.isAcyclic 396 toAdjacencyMap = AM.stars . AIM.adjacencyList 397 toAdjacencyIntMap = id 398 toAdjacencyMapTranspose = AM.transpose . toAdjacencyMap 399 toAdjacencyIntMapTranspose = AIM.transpose . toAdjacencyIntMap 400 isDfsForestOf = AIM.isDfsForestOf 401 isTopSortOf = AIM.isTopSortOf 402 403-- | See "Algebra.Graph.Labelled". 404instance (Eq e, Monoid e, Ord a) => ToGraph (LG.Graph e a) where 405 type ToVertex (LG.Graph e a) = a 406 foldg e v o c = LG.foldg e v (\e -> if e == mempty then o else c) 407 vertexList = LG.vertexList 408 vertexSet = LG.vertexSet 409 toAdjacencyMap = LAM.skeleton 410 . LG.foldg LAM.empty LAM.vertex LAM.connect 411 toAdjacencyMapTranspose = LAM.skeleton 412 . LG.foldg LAM.empty LAM.vertex (fmap flip LAM.connect) 413 toAdjacencyIntMap = toAdjacencyIntMap . toAdjacencyMap 414 toAdjacencyIntMapTranspose = toAdjacencyIntMapTranspose . toAdjacencyMapTranspose 415 416-- | See "Algebra.Graph.Labelled.AdjacencyMap". 417instance (Eq e, Monoid e, Ord a) => ToGraph (LAM.AdjacencyMap e a) where 418 type ToVertex (LAM.AdjacencyMap e a) = a 419 toGraph = toGraph . LAM.skeleton 420 foldg e v o c = foldg e v o c . LAM.skeleton 421 isEmpty = LAM.isEmpty 422 hasVertex = LAM.hasVertex 423 hasEdge = LAM.hasEdge 424 vertexCount = LAM.vertexCount 425 edgeCount = LAM.edgeCount 426 vertexList = LAM.vertexList 427 vertexSet = LAM.vertexSet 428 vertexIntSet = IntSet.fromAscList . LAM.vertexList 429 edgeList = edgeList . LAM.skeleton 430 edgeSet = edgeSet . LAM.skeleton 431 adjacencyList = adjacencyList . LAM.skeleton 432 preSet = LAM.preSet 433 postSet = LAM.postSet 434 toAdjacencyMap = LAM.skeleton 435 toAdjacencyIntMap = toAdjacencyIntMap . LAM.skeleton 436 toAdjacencyMapTranspose = toAdjacencyMapTranspose . LAM.skeleton 437 toAdjacencyIntMapTranspose = toAdjacencyIntMapTranspose . LAM.skeleton 438 439-- | See "Algebra.Graph.NonEmpty.AdjacencyMap". 440instance Ord a => ToGraph (NAM.AdjacencyMap a) where 441 type ToVertex (NAM.AdjacencyMap a) = a 442 toGraph = toGraph . toAdjacencyMap 443 isEmpty _ = False 444 hasVertex = NAM.hasVertex 445 hasEdge = NAM.hasEdge 446 vertexCount = NAM.vertexCount 447 edgeCount = NAM.edgeCount 448 vertexList = vertexList . toAdjacencyMap 449 vertexSet = NAM.vertexSet 450 vertexIntSet = vertexIntSet . toAdjacencyMap 451 edgeList = NAM.edgeList 452 edgeSet = NAM.edgeSet 453 adjacencyList = adjacencyList . toAdjacencyMap 454 preSet = NAM.preSet 455 postSet = NAM.postSet 456 dfsForest = dfsForest . toAdjacencyMap 457 dfsForestFrom xs = dfsForestFrom xs . toAdjacencyMap 458 dfs xs = dfs xs . toAdjacencyMap 459 reachable x = reachable x . toAdjacencyMap 460 topSort = topSort . toAdjacencyMap 461 isAcyclic = isAcyclic . toAdjacencyMap 462 toAdjacencyMap = NAM.fromNonEmpty 463 toAdjacencyIntMap = toAdjacencyIntMap . toAdjacencyMap 464 toAdjacencyMapTranspose = toAdjacencyMap . NAM.transpose 465 toAdjacencyIntMapTranspose = toAdjacencyIntMap . NAM.transpose 466 isDfsForestOf f = isDfsForestOf f . toAdjacencyMap 467 isTopSortOf x = isTopSortOf x . toAdjacencyMap 468 469-- TODO: Get rid of "Relation.Internal" and move this instance to "Relation". 470-- | See "Algebra.Graph.Relation". 471instance Ord a => ToGraph (R.Relation a) where 472 type ToVertex (R.Relation a) = a 473 toGraph r = G.vertices (Set.toList $ R.domain r) `G.overlay` 474 G.edges (Set.toList $ R.relation r) 475 isEmpty = R.isEmpty 476 hasVertex = R.hasVertex 477 hasEdge = R.hasEdge 478 vertexCount = R.vertexCount 479 edgeCount = R.edgeCount 480 vertexList = R.vertexList 481 vertexSet = R.vertexSet 482 vertexIntSet = IntSet.fromAscList . R.vertexList 483 edgeList = R.edgeList 484 edgeSet = R.edgeSet 485 adjacencyList = R.adjacencyList 486 toAdjacencyMap = AM.stars . R.adjacencyList 487 toAdjacencyIntMap = AIM.stars . R.adjacencyList 488 toAdjacencyMapTranspose = AM.transpose . toAdjacencyMap 489 toAdjacencyIntMapTranspose = AIM.transpose . toAdjacencyIntMap 490 491-- TODO: This instance is probably wrong because of the way it treats edges. 492-- Find out a better way to integrate undirected graphs into 'ToGraph'. 493-- | See "Algebra.Graph.Symmetric.Relation". Warning: this instance is likely to 494-- be modified or removed in future. 495instance Ord a => ToGraph (SR.Relation a) where 496 type ToVertex (SR.Relation a) = a 497 toGraph = toGraph . SR.fromSymmetric 498 isEmpty = SR.isEmpty 499 hasVertex = SR.hasVertex 500 hasEdge = SR.hasEdge 501 vertexCount = SR.vertexCount 502 edgeCount = SR.edgeCount 503 vertexList = SR.vertexList 504 vertexSet = SR.vertexSet 505 vertexIntSet = IntSet.fromAscList . SR.vertexList 506 edgeList = SR.edgeList 507 edgeSet = SR.edgeSet 508 adjacencyList = SR.adjacencyList 509 toAdjacencyMap = toAdjacencyMap . SR.fromSymmetric 510 toAdjacencyIntMap = toAdjacencyIntMap . SR.fromSymmetric 511 toAdjacencyMapTranspose = toAdjacencyMap 512 toAdjacencyIntMapTranspose = toAdjacencyIntMap 513 514-- | The /adjacency map/ of a graph: each vertex is associated with a set of its 515-- /direct successors/. 516-- 517-- @ 518-- adjacencyMap == Algebra.Graph.AdjacencyMap.'Algebra.Graph.AdjacencyMap.adjacencyMap' . 'toAdjacencyMap' 519-- @ 520adjacencyMap :: ToGraph t => Ord (ToVertex t) => t -> Map (ToVertex t) (Set (ToVertex t)) 521adjacencyMap = AM.adjacencyMap . toAdjacencyMap 522 523-- | The /adjacency map/ of a graph: each vertex is associated with a set of its 524-- /direct successors/. Like 'adjacencyMap' but specialised for graphs with 525-- vertices of type 'Int'. 526-- 527-- @ 528-- adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.'Algebra.Graph.AdjacencyIntMap.adjacencyIntMap' . 'toAdjacencyIntMap' 529-- @ 530adjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet 531adjacencyIntMap = AIM.adjacencyIntMap . toAdjacencyIntMap 532 533-- | The transposed /adjacency map/ of a graph: each vertex is associated with a 534-- set of its /direct predecessors/. 535-- 536-- @ 537-- adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.'Algebra.Graph.AdjacencyMap.adjacencyMap' . 'toAdjacencyMapTranspose' 538-- @ 539adjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t)) 540adjacencyMapTranspose = AM.adjacencyMap . toAdjacencyMapTranspose 541 542-- | The transposed /adjacency map/ of a graph: each vertex is associated with a 543-- set of its /direct predecessors/. Like 'adjacencyMapTranspose' but 544-- specialised for graphs with vertices of type 'Int'. 545-- 546-- @ 547-- adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.'Algebra.Graph.AdjacencyIntMap.adjacencyIntMap' . 'toAdjacencyIntMapTranspose' 548-- @ 549adjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet 550adjacencyIntMapTranspose = AIM.adjacencyIntMap . toAdjacencyIntMapTranspose 551