This help page describes implementation details of the GraphTheory package and the internal data structure for representing graphs.

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 is one of undirected or directed, indicating whether the graph is undirected or directed, respectively.

W is one of unweighted or weighted, indicating whether the graph is weighted or unweighted, respectively. If W=unweighted then M is the integer 0. Otherwise if W=weighted then M is a 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 the integer 0 or a Matrix of integer or floating-point edge weights

Given a graph G, you can examine this internal structure by executing lprint(G).

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

IsDirected(G) returns true if G is a directed graph and false otherwise.

IsWeighted(G) returns true if G is a weighted graph and false otherwise

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 $u=V_i$ and $v=V_j$ are two vertices in the graph, the edge $\left\{u\,v\right\}$ (or arc $\left[u\,v\right]$) is in the graph if and only if the integer j is in the set of integers $A_i$.  The Edges, Neighbors, Arrivals, Departures, and AdjacencyMatrix commands all return this edge information in different formats.

You can 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 GetVertexPositions and SetVertexPositions commands.

Further information about the design of the package and the algorithms used in the package available in the two references below.

Farr, Khatarinejad, Khodadad, Monagan. "A Graph Theory Package for Maple." Proceedings of the 2005 Maple Conference, Maplesoft, July 2005: 260-271. Available at http://www.cecm.sfu.ca/CAG/papers/GTpaper.pdf

Ebrahimi, Ghebleh, Javadi, Monagan, Wittkopf. "A Graph Theory Package for Maple, Part II: Graph Coloring, Graph Drawing, Support Tools, and Networks." Maple Conference 2006 Proceedings, Maplesoft, July 2006: 99-112. Available at http://www.cecm.sfu.ca/CAG/papers/GT2006.pdf