Graph Theory Updates - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 18 : Graph Theory Updates

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

IsIsomorphic Improvements

New Latex Command

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.

> 

with⁡GraphTheory:

> 

with⁡SpecialGraphs:

> 

G:=CycleGraph⁡105:

> 

CodeTools:-Usage⁡DrawGraph⁡G:

– 

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.

> 

G1:=Graph⁡directed,Trail⁡1,2,3,1,4,5

G1:=Graph 1: a directed unweighted graph with 5 vertices and 5 arc(s)

(1)
> 

G2:=Graph⁡directed,Trail⁡1,2,3,4,5,3

G2:=Graph 2: a directed unweighted graph with 5 vertices and 5 arc(s)

(2)
> 

G3:=Graph⁡directed,Trail⁡3,4,5,3,1,2

G3:=Graph 3: a directed unweighted graph with 5 vertices and 5 arc(s)

(3)
> 

DrawGraph⁡G1,G2,G3,width=3,style=circle

> 

IsIsomorphic⁡G1,G2

false

(4)
> 

IsIsomorphic⁡G2,G3

false

(5)
> 

IsIsomorphic⁡G1,G3,'φ'

true

(6)
> 

φ

1=3,2=4,3=5,4=1,5=2

(7)

A disconnected example:

> 

G:=Graph⁡directed,Trail⁡a,b,c,a,Trail⁡d,e,f,Trail⁡g,h,g

G:=Graph 4: a directed unweighted graph with 8 vertices and 7 arc(s)

(8)
> 

H:=Graph⁡directed,Trail⁡a,b,a,Trail⁡c,d,e,c,Trail⁡f,g,h

H:=Graph 5: a directed unweighted graph with 8 vertices and 7 arc(s)

(9)
> 

DrawGraph⁡G,H,width=2,style=circle

> 

IsIsomorphic⁡G,H,'φ'

true

(10)
> 

φ

a=c,b=d,c=e,d=f,e=g,f=h,g=a,h=b

(11)

 

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.

> 

S:=SoccerBallGraph⁡

S:=Graph 1: an undirected unweighted graph with 60 vertices and 90 edge(s)

(12)
> 

DrawGraph⁡S

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

> 

Latex⁡S,FileTools:-JoinPathFileTools:-TemporaryDirectory, soccer.tex,300,300,true

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.

> 

lstring:=Latex⁡S,,300,300,true,'pictureonly'=true:

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

> 

printf⁡%.1500s...,lstring

\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:

See Also

GraphTheory

GraphTheory[DrawGraph]

GraphTheory[IsIsomorphic]

GraphTheory[Latex]