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