The Vertex-Set and Edge-Set of a Graph
========================================

Introduction
-------------

Let :math:`G` be a graph on :math:`n` vertices and :math:`m` edges whose 
vertex-set is :math:`V = \{v_1, \ldots, v_m\}` and edge-set is 
:math:`E = \{e_1, \ldots, e_m\}`. A graph created by Magma consists of three 
objects: the *vertex-set* :math:`V`, the *edge-set* :math:`E` and the graph 
:math:`G` itself. The vertex-set and edge-set of a graph are *enriched* sets 
and consequently constitute types. The vertex-set and edge-set are returned as 
the second and third arguments, respectively, by all functions which create 
graphs. Alternatively, a pair of functions are provided to extract the 
vertex-set and edge-set of a graph :math:`G`. The main purpose of having 
vertex-sets and edge-sets as types is to provide a convenient mechanism for 
referring to vertices and edges of a graph. Here, the functions applicable to 
vertex-sets and edge-sets are described.



Creating Edges and Vertices
----------------------------

.. magma:function:: EdgeSet(G)
   :input_types: Grph
   :output_types: GrphEdgeSet

   Given a graph :math:`G`, return the edge-set of :math:`G`.


.. magma:function:: Edges(G)
   :input_types: Grph
   :output_types: {@ GrphEdge @}

   A set :math:`E` whose elements are the edges of the graph :math:`G`. Note
   that this creates an indexed set and not the edge-set of :math:`G`, in
   contrast to the function :function:`function__EdgeSet__Grph__GrphEdgeSet`.


.. magma:function:: VertexSet(G) 
   :input_types: Grph
   :output_types: GrphVertSet

   Given a graph :math:`G`, return the vertex-set of :math:`G`.


.. .. magma:function:: Vertices(G) : Grph -> \brace GrphVert\rbrace
..    :input_types:
..    :output_types:

..    A set :math:`V` whose elements are the vertices of the graph :math:`G`. In
..    contrast to the function ``VertexSet``, this function returns
..    the collection of vertices of :math:`G` in the form of an indexed set.


.. \sigop
.. V ! v : GrphVertSet, . -> GrphVert


.. Given the vertex-set :math:`V` of the graph :math:`G` and an element :math:`v` 
.. of the support of :math:`V`, create the corresponding vertex of :math:`G`.


.. \sigop
.. V . i : GrphVertSet, RngIntElt -> GrphVert


.. Given a vertex-set :math:`V` and an integer :math:`i` such that 
.. :math:`1 \leq i \leq \#V`, create the vertex :math:`v_i` of :math:`V`.


.. .. magma:function:: Index(v) : GrphVert -> RngIntElt


.. Given a vertex :math:`v` of some graph :math:`G`, return the index of :math:`v` 
.. in the (indexed) vertex-set of :math:`G`.


.. \sigop
.. E ! \brace u, v\rbrace : GrphEdgeSet, { . } -> GrphEdge


.. Given the edge-set :math:`E` of the graph :math:`G` and objects :math:`u`, :math:`v` 
.. belonging to the support of :math:`G`, which correspond to adjacent 
.. vertices, create the edge :math:`uv` of :math:`G`.


.. \sigop
.. E ! [u, v] : GrphEdgeSet, [ . ] -> GrphEdge


.. Given the edge-set :math:`E` of the digraph :math:`G` and objects :math:`u`, :math:`v` 
.. belonging to the support of :math:`G`, which correspond to adjacent 
.. vertices, create the edge :math:`uv` of :math:`G`.


.. \sigop
.. E . i : GrphEdgeSet, RngIntElt -> GrphEdge


.. Given an edge-set :math:`E` and an integer :math:`i` such that :math:`1 \leq i \leq \#E`, 
.. create the :math:`i`-th edge of :math:`E`.

.. \beginex{EdgeSets}%\>-----------------------------------------------------
.. The construction of vertices and edges is illustrated using the
.. Odd Graph, :math:`O_{3}`.
.. and then form its standard graph. 
.. \begincode
.. > S := Subsets({1..5}, 2);                                   
.. > O3, V, E := Graph< S | { {u,v} : u,v in S | IsDisjoint(u, v) } >;
.. > VertexSet(O3);
.. Vertex-set of O3
.. > Vertices(O3); 
.. {@ { 1, 5 }, { 2, 5 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, { 3, 5 }, 
.. { 2, 3 }, { 1, 2 }, { 3, 4 }, { 4, 5 } @}
.. > EdgeSet(O3);
.. Edge-set of O3
.. > Edges(O3);  
.. {@ {{ 1, 5 }, { 2, 4 }}, {{ 1, 5 }, { 2, 3 }}, {{ 1, 5 }, { 3, 4 }}, 
.. {{ 2, 5 }, { 1, 3 }}, {{ 2, 5 }, { 1, 4 }}, {{ 2, 5 }, { 3, 4 }}, 
.. {{ 1, 3 }, { 2, 4 }}, {{ 1, 3 }, { 4, 5 }}, {{ 1, 4 }, { 3, 5 }}, 
.. {{ 1, 4 }, { 2, 3 }}, {{ 2, 4 }, { 3, 5 }}, {{ 3, 5 }, { 1, 2 }}, 
.. {{ 2, 3 }, { 4, 5 }}, {{ 1, 2 }, { 3, 4 }}, {{ 1, 2 }, { 4, 5 }} @}
.. > u := V!{1, 2};
.. > u, Type(u);
.. {1, 2} GrphVert
.. > Index(u);
.. 8
.. > x := E!{ {1,2}, {3,4}};
.. > x, Type(x);
.. {{ 1, 2 }, { 3, 4 }} GrphEdge
.. \endcodex


.. Operations on Vertex-Sets and Edge-Sets
.. ---------------------------------------------

.. For each of the following operations, 
..    :math:`S` and :math:`T` may be interpreted as either
..    the vertex-set or the edge-set of the graph :math:`G`. 
.. The variable :math:`s` may be
..    interpreted as either a vertex or an edge.  
.. The edge-set and vertex-set
..    support all the standard set operations.


.. \sigopunno
.. \# S : GrphVertSet -> RngIntElt

.. \sigopun
.. \# S : GrphEdgeSet -> RngIntElt


.. The cardinality of the set :math:`S`.

.. \sigopno
.. s in S : GrphVert, GrphVertSet -> BoolElt

.. \sigop
.. s in S : GrphEdge, GrphEdgeSet -> BoolElt

.. Return ``true``{} if the vertex (edge) :math:`s` lies in the vertex-set (edge-set) :math:`S`,
.. otherwise ``false``.

.. \sigopno
.. s notin S : GrphVert, GrphVertSet -> BoolElt

.. \sigop
.. s notin S : GrphEdge, GrphEdgeSet -> BoolElt

.. Return ``true`` if the vertex (edge) :math:`s` does not lie in the vertex-set (edge-set) :math:`S`, otherwise ``false``.

.. \sigopno
.. S subset T : GrphVertSet, GrphVertSet -> BoolElt

.. \sigop
.. S subset T : GrphEdgeSet, GrphEdgeSet -> BoolElt

.. Return ``true`` if the vertex-set (edge-set) :math:`S` is contained in the vertex-set
.. (edge-set) :math:`T`, otherwise ``false``.

.. \sigopno
.. S notsubset T : GrphVertSet, GrphVertSet -> BoolElt

.. \sigop
.. S notsubset T : GrphEdgeSet, GrphEdgeSet -> BoolElt

.. Return ``true`` if the vertex-set (edge-set) :math:`S` is not contained in the
.. vertex-set (edge-set) :math:`T`, otherwise ``false``.

.. \sigopno
.. S eq T : GrphVertSet, GrphVertSet -> BoolElt

.. \sigop
.. S eq T : GrphEdgeSet, GrphEdgeSet -> BoolElt

.. Return ``true`` if the vertex-set (edge-set) :math:`S` is equal to the vertex-set
..   (edge-set) :math:`T`.

.. \sigopno
.. s eq t : GrphVert, GrphVert -> BoolElt

.. \sigop
.. s eq t : GrphEdge, GrphEdge -> BoolElt

.. Returns ``true`` if the vertex (edge) :math:`s` 
..   is equal to the vertex (edge) :math:`t`.

.. \sigopno
.. S ne T : GrphVertSet, GrphVertSet -> BoolElt

.. \sigop
.. S ne T : GrphEdgeSet, GrphEdgeSet -> BoolElt

.. Returns ``true`` if the vertex-set (edge-set) :math:`S` 
..   is not equal to the vertex-set (edge-set) :math:`T`.

.. \sigopno
.. s ne t : GrphVert, GrphVert -> BoolElt

.. \sigop
.. s ne t : GrphEdge, GrphEdge -> BoolElt

.. Returns ``true`` if the vertex (edge) :math:`s` 
..   is not equal to the vertex (edge) :math:`t`.

.. .. magma:function:: ParentGraph(S) : GrphVertSet -> Grph

.. .. magma:function:: ParentGraph(S) : GrphEdgeSet -> Grph

.. Return the graph :math:`G` for which :math:`S` is the vertex-set (edge-set).

.. .. magma:function:: ParentGraph(s) : GrphVert -> Grph

.. .. magma:function:: ParentGraph(s) : GrphEdge -> Grph

.. Return the graph :math:`G` for which :math:`s` is a vertex (edge).

.. .. magma:function:: Random(S) : GrphVertSet -> GrphVert

.. .. magma:function:: Random(S) : GrphEdgeSet -> GrphEdge

.. Choose a random element from the vertex-set (edge-set) :math:`S`.

.. .. magma:function:: Representative(S) : GrphVertSet -> GrphVert

.. .. magma:function:: Rep(S) : GrphVertSet -> GrphVert

.. .. magma:function:: Representative(S) : GrphEdgeSet -> GrphEdge

.. .. magma:function:: Rep(S) : GrphEdgeSet -> GrphEdge

.. Choose some element from the vertex-set (edge-set) :math:`S`.

.. \siglit{for}
.. for x in S do ... end for;

.. The vertex-set (edge-set) :math:`S` may appear as the 
..   range in the ``for``-statement.

.. \siglit{for-random}
.. for random x in S do ...\ end for;

.. The vertex-set (edge-set) :math:`S` may appear as the 
..   range in the ``for random`` - statement. 


.. Operations on Edges and Vertices
.. ---------------------------------

.. .. magma:function:: EndVertices(e) : GrphEdge -> \brace GrphVert\rbrace

.. .. magma:function:: EndVertices(e) : GrphEdge -> [ GrphVert ]

.. Given an edge :math:`e` belonging to the graph :math:`G`, return a set
.. containing the two end-vertices of :math:`e`.
.. If :math:`G` is a digraph return the two end-vertices in a sequence.

.. .. magma:function:: InitialVertex(e) : GrphEdge -> GrphVert


.. Given an undirected or directed 
..   edge :math:`e` from vertex :math:`u` to vertex :math:`v`, return  vertex :math:`u`. 
.. This is useful in the undirected case since it indicates, where relevant,
..   the direction
..   in which the edge has been traversed.

.. .. magma:function:: TerminalVertex(e) : GrphEdge -> GrphVert

.. Given an undirected or directed  edge :math:`e` from vertex :math:`u` 
..   to vertex :math:`v`, return  vertex :math:`v`.
.. This is useful in the undirected case since it indicates, where relevant,
..   the direction
..   in which the edge has been traversed.

.. .. magma:function:: IncidentEdges(u) : GrphVert -> \brace GrphEdge\rbrace

.. Given a vertex :math:`u` of a graph :math:`G`, return the set of all edges 
..   incident with the vertex :math:`u`.
.. If :math:`G` is directed, then the set consists of 
..   all the edges incident into :math:`u` and from :math:`v`.