YAGS - Yet Another Graph System (also Yttrium Aluminium GarnetS) is a GAP package for dealing with graphs, in the sense of Graph Theory (not bar graphs, pie charts nor graphs of functions). Hence our graphs are ordered pairs G=(V,E), where V is a finite set of vertices and E is a finite set of edges which are (ordered or unordered) pairs of vertices.
YAGS was designed to be useful for research on graphs theory and clique graphs. It is a very functional, full-featured system; a system adequate for rapid prototyping of algorithms; and it is a quick, easy-to-use way, for testing the rapidly changing working conjectures which are typical of the research process.
YAGS offers an ample set of functions (Appendix B); a graph-drawing subsystem (Draw (B.4-15)); many methods for dealing with graph homomorphism (Chapter 5); an Object-Oriented approach that simplifies the task of working with several different graph categories (Chapter 4); and a generic backtracking subsystem useful to solve many combinatorial problems easily (Chapter 6).
If you are fond of git and you already installed GAP, then you could clone our repository as usual (here we assume that GAP-DIR is your GAP installation directory):
git clone http://github.com/yags/yags.git GAP-DIR/pkg/yags
Otherwise, you may follow these installation instructions:
Install GAP following the instructions at http://www.gap-system.org/.
Obtain YAGS from its repository here http://xamanek.izt.uam.mx/yags/yags.zip or here https://github.com/yags/yags/archive/v0.0.5.zip.
Unpack YAGS: the contents of the zip file should go under GAP-DIR/pkg/yags/. Here, we assume that GAP-DIR is your GAP installation directory.
Test YAGS by running GAP, loading YAGS and executing a few basic commands in a terminal:
> gap --- some GAP info here --- gap> RequirePackage("yags"); Loading YAGS - Yet Another Graph System, Version 0.0.5. Copyright (C) 2019 by the YAGS authors; for details type: ?yags:authors This is free software under GPLv3; for details type: ?yags:copyright true gap> CliqueNumber(Icosahedron);NumberOfCliques(Icosahedron); 3 20 gap>
(Optional) Make us happier by sending us a brief installation notification to yags@xamanek.izt.uam.mx and subscribing to YAGS's distribution list: http://xamanek.izt.uam.mx/yagsnews/
Did it work? Congratulations! Otherwise, consider the following troubleshooting issues:
Is GAP working?
Make sure it is. Follow carefully GAP's installation and troubleshooting procedures.
Is the installation directory correct?
The GAP's installation directory, GAP-DIR, is typically something like /opt/gap4r8/ (in MS Windows it may look like C:\gap4r8\). If this is the case, the YAGS's installation directory, YAGS-DIR, is /opt/gap4r8/pkg/yags/ (in MS Windows, it would be C:\gap4r8\pkg\yags\). Then, the full path for YAGS's info file PackageInfo.g should be /opt/gap4r8/pkg/yags/PackageInfo.g (or C:\gap4r8\pkg\yags\PackageInfo.g)
Are you using GRAPE?
GRAPE and YAGS are incompatible: they can not be loaded at the same time. If you had an initialization file that loads GRAPE automatically, you should disable it in order to use YAGS. Alternatively, the command gap -r starts gap disabling any user-specific configuration files.
Unauthorized to access GAP's directories?
The installation procedure above assumed that you have full access to your computer (i.e. that you are the root of the system or that you are using your PC or Mac). If this is not the case, you can also install YAGS under your user directory. For instance, if your user directory is /home/joe/ then you can create a subdirectory /home/joe/gaplocal/ and hence your YAGS's installation directory will be /home/joe/gaplocal/pkg/yags/. Then you can start GAP using gap -l ";/home/joe/gaplocal" so that GAP knows where your YAGS is.
This tutorial assumes that you already installed GAP and YAGS; and that you have some basic understanding of GAP: user interface, the read-eval-print loop, arithmetic operations, and lists. It is strongly recommended that you have some working directory, WORKING-DIR, different from your GAP's and YAGS's installation directories. For instance, if your home directory is /home/joe/ your working directory could be /home/joe/Yags/. Then you should open a terminal, move to your working directory, start GAP and then, load YAGS:
/home/joe> cd Yags /home/joe/Yags> gap --- some GAP info here --- gap> RequirePackage("yags"); gap> RequirePackage("yags"); Loading YAGS - Yet Another Graph System, Version 0.0.5. Copyright (C) 2019 by the YAGS authors; for details type: ?yags:authors This is free software under GPLv3; for details type: ?yags:copyright true gap>
The exact appearance of your system prompt (/home/joe> and /home/joe/Yags/> in the example) may be different depending on your system, but the commands 'cd Yags' and 'gap' are actually the same in all supported systems (assuming your working directory exists and is named 'Yags'). From there (starting with the command 'RequirePackage("yags");') everything happens within GAP and hence it is system-independent.
Now we want to define some graph. Say we have the list of edges of the desired graph:
{ { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 1 }, { 1, 5 }, { 5, 4 } }
We can put those edges in a list and then construct the graph:
gap> list:=[[1,2],[2,3],[3,4],[4,1],[1,5],[5,4]]; [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ], [ 1, 5 ], [ 5, 4 ] ] gap> g:=GraphByEdges(list); Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] )
Note that GAP uses brackets ('[' and ']') instead of braces ('{' and '}') to represent sets and lists (actually, in GAP a set is simply an ordered list). Note also that in GAP 'list' and 'List' are two different things and you can not use the latter since it is a reserved word of GAP. In general, it is better for you to use lowercase names for your variables, to avoid name clashes, since all functions in GAP and YAGS start with an uppercase letter.
The result in the previous example says that it is a graph, and a simple graph. By default all graphs in YAGS are simple (no loops, no arrows, no parallel edges, only plain undirected edges), in Chapter 4 we explain how to work with other types of graphs, like digraphs, loopless graphs, and graphs that may have loops (but no parallel edges are supported in YAGS at all). In this gentle tutorial all our graphs are simple.
The result also says, that the just constructed graph g have 5 vertices and 6 edges. The reported list of adjacencies means that the vertex 1 is adjacent (connected by an edge) to 2, 4 and 5, that the vertex 2 is adjacent to 1 and 3 and so on. To be sure, we can draw our graph and check if it is the intended graph:
gap> Draw(g);
A separate window appears with an editable drawing of the graph (but the graph itself is not editable here). On that window, type: 'D' (toggle dynamics on/off), 'R' (toggle repulsion on/off), 'L' (toggle labels on/off) and 'F' (fit graph into window) to obtain a nice drawing (the initial one is random). The full list of keyboard commands for the Draw window is displayed when typing 'H' (toggle help message). Besides these keyboard commands, you can use your mouse in obvious ways to edit the drawing.
To quit, type 'S'. The drawing is stored within the graph g and remembered by YAGS in case you want to draw the graph again.
If you are new to GAP, it may be worth mentioning that you need not remember or type all the full names of every YAGS operation: GAP supports command completion. For instance, if you type Path and then hit the <TAB> key, GAP automatically completes the prefix to the unique command that completes it, namely: PathGraph. If, on the other hand, the prefix has several possible completions, then GAP simply beeps, but a second <TAB> makes GAP respond with a list of possible completions, so you can then type some additional keys and perhaps type <TAB> again, and so on.
gap> GraphBy<TAB><TAB> GraphByAdjMatrix GraphByAdjacencies GraphByCompleteCover GraphByEdges GraphByRelation GraphByWalks gap> GraphBy
Also, the <UP> and <DOWN> keys are useful to bring back (and perhaps edit) some commands typed earlier in your GAP session. As with any command in GAP/YAGS, in case of doubt, you can always access the online help by typing:
gap> ?yags:draw Help: several entries match this topic - type ?2 to get match [2] [1] yags: Draw [2] yags: Drawing gap> ?1 B.1-55 Draw ‣ Draw( G ) ───────────────────────────────────────────── operation Takes a graph G and makes a drawing of it in a separate window. The user can then view and modify the drawing and finally save the vertex coordinates of the drawing into the graph G. --- many more lines here ---
Here, '?' specifies that we want help; 'yags:' specifies on which manual book we want to search (YAGS's book in this case) and 'draw' specifies the topic we would like to be informed about. As it is common, there are more than one place with information on our topic, hence we choose among the options with '?1' in the next command line. It is not necessary to specify the book, but then you could receive many more options, in different books, about some specific topic.
Now that we know that our graph is the one we want, we can ask YAGS a lot of things about it:
gap> Order(g); Size(g); Diameter(g); Girth(g); 5 6 2 3 gap> NumberOfCliques(g); CliqueNumber(g); 4 3 gap> Adjacencies(g);Adjacency(g,4);Adjacency(g,3); [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] [ 1, 3, 5 ] [ 2, 4 ] gap> VertexDegrees(g);VertexDegree(g,4);VertexDegree(g,3); [ 3, 2, 2, 3, 2 ] 3 2 gap> IsDiamondFree(g);IsCompleteGraph(g);IsLoopless(g); true false true gap> Cliques(g);CompletesOfGivenOrder(g,3); [ [ 1, 4, 5 ], [ 1, 2 ], [ 2, 3 ], [ 3, 4 ] ] [ [ 1, 4, 5 ] ] gap> CompletesOfGivenOrder(g,2); [ [ 1, 2 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ] ]
Note that in YAGS a clique is always maximal. This is just a small sample. The full alphabetic list of YAGS operations can be found in Appendix B, and grouped by topic in Appendix A. There is also a one-page pdf file, cheatsheet-yags.pdf, which contains a very useful synopsis of many of the most common YAGS operations. See the next section (2.4) for details.
What about modifying our graphs? Well, all graphs in YAGS are always immutable, which means that, once created, we can never modify a graph. But we can create new graphs which are variations of existing ones:
gap> g; Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] ) gap> h:=AddEdges(g,[[1,3],[2,4]]);; gap> g; Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] ) gap> h; Graph( Category := SimpleGraphs, Order := 5, Size := 8, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3, 5 ], [ 1, 4 ] ] )
Note that the graph g remains the same, but the graph h has two additional edges. This is done in this way, because in YAGS everything that is computed about a graph is stored within the graph, so that we never need to compute something twice. This saves time when computing attributes of graphs requiring CPU-intensive algorithms (like computing cliques and clique graphs), but at the expense of having to make a copy of the graph when we just want a small variation of it.
There are a lot of predefined graphs (the full list can be consulted in Appendix A.4):
gap> PathGraph(5);CycleGraph(6);CompleteGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4 ] ] ) Graph( Category := SimpleGraphs, Order := 6, Size := 6, Adjacencies := [ [ 2, 6 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4, 6 ], [ 1, 5 ] ] ) Graph( Category := SimpleGraphs, Order := 5, Size := 10, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4, 5 ], [ 1, 2, 4, 5 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 4 ] ] ) gap> CompleteBipartiteGraph(3,3);TreeGraph([2,2,2]); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 4, 5, 6 ], [ 4, 5, 6 ], [ 4, 5, 6 ], [ 1, 2, 3 ], [ 1, 2, 3 ], [ 1, 2, 3 ] ] ) Graph( Category := SimpleGraphs, Order := 15, Size := 14, Adjacencies := [ [ 2, 3 ], [ 1, 4, 5 ], [ 1, 6, 7 ], [ 2, 8, 9 ], [ 2, 10, 11 ], [ 3, 12, 13 ], [ 3, 14, 15 ], [ 4 ], [ 4 ], [ 5 ], [ 5 ], [ 6 ], [ 6 ], [ 7 ], [ 7 ] ] ) gap> Octahedron;ParapluieGraph; Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 3, 4, 5, 6 ], [ 3, 4, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ] ] ) Graph( Category := SimpleGraphs, Order := 7, Size := 9, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4, 5, 6, 7 ], [ 3, 5 ], [ 3, 4, 6 ], [ 3, 5, 7 ], [ 3, 6 ] ] )
We have found that GraphByWalks (B.7-11) is one of the most useful and versatile ways of specifying graphs:
gap> p5:=PathGraph(5);;c6:=CycleGraph(6);;w4:=WheelGraph(4);; gap> IsIsomorphicGraph(p5,GraphByWalks([1..5])); true gap> IsIsomorphicGraph(c6,GraphByWalks([1,2,3,4,5,6,1])); true gap> IsIsomorphicGraph(c6,GraphByWalks([1..6],[6,1])); true gap> IsIsomorphicGraph(w4,GraphByWalks([1,[2,3,4,5,2]])); true gap> sd:=GraphByWalks([1,[2,3,4,5],6],[5,[6,7,8,1],2]);; gap> IsIsomorphicGraph(SnubDisphenoid,sd); true
YAGS knows about random graphs, so you can take some random graphs and study their parameters. Furthermore, GraphAttributeStatistics (B.7-4) can collect statistics on 100 random graphs at a time returning the collected results of the specified graph parameter on these graphs. The following experiments show, for instance that the values of the minimum degree parameter are much more spread than those of the clique number or those of the diameter.
gap> g:=RandomGraph(30,1/2);; gap> MinDegree(g); CliqueNumber(g); Diameter(g); 9 6 2 gap> GraphAttributeStatistics(30,1/2,MinDegree); [ [ 5, 1 ], [ 6, 2 ], [ 7, 6 ], [ 8, 22 ], [ 9, 30 ], [ 10, 30 ], [ 11, 5 ], [ 12, 4 ] ] gap> GraphAttributeStatistics(30,1/2,CliqueNumber); [ [ 5, 2 ], [ 6, 70 ], [ 7, 24 ], [ 8, 4 ] ] gap> GraphAttributeStatistics(30,1/2,Diameter); [ [ 2, 91 ], [ 3, 9 ] ]
Finally, it is worth mentioning that algorithms the may take too much time to finish report their progress using the InfoLevel mechanism: Enabling and disabling progress reporting is done by changing the InfoLevel of YAGSInfo.InfoClass to the appropriate level. The default InfoLevel is 0. Some of YAGS algorithms report at InfoLevel 1, and others at InfoLevel 3.
gap> SetInfoLevel(YAGSInfo.InfoClass,3); gap> FullMonoMorphisms(PathGraph(3),CycleGraph(3)); #I [ ] #I [ 1 ] #I [ 1, 2 ] #I [ 1, 3 ] #I [ 2 ] #I [ 2, 1 ] #I [ 2, 3 ] #I [ 3 ] #I [ 3, 1 ] #I [ 3, 2 ] [ ] gap> SetInfoLevel(YAGSInfo.InfoClass,0); gap> FullMonoMorphisms(PathGraph(3),CycleGraph(3)); [ ]
This way we can abort the calculation (by typing Ctr-C) in case we see that it will take eons to finish. See YAGSInfo.InfoClass (B.24-3) for details.
There is a very useful two-page pdf cheatsheet with YAGS's most common functions. It can be consulted in your YAGS installation at YAGS-DIR/doc/cheatsheet-yags.pdf or on the web at http://xamanek.izt.uam.mx/yags/cheatsheet-yags.pdf. Also, the pdf version of this manual includes it in the next page and an HTML version can be found here: https://github.com/yags/cheatsheet/blob/master/cheatsheet-yags.org.
generated by GAPDoc2HTML