# Graph theory

See the Sage wiki page http://wiki.sagemath.org/graph_survey for an excellent survey
of exisiting graph theory software.

## Networkx

Networkx (http://networkx.lanl.gov)
“is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks”.
More details can also be found on
http://wiki.sagemath.org/graph_survey or in Robert Miller’s
SageDays 3 talk.

sage: C = graphs.CubeGraph(4)

Now type
`C.show(vertex_labels=False, vertex_size=60, graph_border=True, figsize=[9,8])`
to view this with some of the options.

The digraph below is a \(3\)-cycle with vertices
\(\{0,1,2\}\) and edges \(0\rightarrow 1\),
\(1\rightarrow 2\), \(2\rightarrow 0\):

sage: D = DiGraph( { 0: [1], 1: [2], 2: [0]} )

Type `D.show()` to view this.

## Cayley graphs

includes wrappers to many NetworkX commands, written mainly by
Emily Kirkman and Robert Miller. The implementation of Cayley
graphs was written by Bobby Moretti and Robert Miller.

sage: G = DihedralGroup(5)
sage: C = G.cayley_graph(); C
Digraph on 10 vertices
sage: C.diameter()
3
sage: C.girth()
2
sage: C.automorphism_group().order()
10
sage: len(C.edges())
20

## Graphs from adjacency matrices

To construct the graph G with \(n \times n\) adjacency
matrix \(A\), you want a graph \(X\) so that the
vertex-set of G is \(\{1,..., n\}\), and \([i,j]\)
is an edge of G if and only if \(A[i][j] = 1\).

Here is an example of the syntax in (copied from Robert Miller’s
SageDays 3 talk): Define the distance \(d(x,y)\) from \(x\) to
\(y\) to be the minimum length of a (directed) path in Gamma
joining a vertex \(x\) to a vertex \(y\) if such a path
exists, and \(-1\) otherwise.
A diameter of \(-1\) is returned if G is not (strongly)
connected. Otherwise, the diameter of G is equal to the maximum
(directed) distance \(d(x,y)\) in G (as \(x\) and
\(y\) range over all the vertices of G).

sage: M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ])
sage: # (the order is the number of edges)
sage: G = Graph(M); G.order()
3
sage: G.distance(0,2)
1
sage: G.diameter()
1