The GraphTheory package is a collection of routines for creating graphs, drawing graphs, manipulating graphs, and testing graphs for properties. The graphs are sets of vertices (nodes) connected by edges. The package supports both directed and undirected graphs but not multigraphs. The edges in the graphs may be weighted or unweighted.

The main command for creating undirected graphs is the Graph command. The main command for creating directed graphs is the Digraph command.

To draw a graph use the DrawGraph command.  The output is a Maple plot.

To test if a Maple object G is a graph use the test: type(G,GRAPHLN).

The ImportGraph and ExportGraph commands are for reading a graph from, and writing a graph to, a file in one of the supported data formats.

The following commands are essential for working with large graphs: HasEdge, HasArc, AddEdge, AddArc, DeleteEdge, DeleteArc.

The SpecialGraphs package contains a library of pre-defined graphs and the RandomGraphs package has routines for randomly generating graphs.

The GraphTheory examples worksheet has a guided tour of the package.

The data structure for representing a graph is a Maple function of the form GRAPHLN( D, W, V::list, A::Array, T::table, M::{0,Matrix} ) where

D = undirected implies the graph is undirected

D = directed implies the graph is directed

W = unweighted implies the graph is unweighted and M is the integer 0

W = weighted implies the graph is weighted and M is of type Matrix

V is a list of integers, symbols or strings (the vertex labels).

A is an Array of sets of integers (the edges of the graph)

T has information about the graph, each vertex and each edge (see below)

M is either 0 or a Matrix of integer or floating point edge weights

The following commands give the user direct access to these fields.

IsDirected(G) returns true if D=directed and false if D=undirected.

IsWeighted(G) returns true if W=weighted and false if W=unweighted.

Vertices(G) returns V

WeightMatrix(G) returns M if G is weighted and an error otherwise.

The edges in the graph are implicitly defined by A.  If  and  are two vertices in the graph, the edge  (or arc ) is in the graph if and only if the integer j is in the set of integers .  The Edges, Neighbors, Arrivals, Departures, and AdjacencyMatrix commands all return this edge information in different formats.

You may attach arbitrary information to the vertices of the graph, the edges of the graph, or the graph as a whole.  This is done using attributes and the information is stored in the table T. See the GraphAttributes help page, as well as the GetVertexPosition and SetVertexPosition commands.

The following is a list of the commands in the main GraphTheory package.

Each command in the GraphTheory package can be accessed by using either the long form or the short form of the command name in the command calling sequence.  For example, if G is a graph you may use either GraphTheory[IsPlanar](G) or with(GraphTheory); then IsPlanar(G).

Because the underlying implementation of the GraphTheory package is a module, it is possible to use the form GraphTheory:-command to access a command from the package. For more information, see Module Members.