Graph Theory

Several improvements have been made to the GraphTheory package, including:

DrawGraph has improved performance for large sparse graphs because key subroutines will now use sparse matrices.
IsIsomorphic can now handle both undirected and directed graphs. Edge weights are ignored if the graph is weighted.
Latex was added to generate LaTeX code of a graph using the picture environment.

DrawGraph Performance Improvement

The DrawGraph command has improved performance for large graphs because subroutines GetEdgesColor and GetEdgesThickness now use sparse Matrices when the graph is sparse.

Maple 18: memory used=1.26GiB, alloc change=122.29MiB, cpu time=18.10s, real time=18.23s, gc time=7.25s (Windows)
Maple 17: Runs out of memory
Mathematica^® 9: AbsoluteTiming[GraphPlot[CycleGraph[10^5]]] gives 27.597759 s

Performance Comparison

Graph

Maple 18

Mathematica^® 9

CycleGraph(10^3)

0.124 s

0.235 s

CycleGraph(10^4)

1.140 s

2.226 s

CycleGraph(10^5)

18.10 s

27.59 s

IsIsomorphic Improvements

The IsIsomorphic command did not handle directed graphs in Maple 17. Now, both undirected and directed graphs are handled. In the case of weighted undirected or directed graphs, the edge weights are ignored.

A disconnected example:

Performance Comparison for Directed Graphs

Graph size	Maple 18	Mathematica^® 9
Small	0.031 s	0. s
Medium	0.078 s	791.216897 s
Large	5.57 s	will not finish computation

Notes

Commands: IsIsomorphic (Maple 18) versus IsomorphicGraphQ (Mathematica^® 9)
Small: Random directed unweighted graph with 10 vertices and 20 arc(s)
Medium: Random directed unweighted graph with 100 vertices and 200 arc(s)
Large: Random directed unweighted graph with 987 vertices and 2000 arc(s)

New Latex Command

The new GraphTheory[Latex] command generates code for displaying a graph using the LaTeX picture environment. It handles directed and undirected graphs in both black and white and color. The vertex labels are placed beside the vertices in the LaTeX picture.

In the following example, we create an undirected unweighted soccer ball graph.

We export the soccer ball graph S to a compilable LaTeX file "soccer.tex" written in a temporary directory.

We can also obtain a Maple string of the LaTeX code by specifying an empty string instead of the file name "soccer.tex", as shown next.

The option 'pictureonly' used above is convenient for obtaining the LaTeX picture environment only.

\begin{picture}(300,300)
\linethickness{1pt}
\color[rgb]{0.0,0.0,1.0}\qbezier(60.78,187.36)(62.00,197.59)(63.22,207.82)
\color[rgb]{0.0,0.0,1.0}\qbezier(60.78,187.36)(54.80,168.00)(48.83,148.65)
\color[rgb]{0.0,0.0,1.0}\qbezier(60.78,187.36)(73.15,192.54)(85.53,197.72)
\color[rgb]{0.0,0.0,1.0}\qbezier(63.22,207.82)(47.73,191.76)(32.23,175.70)
\color[rgb]{0.0,0.0,1.0}\qbezier(63.22,207.82)(87.29,226.23)(111.36,244.64)
\color[rgb]{0.0,0.0,1.0}\qbezier(32.23,175.70)(35.77,153.14)(39.31,130.58)
\color[rgb]{0.0,0.0,1.0}\qbezier(32.23,175.70)(22.11,179.19)(12.00,182.69)
\color[rgb]{0.0,0.0,1.0}\qbezier(39.31,130.58)(44.07,139.61)(48.83,148.65)
\color[rgb]{0.0,0.0,1.0}\qbezier(39.31,130.58)(48.50,100.82)(57.70,71.07)
\color[rgb]{0.0,0.0,1.0}\qbezier(48.83,148.65)(55.94,136.80)(63.05,124.95)
\color[rgb]{0.0,0.0,1.0}\qbezier(85.53,197.72)(88.84,186.06)(92.14,174.39)
\color[rgb]{0.0,0.0,1.0}\qbezier(85.53,197.72)(99.57,208.45)(113.61,219.19)
\color[rgb]{0.0,0.0,1.0}\qbezier(92.14,174.39)(105.40,177.59)(118.67,180.79)
\color[rgb]{0.0,0.0,1.0}\qbezier(92.14,174.39)(86.77,157.04)(81.41,139.70)
\color[rgb]{0.0,0.0,1.0}\qbezier(118.67,180.79)(125.67,193.07)(132.67,205.34)
\color[rgb]{0.0,0.0,1.0}\qbezier(118.67,180.79)(127.26,168.36)(135.85,155.92)
\color[rgb]{0.0,0.0,1.0}\qbezier(132.67,205.34)(123.14,212.26)(113.61,219.19)
\color[rgb]{0.0,0.0,1.0}\qbezier(132.67,205.34)(150.02,205.34)(167.36,205.33)
\color[rgb]{0.0,0.0,1.0}\qbezier(113.61,219.19)(122.13,229.93)(130.66,240.67)
\color[rgb]{...

The compiled LaTeX code above generates the following picture in a LaTeX document: