GraphTheory
A substantial effort was put into Graph Theory for Maple 2023, including improved ability to solve traveling salesman problems, support for multigraphs, new commands for graph computation, and advances in visualization.
withGraphTheory:
Traveling Salesman
Multigraph support
Graph products
Additions to SpecialGraphs
The TravelingSalesman command now makes use of Concorde, a well-known library implementing highly efficient heuristics for solving instances of the traveling salesman problem. This addition considerably increases the size of problems which TravelingSalesman is able to handle.
Example: Using TravelingSalesman with vertexpositions
In the following example, we import a dataset of the 100 largest cities in the continent of Africa (including the island of Madagascar) and ask TravelingSalesman to find a minimal tour of them.
AfricanCities ≔ Importexample/AfricanCities100.tsv,base=datadir,output=Matrix,skiplines=1
G ≔ CompleteGraph convertAfricanCities..,2,list, vertexpositions=AfricanCities..,6,5
G≔Graph 1: an undirected graph with 100 vertices and 4950 edge(s)
With the new vertexpositions option, TravelingSalesman uses edge weights computed from the geometric distance between vertices in the graph layout specified previously when CompleteGraph was called. The new startvertex option allows a particular starting vertex to be specified.
W, T ≔ TravelingSalesman G, vertexpositions,startvertex=Cairo
W,T≔421.032920193835,Cairo,Alexandria,Benghazi,Misratah,Tripoli,Tunis,Algiers,Oran,Tangier,Fez,Rabat,Casablanca,Marrakesh,Agadir,Nouakchott,Dakar,Conakry,Freetown,Monrovia,Bamako,Bobo Dioulasso,Ouagadougou,Niamey,Ilorin,Ibadan,Kumasi,Abidjan,Accra,Lomé,Abomey-Calavi,Lagos,Ikorodu,Benin City,Warri,Owerri,Umuahia,Onitsha,Nnewi,Port Harcourt,Yaoundé,Douala,Libreville,Uyo,Aba,Enugu,Lokoja,Abuja,Kaduna,Jos,Kano,Maiduguri,N'Djamena,Nyala,Bangui,Kisangani,Bunia,Kampala,Mwanza,Kigali,Bujumbura,Bukavu,Mbuji-Mayi,Kananga,Tshikapa,Kinshasa,Brazzaville,Pointe-Noire,Cabinda,Luanda,Benguela,Lubango,Cape Town,Gqeberha (Port Elizabeth),Durban (eThekwini),Vereeniging (Emfuleni),West Rand,Johannesburg,East Rand (Ekurhuleni),Pretoria (Tshwane),Matola,Maputo,Harare,Lusaka,Lubumbashi,Lilongwe,Blantyre,Antananarivo,Nampula,Dar es Salaam,Zanzibar,Mombasa,Nairobi,Mogadishu,Hargeisa,Addis Ababa,Asmara,Omdurman,Khartoum,Giza,Shubra el-Kheima,Cairo
We will illustrate the tour by constructing a subgraph consisting only of the edges included in the optimal tour across G.
TG ≔ Subgraph G, TrailT ;
TG≔Graph 2: an undirected graph with 100 vertices and 100 edge(s)
DrawGraphTG
To better visualize the tour we can combine this with a country map of Africa.
plots:-displayImportexample/AfricaMap.kml,base=datadir,DrawGraphTG,stylesheet=vertexcolor=black
Using TravelingSalesman with an arbitrary weight matrix
The previous example demonstrates the use of TravelingSalesman with edge weights corresponding directly to geometric distances between vertices. In many instances of the traveling salesman problem, the weights do not correspond so directly to the geometry.
Fortunately, TravelingSalesman can also compute a tour when given an arbitrary weight matrix. To illustrate this, let us extend the previous example of a tour of 100 African cities to incorporate the idea that there might be some increased cost associated with traversing an international border.
First let us get the matrix of Euclidean distances from the previous example:
DM ≔ WeightMatrix MakeWeightedG,vertexpositions,metric=Euclidean
Now we can construct a new weight matrix WM in which the weight is doubled whenever the cities connected are in distinct countries.
WM ≔ Matrix upperboundDM, i,j→ifelseAfricanCitiesi,3=AfricanCitiesj,3,DMi,j,2⋅ DMi,j,datatype=double
We can now pass the weight matrix WM directly to TravelingSalesman to get a new tour.
W2, T2 ≔ TravelingSalesman G, WM,startvertex=Cairo
W2,T2≔616.778513706285,Cairo,Shubra el-Kheima,Alexandria,Benghazi,Misratah,Tripoli,Tunis,Algiers,Oran,Fez,Tangier,Rabat,Casablanca,Marrakesh,Agadir,Nouakchott,Dakar,Conakry,Freetown,Monrovia,Bamako,Bobo Dioulasso,Ouagadougou,Niamey,Abidjan,Kumasi,Accra,Lomé,Abomey-Calavi,Lagos,Ikorodu,Ibadan,Ilorin,Benin City,Warri,Port Harcourt,Aba,Uyo,Umuahia,Owerri,Nnewi,Onitsha,Enugu,Lokoja,Abuja,Jos,Kaduna,Kano,Maiduguri,N'Djamena,Bangui,Yaoundé,Douala,Libreville,Kinshasa,Brazzaville,Pointe-Noire,Cabinda,Luanda,Benguela,Lubango,Cape Town,Gqeberha (Port Elizabeth),Durban (eThekwini),Vereeniging (Emfuleni),West Rand,Johannesburg,East Rand (Ekurhuleni),Pretoria (Tshwane),Matola,Maputo,Nampula,Antananarivo,Blantyre,Lilongwe,Harare,Lusaka,Lubumbashi,Mbuji-Mayi,Kananga,Tshikapa,Kisangani,Bunia,Bukavu,Bujumbura,Kigali,Kampala,Mwanza,Dar es Salaam,Zanzibar,Mombasa,Nairobi,Mogadishu,Hargeisa,Addis Ababa,Asmara,Khartoum,Nyala,Omdurman,Giza,Cairo
TG2 ≔ SubgraphG,TrailT2
TG2≔Graph 3: an undirected graph with 100 vertices and 100 edge(s)
This new tour is similar to the previous one in many respects, but notably does not visit Sudan or the Democratic Republic of the Congo twice as the first one did, illustrating the effect of our increased edge weights.
plots:-displayImportexample/AfricaMap.kml,base=datadir,title=none,DrawGraphTG2,stylesheet=vertexcolor=black
Finally we can draw the original tour (in green) and the new tour (in red) to see the effect of the altered weights.
plots:-display DrawGraphTG,stylesheet=edgecolor=darkgreen|DrawGraphTG2,stylesheet=edgecolor=red
GraphTheory now supports multigraphs. That is, graphs in which there may be multiple edges between the same pair of vertices.
MG ≔ Graph4,0200201001020020,multigraph
MG≔Graph 3: an undirected multigraph with 4 vertices and 5 edge(s)
The new command IsMultigraph tests whether a graph is a multigraph.
IsMultigraphMG
true
Many other commands have been updated to support multigraphs.
The Edges command for this graph returns a list, not a set, and repeats the edge between vertices 3 and 4 twice.
EdgesMG
1,2,1,2,2,3,3,4,3,4
EdgeMultiplicityMG,1,2
2
Graph visualization commands such as DrawGraph will draw an integer weight on edges for which the edge multiplicity is greater than 1.
DrawGraphMG
A graph product is a binary operation on graphs which takes two graphs G__1 and G__2 and produces a graph H with the following properties:
The vertex set of H is the Cartesian product VG__1 × VG__2 where VG__1 and VG__2 are the vertex sets of G__1 and G__2, respectively.
VG__2
Two vertices u__1,v__1 and u__2,v__2 of H are connected by an edge, iff some condition about u__1, v__1 ∈ G__1 and u__2, v__2 ∈ G__2 is fulfilled.
Many different graph products have been defined which differ in the condition imposed on the edges. To the existing CartesianProduct and TensorProduct commands, the following new graph products have been added:
Name
Edge Condition
ConormalProduct
u__1 and v__1 share an edge in G__1 or u__2 and v__2 share an edge in G__2
LexicographicProduct
u__1 and v__1 share an edge in G__1, or u__1=v__1 in G__1 and u__2 and v__2 share an edge in G__2
ModularProduct
u__1 and v__1 share an edge in G__1 and u__2 and v__2 share an edge in G__2, or u__1 and v__1 do not share an edge in G__1 and u__2 and v__2 do not share an edge in G__2
StrongProduct
u__1=v__1 in G__1 and u__2 and v__2 share an edge in G__2, or u__1 and v__1 share an edge in G__1 and u__2=v__2 in G__2 or u__1 and v__1 share an edge in G__1 and u__2 and v__2 share an edge in G__2
C ≔ CycleGraph3
C≔Graph 4: an undirected graph with 3 vertices and 3 edge(s)
H ≔ SpecialGraphs:-HouseGraph
H≔Graph 5: an undirected graph with 5 vertices and 6 edge(s)
LP ≔ LexicographicProductC,H
LP≔Graph 6: an undirected graph with 15 vertices and 93 edge(s)
plots:-displayDrawGraph~C|H|LP
Maple 2023 provides support for 6 additional Special Graphs, bringing the total to 119.
withSpecialGraphs:
Bishops's Graph
Bouquet Graph
Dipole Graph
BG46 ≔ BishopsGraph4,5
BG46≔Graph 7: an undirected graph with 20 vertices and 40 edge(s)
DrawGraphBG46, stylesheet = vertexpadding = 12
BG ≔ BouquetGraph5
BG≔Graph 8: an undirected multigraph with 1 vertex, no edges, and 5 self-loops
DrawGraphBG, stylesheet = vertexpadding = 12
DG ≔DipoleGraph2
DG≔Graph 9: an undirected multigraph with 2 vertices and 2 edge(s)
DrawGraphDG, stylesheet = vertexpadding = 12
Hamming Graph
House Graph
Windmill Graph
HG33 ≔ HammingGraph3,3
HG33≔Graph 10: an undirected graph with 27 vertices and 81 edge(s)
DrawGraphHG33,style=spring, stylesheet = vertexpadding = 12
HG ≔HouseGraph
HG≔Graph 11: an undirected graph with 5 vertices and 6 edge(s)
DrawGraphHG,stylesheet=vertexpadding=10
WG ≔ WindmillGraph3,7
WG≔Graph 12: an undirected graph with 15 vertices and 21 edge(s)
DrawGraphWG,stylesheet=vertexpadding=10
Download Help Document
