Maple's GraphTheory package was developed by a group of graduate students and faculty at Simon Fraser University under the direction of Michael Monagan starting in 2004.  The design of the package was first presented at the 2005 Maple conference in Waterloo in the summer of 2005.   New commands and improvements, in particular to facilities for drawing graphs, were presented at the 2006 Maple conference.  The first version of the package was released in Maple 11 in 2007 as the GraphTheory package.  Since then further improvements have been added and more improvements will appear in Maple 17 this year. The package supports simple undirected graphs and simple directed graphs, both of which may be weighted.  At this time there is no support for multi-graphs.

It has been a very stimulating experience for me as director of the project.  Graph theory is such a rich area with an inexhaustible list of improvements that one might wish to add and a wide variety of software development issues that needed to address.  We've been fortunate to have many dedicated and very talented graduate students work on the package.  The package itself has a bit of everything.  It has basic tools for creating and manipulating graphs, a subpackage of known special graphs from the literature, tools for creating random and non-isomorphic graphs, for exporting and importing graphs, animations of algorithms for teaching, programs for computing graph properties and graph polynomials, some of which are known to be NP-complete and NP-hard, and lastly, but perhaps most useful, tools for drawing graphs.  This article gives you a taste.  More information within Maple can be found at the main help page ?GraphTheory   and the main example help page ?examples,GraphTheory .

To use the GraphTheory package we first load it.

Here are two graphs with 5 vertices.  The first is a simple undirected graph.  The second is a simple directed graph.  

The two graphs may be input in Maple using the Graph command as shown below.  The difference is that for an undirected graph we input edges in set braces { } and for a directed graph we use square brackets [ ] .

Notice that the default output is a one-line description of the graph.  The two drawings of the graphs above were created with the DrawGraph command as follows.  I'll explain later the style=spring option which two of the students and I worked long hours on.

The package has many commands, because that's the nature of the subject.  Commands are input like other Maple commands. There are commands for testing for properties.  For example the graph G has no Eulerian tour but it is planar.  

The faces computed correspond to the drawing.  [4,1,2,3] means the cycle [4,1,2,3,4], which is the inner square; [4,3,5] is the triangle; and [3,2,1,4,5] is the outside face.  There are commands for testing for structural information that allow you to program with graphs.  Here is the list of neighbors of G, the arrivals and departures for H.  Notice that there is no departure from vertex 5 in H.

Special Graphs

A library of standard special graphs (and some not so standard) is available.  For example, here is the well known Petersen graph.

It is well known that the Petersen graph is not planar but it is 3-colorable.

Each list in C is the list of vertices which have the same color.  Here is how we can color the vertices to visualize the coloring.

Table 1 lists Maple commands for computing polynomials related to graphs.

Here is the Chromatic polynomial for the Petersen graph.  It counts the number of ways a graph G can be colored with colors.

It is a polynomial in λ . You can see that λ = 2 is a root of the polynomial.  That means there are 0 ways to color the graph with 2 colors.

Weighted graphs and networks.

Here is an example of a weighted undirected graph and a weighted directed graph (a network).

The two graphs were input using the following commands.

The two graphs were drawn with the following commands.

Here is a minimal spanning tree of G - it's the 3 edges with weight 1.
 

And here is the maximum flow for the network N which is 4 and a flow matrix achieving that flow.

Well, you can see that there are a lot of commands.  Many of the commands are accessible from the context menu for a graph.  Try right-clicking on one of the graph objects e.g. Graph 6 in (2.18) above.

The Graph command is the main command for creating graphs.  It takes 4 main arguments, which may be given in any order.

   n - the number of vertices

   V - a list of vertex labels (can be integers, symbols or strings)

   D - either directed or undirected

   E - edge information which can be any of
      - set of (weighted) edges,
      - array of neighbor sets,
      - trails or
      - the adjacency matrix.

The Graph command is smart in that you don't need to specify n, V or D if they can be deduced from the edge information.

Here are the four ways to input the cycle (a,b,c,d).

You can also create the graph one or more edges at a time.

Maple uses a list-of-neighbors representation for storing the graph.  It stores the edges as an array of sets of vertices.  You can see Maple's data representation for a graph by using the lprint command.

GRAPHLN(undirected, unweighted, [a, b, c, d], Array(1 .. 4, {1 = {2, 4}, 2 = {1, 3}, 3 = {2, 4}, 4 = {1, 3}}, datatype = anything, storage = rectangular, order = Fortran_order), `GRAPHLN/table/5`, 0)

You can access the information using the IsDirected, IsWeighted, Vertices, Edges, Neighbors, WeightMatrix (for weighted graphs) commands.

You can import a graph from a file in several formats e.g. dimacs, dimacs_relaxed, combinatorica, edges, and dot.
And export it in those formats.

File "Ggraph" created in dimacs format

This created the following text file.

     c Generated by the Maple GraphTheory package

     p edge 4 8

     e 1 2

     e 2 1

     e 1 4

     e 4 1

     e 2 3

     e 3 2

     e 3 4

     e 4 3

Reading that file back into Maple we can recover the graph.

And relabel the vertices 1,2,3,4 with labels a,b,c,d.

The graph drawing commands are

 DrawGraph - main command

 DrawNetwork  - for drawing a network (must identify the source and sink)

 DrawPlanar - for drawing a planar graph

The best drawing is usually obtained using the style=spring option.  Here is Petersen graph and two drawings of the Petersen graph obtained using the style=spring option.  The Petersen graph is one of the graphs in the SpecialGraphs subpackage.

You may have to execute these several times to get these drawings.

These drawings are generated by simulating a physical system where the vertices are modeled as electrons that repel each other and the edges are modeled as springs that attract each other.  Initially the vertices are placed randomly in the unit square and the system (a system of differential equations) is solved to determine the final placement of the vertices.  Here is the soccer ball graph (a bucky ball).  In the first (and default) drawing, the vertex positions are predefined.

Using the style=spring option we generate this drawing.

We also support a 3D option which allows us to place the vertices in 3D and the method automatically finds a 3D representation of a soccer ball.  In this version, the graph can be rotated with the mouse.

As noted, the graphs in the SpecialGraphs package have pre-defined vertex positions for drawing.  You can also specify how a graph is to be drawn by specifying directly the vertex positions. Here is a Canadian example for the (mostly Canadian) cities Vancouver, Calgary, Edmonton, Toronto, Ottawa and Montreal, and Seattle.  (I included Seattle because I'm a Seattle Mariners fan.)

Let's see if we can fix this. (The resulting figure is more faithful to the actual geographic locations.)

That means there are 6 trees with 6 vertices.  We obtained trees by specifying  vertices,  edges and forcing the graphs to be connected.  We can generate graphs for each of them and draw them side by side as follows.

We can restrict to regular graphs (graphs where each vertex has the same degree) as follows.