content: -----------------------------------------------------------------------------
  -- |
  -- Module     : Algebra.Graph.Relation.Symmetric
  -- Copyright  : (c) Andrey Mokhov 2016-2025
  -- License    : MIT (see the file LICENSE)
  -- Maintainer : andrey.mokhov@gmail.com
  -- Stability  : experimental
  --
  -- An abstract implementation of symmetric binary relations. To avoid name
  -- clashes with "Algebra.Graph.Relation", this module can be imported qualified:
  --
  -- @
  -- import qualified Algebra.Graph.Relation.Symmetric as Symmetric
  -- @
  --
  -- 'Relation' is an instance of the 'Algebra.Graph.Class.Graph' type class,
  -- which can be used for polymorphic graph construction and manipulation.
  -----------------------------------------------------------------------------
  module Algebra.Graph.Relation.Symmetric (
      -- * Data structure
      Relation, toSymmetric, fromSymmetric,
  
      -- * Basic graph construction primitives
      empty, vertex, edge, overlay, connect, vertices, edges, overlays, connects,
  
      -- * Relations on graphs
      isSubgraphOf,
  
      -- * Graph properties
      isEmpty, hasVertex, hasEdge, vertexCount, edgeCount, vertexList, edgeList,
      adjacencyList, vertexSet, edgeSet, neighbours,
  
      -- * Standard families of graphs
      path, circuit, clique, biclique, star, stars, tree, forest,
  
      -- * Graph transformation
      removeVertex, removeEdge, replaceVertex, mergeVertices, gmap, induce, induceJust,
  
      -- * Miscellaneous
      consistent
  
      ) where
  
  import Control.DeepSeq
  import Data.Coerce
  import Data.Set (Set)
  import Data.String
  import Data.Tree (Forest, Tree)
  
  import qualified Data.IntSet as IntSet
  import qualified Data.Set    as Set
  
  import qualified Algebra.Graph.ToGraph  as T
  import qualified Algebra.Graph.Relation as R
  
  {-| This data type represents a /symmetric binary relation/ over a set of
  elements of type @a@. Symmetric relations satisfy all laws of the
  'Algebra.Graph.Class.Undirected' type class, including the commutativity of
  'connect':
  
  @'connect' x y == 'connect' y x@
  
  The 'Show' instance lists edge vertices in non-decreasing order:
  
  @show (empty     :: Relation Int) == "empty"
  show (1         :: Relation Int) == "vertex 1"
  show (1 + 2     :: Relation Int) == "vertices [1,2]"
  show (1 * 2     :: Relation Int) == "edge 1 2"
  show (2 * 1     :: Relation Int) == "edge 1 2"
  show (1 * 2 * 1 :: Relation Int) == "edges [(1,1),(1,2)]"
  show (3 * 2 * 1 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]"
  show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"@
  
  The total order on graphs is defined using /size-lexicographic/ comparison:
  
  * Compare the number of vertices. In case of a tie, continue.
  * Compare the sets of vertices. In case of a tie, continue.
  * Compare the number of edges. In case of a tie, continue.
  * Compare the sets of edges.
  
  Here are a few examples:
  
  @'vertex' 1 < 'vertex' 2
  'vertex' 3 < 'edge' 1 2
  'vertex' 1 < 'edge' 1 1
  'edge' 1 1 < 'edge' 1 2
  'edge' 1 2 < 'edge' 1 1 + 'edge' 2 2
  'edge' 2 1 < 'edge' 1 3@
  
  @'edge' 1 2 == 'edge' 2 1@
  
  Note that the resulting order refines the 'isSubgraphOf' relation and is
  compatible with 'overlay' and 'connect' operations:
  
  @'isSubgraphOf' x y ==> x <= y@
  
  @'empty' <= x
  x     <= x + y
  x + y <= x * y@
  -}
  newtype Relation a = SR {
      -- | Extract the underlying symmetric "Algebra.Graph.Relation".
      -- Complexity: /O(1)/ time and memory.
      --
      -- @
      -- fromSymmetric ('edge' 1 2)    == 'R.edges' [(1,2), (2,1)]
      -- 'R.vertexCount' . fromSymmetric == 'vertexCount'
      -- 'R.edgeCount'   . fromSymmetric <= (*2) . 'edgeCount'
      -- @
      fromSymmetric :: R.Relation a
      } deriving (Eq, IsString, NFData)
  
  instance (Ord a, Show a) => Show (Relation a) where
      show = show . toRelation
        where
          toRelation r = R.vertices (vertexList r) `R.overlay` R.edges (edgeList r)
  
  instance Ord a => Ord (Relation a) where
      compare x y = mconcat
          [ compare (vertexCount x) (vertexCount  y)
          , compare (vertexSet   x) (vertexSet    y)
          , compare (edgeCount   x) (edgeCount    y)
          , compare (edgeSet     x) (edgeSet      y) ]
  
  -- | __Note:__ this does not satisfy the usual ring laws; see 'Relation' for
  -- more details.
  instance (Ord a, Num a) => Num (Relation a) where
      fromInteger = vertex . fromInteger
      (+)         = overlay
      (*)         = connect
      signum      = const empty
      abs         = id
      negate      = id
  
  -- | Defined via 'overlay'.
  instance Ord a => Semigroup (Relation a) where
      (<>) = overlay
  
  -- | Defined via 'overlay' and 'empty'.
  instance Ord a => Monoid (Relation a) where
      mempty = empty
  
  -- | Defined via 'fromSymmetric' and the 'T.ToGraph' instance of 'R.Relation'.
  instance Ord a => T.ToGraph (Relation a) where
      type ToVertex (Relation a) = a
      toGraph                    = T.toGraph . fromSymmetric
      isEmpty                    = isEmpty
      hasVertex                  = hasVertex
      hasEdge                    = hasEdge
      vertexCount                = vertexCount
      edgeCount                  = R.edgeCount . fromSymmetric
      vertexList                 = vertexList
      vertexSet                  = vertexSet
      vertexIntSet               = IntSet.fromAscList . vertexList
      edgeList                   = R.edgeList . fromSymmetric
      edgeSet                    = R.relation . fromSymmetric
      adjacencyList              = adjacencyList
      toAdjacencyMap             = T.toAdjacencyMap . fromSymmetric
      toAdjacencyIntMap          = T.toAdjacencyIntMap . fromSymmetric
      toAdjacencyMapTranspose    = T.toAdjacencyMap    -- No need to transpose!
      toAdjacencyIntMapTranspose = T.toAdjacencyIntMap -- No need to transpose!
  
  -- | Construct a symmetric relation from a given "Algebra.Graph.Relation".
  -- Complexity: /O(m * log(m))/ time.
  --
  -- @
  -- toSymmetric ('Algebra.Graph.Relation.edge' 1 2)         == 'edge' 1 2
  -- toSymmetric . 'fromSymmetric'    == id
  -- 'fromSymmetric'    . toSymmetric == 'Algebra.Graph.Relation.symmetricClosure'
  -- 'vertexCount'      . toSymmetric == 'Algebra.Graph.Relation.vertexCount'
  -- (*2) . 'edgeCount' . toSymmetric >= 'Algebra.Graph.Relation.edgeCount'
  -- @
  toSymmetric :: Ord a => R.Relation a -> Relation a
  toSymmetric = SR . R.symmetricClosure
  
  -- | Construct the /empty graph/.
  --
  -- @
  -- 'isEmpty'     empty == True
  -- 'hasVertex' x empty == False
  -- 'vertexCount' empty == 0
  -- 'edgeCount'   empty == 0
  -- @
  empty :: Relation a
  empty = coerce R.empty
  
  -- | Construct the graph comprising /a single isolated vertex/.
  --
  -- @
  -- 'isEmpty'     (vertex x) == False
  -- 'hasVertex' x (vertex y) == (x == y)
  -- 'vertexCount' (vertex x) == 1
  -- 'edgeCount'   (vertex x) == 0
  -- @
  vertex :: a -> Relation a
  vertex = coerce R.vertex
  
  -- | Construct the graph comprising /a single edge/.
  --
  -- @
  -- edge x y               == 'connect' ('vertex' x) ('vertex' y)
  -- edge x y               == 'edge' y x
  -- edge x y               == 'edges' [(x,y), (y,x)]
  -- 'hasEdge' x y (edge x y) == True
  -- 'edgeCount'   (edge x y) == 1
  -- 'vertexCount' (edge 1 1) == 1
  -- 'vertexCount' (edge 1 2) == 2
  -- @
  edge :: Ord a => a -> a -> Relation a
  edge x y = SR $ R.edges [(x,y), (y,x)]
  
  -- | /Overlay/ two graphs. This is a commutative, associative and idempotent
  -- operation with the identity 'empty'.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- 'isEmpty'     (overlay x y) == 'isEmpty'   x   && 'isEmpty'   y
  -- 'hasVertex' z (overlay x y) == 'hasVertex' z x || 'hasVertex' z y
  -- 'vertexCount' (overlay x y) >= 'vertexCount' x
  -- 'vertexCount' (overlay x y) <= 'vertexCount' x + 'vertexCount' y
  -- 'edgeCount'   (overlay x y) >= 'edgeCount' x
  -- 'edgeCount'   (overlay x y) <= 'edgeCount' x   + 'edgeCount' y
  -- 'vertexCount' (overlay 1 2) == 2
  -- 'edgeCount'   (overlay 1 2) == 0
  -- @
  overlay :: Ord a => Relation a -> Relation a -> Relation a
  overlay = coerce R.overlay
  
  -- | /Connect/ two graphs. This is a commutative and associative operation with
  -- the identity 'empty', which distributes over 'overlay' and obeys the
  -- decomposition axiom.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory. Note that the
  -- number of edges in the resulting graph is quadratic with respect to the number
  -- of vertices of the arguments: /m = O(m1 + m2 + n1 * n2)/.
  --
  -- @
  -- connect x y               == connect y x
  -- 'isEmpty'     (connect x y) == 'isEmpty'   x   && 'isEmpty'   y
  -- 'hasVertex' z (connect x y) == 'hasVertex' z x || 'hasVertex' z y
  -- 'vertexCount' (connect x y) >= 'vertexCount' x
  -- 'vertexCount' (connect x y) <= 'vertexCount' x + 'vertexCount' y
  -- 'edgeCount'   (connect x y) >= 'edgeCount' x
  -- 'edgeCount'   (connect x y) >= 'edgeCount' y
  -- 'edgeCount'   (connect x y) >= 'vertexCount' x * 'vertexCount' y \`div\` 2
  -- 'vertexCount' (connect 1 2) == 2
  -- 'edgeCount'   (connect 1 2) == 1
  -- @
  connect :: Ord a => Relation a -> Relation a -> Relation a
  connect x y = coerce R.connect x y `overlay` biclique (vertexList y) (vertexList x)
  
  -- | Construct the graph comprising a given list of isolated vertices.
  -- Complexity: /O(L * log(L))/ time and /O(L)/ memory, where /L/ is the length
  -- of the given list.
  --
  -- @
  -- vertices []            == 'empty'
  -- vertices [x]           == 'vertex' x
  -- vertices               == 'overlays' . map 'vertex'
  -- 'hasVertex' x . vertices == 'elem' x
  -- 'vertexCount' . vertices == 'length' . 'Data.List.nub'
  -- 'vertexSet'   . vertices == Set.'Set.fromList'
  -- @
  vertices :: Ord a => [a] -> Relation a
  vertices = coerce R.vertices
  
  -- TODO: Optimise by avoiding multiple list traversal.
  -- | Construct the graph from a list of edges.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- edges []             == 'empty'
  -- edges [(x,y)]        == 'edge' x y
  -- edges [(x,y), (y,x)] == 'edge' x y
  -- @
  edges :: Ord a => [(a, a)] -> Relation a
  edges = toSymmetric . R.edges
  
  -- | Overlay a given list of graphs.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- overlays []        == 'empty'
  -- overlays [x]       == x
  -- overlays [x,y]     == 'overlay' x y
  -- overlays           == 'foldr' 'overlay' 'empty'
  -- 'isEmpty' . overlays == 'all' 'isEmpty'
  -- @
  overlays :: Ord a => [Relation a] -> Relation a
  overlays = coerce R.overlays
  
  -- | Connect a given list of graphs.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- connects []        == 'empty'
  -- connects [x]       == x
  -- connects [x,y]     == 'connect' x y
  -- connects           == 'foldr' 'connect' 'empty'
  -- 'isEmpty' . connects == 'all' 'isEmpty'
  -- connects           == connects . 'reverse'
  -- @
  connects :: Ord a => [Relation a] -> Relation a
  connects = foldr connect empty
  
  -- | The 'isSubgraphOf' function takes two graphs and returns 'True' if the
  -- first graph is a /subgraph/ of the second.
  -- Complexity: /O((n + m) * log(n))/ time.
  --
  -- @
  -- isSubgraphOf 'empty'         x             ==  True
  -- isSubgraphOf ('vertex' x)    'empty'         ==  False
  -- isSubgraphOf x             ('overlay' x y) ==  True
  -- isSubgraphOf ('overlay' x y) ('connect' x y) ==  True
  -- isSubgraphOf ('path' xs)     ('circuit' xs)  ==  True
  -- isSubgraphOf ('edge' x y)    ('edge' y x)    ==  True
  -- isSubgraphOf x y                         ==> x <= y
  -- @
  isSubgraphOf :: Ord a => Relation a -> Relation a -> Bool
  isSubgraphOf = coerce R.isSubgraphOf
  
  -- | Check if a relation is empty.
  -- Complexity: /O(1)/ time.
  --
  -- @
  -- isEmpty 'empty'                       == True
  -- isEmpty ('overlay' 'empty' 'empty')       == True
  -- isEmpty ('vertex' x)                  == False
  -- isEmpty ('removeVertex' x $ 'vertex' x) == True
  -- isEmpty ('removeEdge' x y $ 'edge' x y) == False
  -- @
  isEmpty :: Relation a -> Bool
  isEmpty = coerce R.isEmpty
  
  -- | Check if a graph contains a given vertex.
  -- Complexity: /O(log(n))/ time.
  --
  -- @
  -- hasVertex x 'empty'            == False
  -- hasVertex x ('vertex' y)       == (x == y)
  -- hasVertex x . 'removeVertex' x == 'const' False
  -- @
  hasVertex :: Ord a => a -> Relation a -> Bool
  hasVertex = coerce R.hasVertex
  
  -- | Check if a graph contains a given edge.
  -- Complexity: /O(log(n))/ time.
  --
  -- @
  -- hasEdge x y 'empty'            == False
  -- hasEdge x y ('vertex' z)       == False
  -- hasEdge x y ('edge' x y)       == True
  -- hasEdge x y ('edge' y x)       == True
  -- hasEdge x y . 'removeEdge' x y == 'const' False
  -- hasEdge x y                  == 'elem' ('min' x y, 'max' x y) . 'edgeList'
  -- @
  hasEdge :: Ord a => a -> a -> Relation a -> Bool
  hasEdge = coerce R.hasEdge
  
  -- | The number of vertices in a graph.
  -- Complexity: /O(1)/ time.
  --
  -- @
  -- vertexCount 'empty'             ==  0
  -- vertexCount ('vertex' x)        ==  1
  -- vertexCount                   ==  'length' . 'vertexList'
  -- vertexCount x \< vertexCount y ==> x \< y
  -- @
  vertexCount :: Relation a -> Int
  vertexCount = coerce R.vertexCount
  
  -- | The number of edges in a graph.
  -- Complexity: /O(1)/ time.
  --
  -- @
  -- edgeCount 'empty'      == 0
  -- edgeCount ('vertex' x) == 0
  -- edgeCount ('edge' x y) == 1
  -- edgeCount            == 'length' . 'edgeList'
  -- @
  edgeCount :: Ord a => Relation a -> Int
  edgeCount = Set.size . edgeSet
  
  -- | The sorted list of vertices of a given graph.
  -- Complexity: /O(n)/ time and memory.
  --
  -- @
  -- vertexList 'empty'      == []
  -- vertexList ('vertex' x) == [x]
  -- vertexList . 'vertices' == 'Data.List.nub' . 'Data.List.sort'
  -- @
  vertexList :: Relation a -> [a]
  vertexList = coerce R.vertexList
  
  -- | The sorted list of edges of a graph, where edge vertices appear in the
  -- non-decreasing order.
  -- Complexity: /O(n + m)/ time and /O(m)/ memory.
  --
  -- Note: If you need the sorted list of edges where an edge appears in both
  -- directions, use @'Algebra.Graph.Relation.edgeList' . 'fromSymmetric'@.
  --
  -- @
  -- edgeList 'empty'          == []
  -- edgeList ('vertex' x)     == []
  -- edgeList ('edge' x y)     == [('min' x y, 'max' y x)]
  -- edgeList ('star' 2 [3,1]) == [(1,2), (2,3)]
  -- @
  edgeList :: Ord a => Relation a -> [(a, a)]
  edgeList = Set.toAscList . edgeSet
  
  -- | The set of vertices of a given graph.
  -- Complexity: /O(1)/ time.
  --
  -- @
  -- vertexSet 'empty'      == Set.'Set.empty'
  -- vertexSet . 'vertex'   == Set.'Set.singleton'
  -- vertexSet . 'vertices' == Set.'Set.fromList'
  -- @
  vertexSet :: Relation a -> Set a
  vertexSet = coerce R.vertexSet
  
  -- | The set of edges of a given graph, where edge vertices appear in the
  -- non-decreasing order.
  -- Complexity: /O(m)/ time.
  --
  -- Note: If you need the set of edges where an edge appears in both directions,
  -- use @'R.relation' . 'fromSymmetric'@. The latter is much
  -- faster than this function, and takes only /O(1)/ time and memory.
  --
  -- @
  -- edgeSet 'empty'      == Set.'Set.empty'
  -- edgeSet ('vertex' x) == Set.'Set.empty'
  -- edgeSet ('edge' x y) == Set.'Set.singleton' ('min' x y, 'max' x y)
  -- @
  edgeSet :: Ord a => Relation a -> Set (a, a)
  edgeSet = Set.filter (uncurry (<=)) . R.edgeSet . fromSymmetric
  
  -- | The sorted /adjacency list/ of a graph.
  -- Complexity: /O(n + m)/ time and memory.
  --
  -- @
  -- adjacencyList 'empty'          == []
  -- adjacencyList ('vertex' x)     == [(x, [])]
  -- adjacencyList ('edge' 1 2)     == [(1, [2]), (2, [1])]
  -- adjacencyList ('star' 2 [3,1]) == [(1, [2]), (2, [1,3]), (3, [2])]
  -- 'stars' . adjacencyList        == id
  -- @
  adjacencyList :: Eq a => Relation a -> [(a, [a])]
  adjacencyList = coerce R.adjacencyList
  
  -- | The /path/ on a list of vertices.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- path []    == 'empty'
  -- path [x]   == 'vertex' x
  -- path [x,y] == 'edge' x y
  -- path       == path . 'reverse'
  -- @
  path :: Ord a => [a] -> Relation a
  path = toSymmetric . R.path
  
  -- | The /circuit/ on a list of vertices.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- circuit []    == 'empty'
  -- circuit [x]   == 'edge' x x
  -- circuit [x,y] == 'edge' x y
  -- circuit       == circuit . 'reverse'
  -- @
  circuit :: Ord a => [a] -> Relation a
  circuit = toSymmetric . R.circuit
  
  -- TODO: Optimise by avoiding the call to 'R.symmetricClosure'.
  -- | The /clique/ on a list of vertices.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- clique []         == 'empty'
  -- clique [x]        == 'vertex' x
  -- clique [x,y]      == 'edge' x y
  -- clique [x,y,z]    == 'edges' [(x,y), (x,z), (y,z)]
  -- clique (xs ++ ys) == 'connect' (clique xs) (clique ys)
  -- clique            == clique . 'reverse'
  -- @
  clique :: Ord a => [a] -> Relation a
  clique = toSymmetric . R.clique
  
  -- TODO: Optimise by avoiding the call to 'R.symmetricClosure'.
  -- | The /biclique/ on two lists of vertices.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- biclique []      []      == 'empty'
  -- biclique [x]     []      == 'vertex' x
  -- biclique []      [y]     == 'vertex' y
  -- biclique [x1,x2] [y1,y2] == 'edges' [(x1,y1), (x1,y2), (x2,x2), (x2,y2)]
  -- biclique xs      ys      == 'connect' ('vertices' xs) ('vertices' ys)
  -- @
  biclique :: Ord a => [a] -> [a] -> Relation a
  biclique xs ys = toSymmetric (R.biclique xs ys)
  
  -- TODO: Optimise.
  -- | The /star/ formed by a centre vertex connected to a list of leaves.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- star x []    == 'vertex' x
  -- star x [y]   == 'edge' x y
  -- star x [y,z] == 'edges' [(x,y), (x,z)]
  -- star x ys    == 'connect' ('vertex' x) ('vertices' ys)
  -- @
  star :: Ord a => a -> [a] -> Relation a
  star x = toSymmetric . R.star x
  
  -- | The /stars/ formed by overlaying a list of 'star's. An inverse of
  -- 'adjacencyList'.
  -- Complexity: /O(L * log(n))/ time, memory and size, where /L/ is the total
  -- size of the input.
  --
  -- @
  -- stars []                      == 'empty'
  -- stars [(x, [])]               == 'vertex' x
  -- stars [(x, [y])]              == 'edge' x y
  -- stars [(x, ys)]               == 'star' x ys
  -- stars                         == 'overlays' . 'map' ('uncurry' 'star')
  -- stars . 'adjacencyList'         == id
  -- 'overlay' (stars xs) (stars ys) == stars (xs ++ ys)
  -- @
  stars :: Ord a => [(a, [a])] -> Relation a
  stars = toSymmetric . R.stars
  
  -- | The /tree graph/ constructed from a given 'Tree.Tree' data structure.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- tree (Node x [])                                         == 'vertex' x
  -- tree (Node x [Node y [Node z []]])                       == 'path' [x,y,z]
  -- tree (Node x [Node y [], Node z []])                     == 'star' x [y,z]
  -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == 'edges' [(1,2), (1,3), (3,4), (3,5)]
  -- @
  tree :: Ord a => Tree a -> Relation a
  tree = toSymmetric . R.tree
  
  -- | The /forest graph/ constructed from a given 'Tree.Forest' data structure.
  -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory.
  --
  -- @
  -- forest []                                                  == 'empty'
  -- forest [x]                                                 == 'tree' x
  -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == 'edges' [(1,2), (1,3), (4,5)]
  -- forest                                                     == 'overlays' . 'map' 'tree'
  -- @
  forest :: Ord a => Forest a -> Relation a
  forest = toSymmetric . R.forest
  
  -- | Remove a vertex from a given graph.
  -- Complexity: /O(n + m)/ time.
  --
  -- @
  -- removeVertex x ('vertex' x)       == 'empty'
  -- removeVertex 1 ('vertex' 2)       == 'vertex' 2
  -- removeVertex x ('edge' x x)       == 'empty'
  -- removeVertex 1 ('edge' 1 2)       == 'vertex' 2
  -- removeVertex x . removeVertex x == removeVertex x
  -- @
  removeVertex :: Ord a => a -> Relation a -> Relation a
  removeVertex = coerce R.removeVertex
  
  -- | Remove an edge from a given graph.
  -- Complexity: /O(log(m))/ time.
  --
  -- @
  -- removeEdge x y ('edge' x y)       == 'vertices' [x,y]
  -- removeEdge x y . removeEdge x y == removeEdge x y
  -- removeEdge x y                  == removeEdge y x
  -- removeEdge x y . 'removeVertex' x == 'removeVertex' x
  -- removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
  -- removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
  -- @
  removeEdge :: Ord a => a -> a -> Relation a -> Relation a
  removeEdge x y = SR . R.removeEdge x y . R.removeEdge y x . fromSymmetric
  
  -- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a
  -- given 'Relation'. If @y@ already exists, @x@ and @y@ will be merged.
  -- Complexity: /O((n + m) * log(n))/ time.
  --
  -- @
  -- replaceVertex x x            == id
  -- replaceVertex x y ('vertex' x) == 'vertex' y
  -- replaceVertex x y            == 'mergeVertices' (== x) y
  -- @
  replaceVertex :: Ord a => a -> a -> Relation a -> Relation a
  replaceVertex = coerce R.replaceVertex
  
  -- | Merge vertices satisfying a given predicate into a given vertex.
  -- Complexity: /O((n + m) * log(n))/ time, assuming that the predicate takes
  -- constant time.
  --
  -- @
  -- mergeVertices ('const' False) x    == id
  -- mergeVertices (== x) y           == 'replaceVertex' x y
  -- mergeVertices 'even' 1 (0 * 2)     == 1 * 1
  -- mergeVertices 'odd'  1 (3 + 4 * 5) == 4 * 1
  -- @
  mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a
  mergeVertices = coerce R.mergeVertices
  
  -- | Transform a graph by applying a function to each of its vertices. This is
  -- similar to @Functor@'s 'fmap' but can be used with non-fully-parametric
  -- 'Relation'.
  -- Complexity: /O((n + m) * log(n))/ time.
  --
  -- @
  -- gmap f 'empty'      == 'empty'
  -- gmap f ('vertex' x) == 'vertex' (f x)
  -- gmap f ('edge' x y) == 'edge' (f x) (f y)
  -- gmap id           == id
  -- gmap f . gmap g   == gmap (f . g)
  -- @
  gmap :: Ord b => (a -> b) -> Relation a -> Relation b
  gmap = coerce R.gmap
  
  -- | Construct the /induced subgraph/ of a given graph by removing the
  -- vertices that do not satisfy a given predicate.
  -- Complexity: /O(n + m)/ time, assuming that the predicate takes constant time.
  --
  -- @
  -- induce ('const' True ) x      == x
  -- induce ('const' False) x      == 'empty'
  -- induce (/= x)               == 'removeVertex' x
  -- induce p . induce q         == induce (\\x -> p x && q x)
  -- 'isSubgraphOf' (induce p x) x == True
  -- @
  induce :: (a -> Bool) -> Relation a -> Relation a
  induce = coerce R.induce
  
  -- | Construct the /induced subgraph/ of a given graph by removing the vertices
  -- that are 'Nothing'.
  -- Complexity: /O(n + m)/ time.
  --
  -- @
  -- induceJust ('vertex' 'Nothing')                               == 'empty'
  -- induceJust ('edge' ('Just' x) 'Nothing')                        == 'vertex' x
  -- induceJust . 'gmap' 'Just'                                    == 'id'
  -- induceJust . 'gmap' (\\x -> if p x then 'Just' x else 'Nothing') == 'induce' p
  -- @
  induceJust :: Ord a => Relation (Maybe a) -> Relation a
  induceJust = coerce R.induceJust
  
  -- | The set of /neighbours/ of an element @x@ is the set of elements that are
  -- related to it, i.e. @neighbours x == { a | aRx }@. In the context of undirected
  -- graphs, this corresponds to the set of /adjacent/ vertices of vertex @x@.
  --
  -- @
  -- neighbours x 'empty'      == Set.'Set.empty'
  -- neighbours x ('vertex' x) == Set.'Set.empty'
  -- neighbours x ('edge' x y) == Set.'Set.fromList' [y]
  -- neighbours y ('edge' x y) == Set.'Set.fromList' [x]
  -- @
  neighbours :: Ord a => a -> Relation a -> Set a
  neighbours = coerce R.postSet
  
  -- | Check that the internal representation of a symmetric relation is
  -- consistent, i.e. that (i) that all edges refer to existing vertices, and (ii)
  -- all edges have their symmetric counterparts. It should be impossible to
  -- create an inconsistent 'Relation', and we use this function in testing.
  --
  -- @
  -- consistent 'empty'         == True
  -- consistent ('vertex' x)    == True
  -- consistent ('overlay' x y) == True
  -- consistent ('connect' x y) == True
  -- consistent ('edge' x y)    == True
  -- consistent ('edges' xs)    == True
  -- consistent ('stars' xs)    == True
  -- @
  consistent :: Ord a => Relation a -> Bool
  consistent (SR r) = R.consistent r && r == R.transpose r
  