Introduction
=============

.. _graph-intro:


A **simple graph** is a graph in which each edge joins two distinct vertices 
and two distinct vertices are joined by at most one edge. A **simple digraph**,
whose edges are directed, is defined in an analogous manner. Thus, loops and
multiple edges are not permitted in simple graphs and simple digraphs. A graph
(digraph) with loops and/or multiple edges joining a fixed pair of vertices is 
called a **multigraph** (resp. **multidigraph**). A multidigraph whose edges 
are assigned a capacity is more commonly called a **network**.

In this chapter the term "graph" is used when referring to a  simple undirected 
graph, while the term "digraph" is used when referring to a simple directed 
graph. Sometimes the term "graph" is used as the generic term for the incidence 
structure on vertices and edges. Such uses should be clear from the context in 
which they occur.

There are five Magma graph objects: the undirected simple graph of type 
``GrphUnd``, the directed simple graph of type ``GrphDir``, the undirected 
multigraph of type ``GrphMultUnd``, the directed multigraph of type 
``GrphMultDir``, and the network of type ``GrphNet``. The simple graphs are all 
of type ``Grph**``, while the multigraphs (including the network) are of type 
``GrphMult**``. There is a caveat here with respect to simple digraphs and 
loops:  for historical reasons, Magma allows loops in digraphs.

Simple graphs and digraphs are covered in this chapter, while multigraphs, 
multidigraphs are covered in Chapter MultiGraph and networks in Chapter Network.
All types of graphs may have vertex labellings and/or edge labellings.
In addition, assigning weights and/or capacities to graph edges is also 
possible, thus allowing to run shortest-paths and flow-based algorithms over 
the graphs.

Importantly, from the present version (V2.11) onwards, all the standard graph 
construction functions (see Subsections Graph-subsec:subsup and 
Graph-subsec:incr) respect the graph's support set and vertex and edge 
decorations. That is, the resulting graph will have a support set and vertex 
and edge decorations compatible with the original graph and the operation 
performed on that graph.

Magma employs two distinct data structures for representing graphs. 
A graph may be represented in the form of an adjacency matrix (the dense 
representation) or in the form of an adjacency list (the sparse representation).
The latter is better suited for sparse graphs and for algorithms which have 
been designed with the adjacency list representation in mind. An advantage of 
the sparse representation is the possibility of creating much larger (sparse) 
graphs than would be possible using the dense representation, since memory 
requirements for the adjacency list representation is linear in the number of 
edges, while memory requirements for the adjacency matrix representation is 
quadratic in the number of vertices (order) of the graph. This is covered in 
detail in Section Graph-subsec:graph-size.

Further, multigraphs and multidigraphs (and networks) may only be represented 
by an adjacency list since they may contain multiple edges. Users have control 
over the choice of representation when creating simple graphs or digraphs. If 
no indication is given, simple graphs and digraphs are *always* created with 
the dense representation. At the time of the present release (V2.11), a 
significant part of Magma functions are able to work directly with either of 
the representations. However, wherever necessary, a graph will be converted 
internally to whichever representation is required by a given function. We 
emphasize that this process is completely transparent to users and 
**requires no intervention on their part**.

For a concise and comprehensive overview on graph theory and algorithms, the 
reader is referred to cite even; in cite corleiri they'll find a clear exposure 
of some graph algorithms, and cite amo is the recommended reference for flow 
problems in graphs.