A Combinatorica csomag kompatibilitási hiányosságai
(a Wolfram Mathematica 8-as verziójában)

Bevezetés

Ebben a munkafüzetben megpróbálok rávilágítani a Mathematica 8 gráfokkal foglalkozó beépített függvényeinek és a Combinatorica csomag gráfokkal foglalkozó függvényeinek eltérő működésére, valamint a kettő közötti kompatibilitási hiányosságokra. Kompatibilitási hiányosságok alatt azt értem, hogy a beépített függvények a csomag betöltése előtt Graph típusú objektumokat kezelnek illetve hoznak létre, a csomag betöltésével viszont ezek az objektumok System`Graph típusú objektumokká változnak, ami különbözik a ,,csomag betöltése utáni” Graph típustól. A csomag betöltése után a beépített függvények csak a System`Graph típusú objektumokat tudják kezelni, a Graph típusú objektumokat nem, és fordítva, a csomag függvényei csak a csomag betöltése utáni Graph típusú objektumokat tudják kezelni, a System`Graph típusú objektumokat nem. A kompatibilitási hiányosságok kiküszöbölése érdekében megadom a két típus közötti mindkét irányú konverzió egy-egy lehetőségét (ToSystemGraph és ToCombinatoricaGraph).

A Combinatorica csomag betöltése nélkül működő függvények
(A Mathematica korábbi verzióiban a Combinatorica csomag részei voltak, de a Mathematica 8-ban már beépített függvények.)

Gráfok létrehozása (a Graph paramétere egy éllista, az AdjacencyGraph-é egy szomszédossági mátrix, az IncidenceGraph-é egy illeszkedési mátrix):

{G=Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4},VertexLabels->"Name"],
AdjacencyGraph[{{0,1,1,0},{1,0,1,1},{1,1,0,1},{0,1,1,0}}],
IncidenceGraph[{{1,1,0,0,0},{1,0,1,1,0},{0,1,1,0,1},{0,0,0,1,1}}]}

Mindhárom függvény Graph típusú objektumot hoz létre:

Head /@%

A System`Graph ugyanúgy működik, mint a Graph (Graph típusú objektumot hoz létre):

System`Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

Head[%]

A GraphPlot kirajzolja a gráfot:

GraphPlot[G]

Az EdgeCount megszámolja az éleit:

EdgeCount[G]

A VertexCount megszámolja a pontjait:

VertexCount[G]

A EdgeList visszaadja az éleinek listáját:

EdgeList[G]

A VertexList visszaadja a pontjainak listáját:

VertexList[G]

A EdgeDelete törli az általunk megadott élt (vagy listával megadott éleket) - új a Mathematica 8-ban:

EdgeDelete[G,3\[UndirectedEdge]4]

A VertexDelete törli az általunk megadott pontot (vagy listával megadott pontokat), és megőrzi a pontok cimkézését - új a Mathematica 8-ban:

VertexDelete[G,3]

A EdgeAdd hozzáadja az általunk megadott élt (vagy listával megadott éleket) - új a Mathematica 8-ban:

EdgeAdd[G,4\[UndirectedEdge]5]

A VertexAdd hozzáadja az általunk megadott pontot (vagy listával megadott pontokat) - új a Mathematica 8-ban:

VertexAdd[G,5]

A ConnectedComponents visszaadja az összefüggő komponensek listáját - új a Mathematica 8-ban:

ConnectedComponents[%]

Az AdjacencyMatrix létrehozza a gráf szomszédossági mátrixát, és egy SparseArray típusú objektumot ad vissza (ritka mátrix):

AdjacencyMatrix[G]

MatrixForm[%]

Az IncidenceMatrix létrehozza a gráf illeszkedési mátrixát, és egy SparseArray típusú objektumot ad vissza (ritka mátrix):

IncidenceMatrix[G]

MatrixForm[%]

A CompleteGraph létrehoz egy teljes gráfot:

CompleteGraph[5]

Most töltsük be a Combinatorica csomagot! (rögtön kapunk egy üzenetet)

<<Combinatorica`

A csomag betöltésével a Graph típusú objektumok System`Graph típusúvá változnak:

Head[G]

Ha felgörgetünk, láthatjuk, hogy a csomag betöltésekor néhány parancs pirosra változik, ami azért van, mert a csomag ,,beárnyékolja” őket (Shadowing in multiple contexts), így a Combinatorica csomagbeli változatuk lesz érvényes (ezt később látni fogjuk), és System`Graph típusú objektumokra nem működnek:

ConnectedComponents[G]

IncidenceMatrix[G]

Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

Ezt könnyen orvosolhatjuk a parancsok System` előtaggal való kiegészítésével:

System`ConnectedComponents[G]

System`IncidenceMatrix[G]

System`Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

A System`Graph a csomag betöltése után már System`Graph típusú objektumot hoz létre:

Head[%]

Azok a parancsok, amelyek nem lettek beárnyékolva, továbbra is (azaz System`Graph típusú objektumokra is) működnek:

GraphPlot[G]

EdgeList[G]

VertexList[G]

EdgeCount[G]

VertexCount[G]

EdgeDelete[G,3\[UndirectedEdge]4]

VertexDelete[G,3]

EdgeAdd[G,4\[UndirectedEdge]5]

VertexAdd[G,5]

AdjacencyMatrix[G]

A Combinatorica csomag függvényei

Gráf létrehozása FromAdjacencyMatrix-szal (paramétere az AdjacencyGraph-hoz hasonlóan egy szomszédossági mátrix):

H=FromAdjacencyMatrix[{{0,1,1,0},{1,0,1,1},{1,1,0,1},{0,1,1,0}}]

Graph típusú objektumot hoz létre:

Head[%]

A csomag betöltése utáni Graph típusú gráfokat nem jeleníti meg a Mathematica automatikusan, de a GraphPlot, vagy a ShowGraph igen:

GraphPlot[H]

ShowGraph[H]

A beárnyékolt parancsok Graph típusú objektumokra jól működnek:

ConnectedComponents[H]

Az IncidenceMatrix ebben az esetben lista típusú mártixot ad vissza SparseArray helyett:

IncidenceMatrix[H]

Az CompleteGraph Graph típusú gráfot hoz létre:

CompleteGraph[5]

ShowGraph[%]

A ToAdjacencyMatrix visszaadja a szomszédossági mátrixát:

ToAdjacencyMatrix[H]

Az M megszámolja a éleit:

M[H]

A V megszámolja a pontjait:

V[H]

Az Edges visszaadja az éleinek listáját (az éleket két elemű lista formájában adja meg):

Edges[H]

A Vertices visszaadja a pontjainak koordinátáit (egy síkba ágyazva - a ShowGraph ezt a beágyazást mutatja):

Vertices[H]

A DeleteEdge törli az általunk megadott élt (csak egy élt lehet vele törölni, és az élt lista formájában kell megadni):

DeleteEdge[H,{3,4}]

ShowGraph[%]

A DeleteEdges törli az általunk megadott élt vagy éleket (az éleket lista formájában kell megadni):

DeleteEdges[H,{{1,3},{3,4}}]

ShowGraph[%]

A DeleteVertex törli az általunk megadott pontot (csak egy pontot lehet vele törölni, a pontot számmal kell megadni), és a VertexDelete-tel ellentétben átcimkézi a gráf pontjait (pontosabban a csomag betöltése utáni Graph típusú gráfok pontjainak cimkézése mindig 1-től n-ig történik, ellentétben System`Graph típusúakkal):

DeleteVertex[H,3]

ShowGraph[%]

GraphPlot[DeleteVertex[H,3],VertexLabeling->True]

A DeleteVertices törli az általunk megadott pontot vagy pontokat (a pontokat szám formájában kell megadni):

DeleteVertices[H,{1,3}]

ShowGraph[%]

Az AddEdge hozzáadja az általunk megadott élt (csak egy élt lehet vele hozzáadni, az élt lista formában kell megadni, továbbá csak olyan élt fogad el, ami a gráf két korábban is létező pontját köti össze, ellentétben az EdgeAdd-del):

AddEdge[H,{1,4}]

ShowGraph[%]

Az AddEdges hozzáadja az általunk megadott élt vagy élelet (az éleket lista formában kell megadni, és szintén csak olyan éleket fogad el, ami a gráf két korábban is létező pontját köti össze):

AddEdges[H,{{1,3},{1,4}}]

ShowGraph[%]

Az AddVertex hozzáadja az általunk megadott pontot (csak egy pontot lehet vele hozzáadni, és a pontot a koordinátáival kell megadni):

AddVertex[H,{1,1}]

ShowGraph[%]

Az AddVertices hozzáadja az általunk megadott pontot vagy pontokat (a pontokat koordinátáikkal kell megadni):

AddVertices[H,{{1,1},{-1,1}}]

ShowGraph[%]

A Cycle létrehoz egy kört:

Cycle[5]

ShowGraph[%]

A GraphJoin összekapcsol két gráfot (az egyik gráf minden pontját összeköti a másik gráf minden pontjával):

GraphJoin[H,CompleteGraph[1]]

ShowGraph[%]

A HamiltonianQ megvizsgálja, hogy tartalmaz-e Hamilton-kört:

HamiltonianQ[H]

A HamiltonianCycle visszaadja egy Hamilton-körét, ha tartalmaz Hamilton-kört (ha nem, akkor üres listát ad vissza):

HamiltonianCycle[H]

A HamiltonianPath visszaadja egy Hamilton-útját, ha tartalmaz Hamilton-utat (ha nem, akkor üres listát ad vissza):

HamiltonianPath[H]

Élek és pontok törlését és hozzáadását végző függvények:

({{Művelet, Combinatorica függvény, Paraméterek, Beépített függvény, Paraméterek}, {Él törlése, DeleteEdge, gráf, él(két elemű lista), EdgeDelete, gráf,él vagy élek listája(x<->y)}, {Élek törlése, DeleteEdges, gráf, élek listája, , }, {Pont törlése, DeleteVertex, gráf, pont(szám), VertexDelete, gráf, pont vagy pontok listája(szám)}, {Pontok törlése, DeleteVertices, gráf, pontok listája, , }, {Él hozzáadása, AddEdge, gráf, él(két elemű lista), EdgeAdd, gráf,él vagy élek listája(x<->y)}, {Élek hozzáadása, AddEdges, gráf, élek listája, , }, {Pont hozzáadása, AddVertex, gráf, pont(koordináták), VertexDelete, gráf, pont vagy pontok listája(szám)}, {Pontok hozzáadása, AddVertices, gráf, pontok listája, , }})

Kompatibilitási hiányosságok

Próbáljuk ki a Combinatorica csomagon kívüli (beépített) függvényeket egy Graph típusú gráfon.
A beépített függvények nem tudják kezelni a Combinatorica csomag betöltése utáni Graph típusú gráfot:

EdgeCount[H]

VertexCount[H]

EdgeList[H]

VertexList[H]

EdgeDelete[H,3\[UndirectedEdge]4]

VertexDelete[H,3]

EdgeAdd[H,4\[UndirectedEdge]5]

VertexAdd[H,5]

AdjacencyMatrix[H]

Megoldás: Az AdjacencyGraph [ ToAdjacencyMatrix [ G ]] parancs System`Graph típusú objektummá alakítja a Graph típusút:

ToSystemGraph[G_]:=AdjacencyGraph[ToAdjacencyMatrix[G]]

H2=ToSystemGraph[H]

Head[%]

Ezt pedig már tudják kezelni a Combinatorica csomagon kívüli (beépített) függvények:

VertexCount[H2]

Most próbáljuk ki a Combinatorica csomag függvényeit egy System`Graph típusú gráfon.
Az Combinatorica csomag függvényei nem tudják kezelni a System`Graph típusú gráfot:

G=System`Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

ShowGraph[G]

ToAdjacencyMatrix[G]

M[G]

V[G]

Edges[G]

Vertices[G]

DeleteEdge[G,{3,4}]

DeleteVertex[G,3]

AddEdge[G,{1,4}]

AddVertex[G,{1,1}]

GraphJoin[G,System`CompleteGraph[1]]

HamiltonianQ[G]

HamiltonianCycle[G]

HamiltonianPath[G]

A FromAdjacencyMatrix[AdjacencyMatrix[G]] nem működik, mert a FromAdjacencyMatrix nem tudja kezelni a SparseArray típusú ritka mátrixot:

FromAdjacencyMatrix[AdjacencyMatrix[G]]

Megoldás: A Normal parancs lista típusú mátrixá alakítja a SparseArray típusú ritka mátrixot:

Normal[AdjacencyMatrix[G]]

Tehát a FromAdjacencyMatrix[Normal[AdjacencyMatrix[G]]] parancs Graph típusú objektummá alakítja a System`Graph típusút:

ToCombinatoricaGraph[G_]:=FromAdjacencyMatrix[Normal[AdjacencyMatrix[G]]]

G2=ToCombinatoricaGraph[G]

Head[%]

Ezt pedig már tudják kezelni a Combinatorica csomag függvényei:

V[G2]

Gráfok beolvasása külső állományból

A gráfokat egy graph6 formátumú (.g6 kiterjesztésű) állományból olvassuk be az Import paranccsal:

SetDirectory[NotebookDirectory[]];
graphs=Import["graph4c.g6"]

F=graphs[[5]]

A beolvasott gráfok System`Graph típusúak:

Head[%]

Így a Combinatorica csomag függvényei nem tudják kezelni:

V[F]

ToAdjacencyMatrix[F]

HamiltonianQ[F]

Megoldás: Az Import szomszédossági mátrixot is be tud olvasni, amiből pedig mindkét típusú gráfot elő tudjuk állítani:

am=Import["graph4c.g6",{"AdjacencyMatrix",5}]

F1=AdjacencyGraph[am]

F2=FromAdjacencyMatrix[am]

GraphPlot[%]

Ebben a formában pedig már tudják kezelni a Combinatorica csomag függvényei is:

V[F2]

ToAdjacencyMatrix[F2]

HamiltonianQ[F2]

Megjegyzés: A függvények listája a teljesség igénye nélkül készült, csak a Combinatorica csomag kompatibilitási hiányosságaira hivatottak rávilágítani.