By default, all graphs in YAGS are simple, i.e. all graphs belong to the SimpleGraphs category. There are 5 graph categories in YAGS, namely: Graphs (B.7-13), UndirectedGraphs (B.21-3), LooplessGraphs (B.12-4), SimpleGraphs (B.19-3) and OrientedGraphs (B.15-5). The inclusion relations among them is as follows:
Graphs
/ \
UndirectedGraphs LooplessGraphs
\ / \
SimpleGraphs OrientedGraphs
The most general of these categories is Graphs: every graph in YAGS belongs to some category and, by inclusion, every graph belongs to the category Graphs. By definition a graph in Graphs may contain loops, arrows and edges (which in YAGS are exactly the same as two opposite arrows); another way to say it, is that a graph is anything that can be represented as a binary matrix (its adjacency matrix). In particular, no multiple/parallel edges/arrows are allowed in a graph in YAGS. Likewise, each of the YAGS's graph categories have their own characteristic properties:
Graphs |
May contain loops, arrows and edges. |
UndirectedGraphs |
Can not contain plain arrows (only edges and loops). |
LooplessGraphs |
Can not contain loops (only arrows and edges). |
SimpleGraphs |
Can not contain loops nor arrows (only edges). |
OrientedGraphs |
Can not contain edges nor loops (only arrows). |
Graph categories simplify things for users: for example in the category SimpleGraphs, a complete graph may be defined as a graph containing "all possible edges" among their vertices, but "all possible edges" in the category Graphs includes the loops, while in the category OrientedGraphs, it can only contain one arrow for each pair of vertices.
The graph category used for constructing graphs forbids you to add a loop accidentally or to forget to include one of the arrows that constitute an edge in a simple graph: Every graph created in YAGS is forced to comply with its graph category's characteristic properties.
YAGS supports several mechanisms to carefully control the graphs categories used to construct your graphs. These are explained in the following sections.
The DefaultGraphCategory controls (in the absence of other indications) the graph category to which the new graphs belong. It can not be changed directly as if it were a normal variable, instead, it can be changed by the method SetDefaultGraphCategory (B.19-2)
gap> DefaultGraphCategory; <Category "SimpleGraphs"> gap> SetDefaultGraphCategory(OrientedGraphs); gap> DefaultGraphCategory; <Category "OrientedGraphs"> gap> DefaultGraphCategory:=LooplessGraphs; Error, Variable: 'DefaultGraphCategory' is read only
The effect on the constructed graphs is very noticeable: look at the adjacencies of these graphs:
gap> SetDefaultGraphCategory(Graphs);CompleteGraph(4); Graph( Category := Graphs, Order := 4, Size := 16, Adjacencies := [ [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ] ] ) gap> SetDefaultGraphCategory(LooplessGraphs);CompleteGraph(4); Graph( Category := LooplessGraphs, Order := 4, Size := 12, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) gap> SetDefaultGraphCategory(UndirectedGraphs);CompleteGraph(4); Graph( Category := UndirectedGraphs, Order := 4, Size := 10, Adjacencies := [ [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ] ] ) gap> SetDefaultGraphCategory(OrientedGraphs);CompleteGraph(4); Graph( Category := OrientedGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 3, 4 ], [ 4 ], [ ] ] ) gap> SetDefaultGraphCategory(SimpleGraphs);CompleteGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] )
When constructing a graph, YAGS always forces the new graphs to comply with its category, hence, in the case of OrientedGraphs in the previous example, it has to remove one of the arrows conforming the edge for each pair of vertices of the graph. Sometimes it may not be evident which arrow will YAGS choose to remove, but in general, YAGS tries to make sense:
gap> SetDefaultGraphCategory(OrientedGraphs); gap> CycleGraph(4); PathGraph(4); GraphByWalks([1..5],[3,5,1]); Graph( Category := OrientedGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2 ], [ 3 ], [ 4 ], [ 1 ] ] ) Graph( Category := OrientedGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 3 ], [ 4 ], [ ] ] ) Graph( Category := OrientedGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2 ], [ 3 ], [ 4, 5 ], [ 5 ], [ 1 ] ] ) gap> SetDefaultGraphCategory(SimpleGraphs); gap> CycleGraph(4); PathGraph(4); GraphByWalks([1..5],[3,5,1]); Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] ) Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4, 5 ], [ 3, 5 ], [ 1, 3, 4 ] ] )
Therefore, if you always work with SimpleGraphs, YAGS defaults are perfect for you. If, in the other hand you always work with OrientedGraphs (also known as digraphs), you probably would want to start all your sessions by changing the default graph category to that... or even better, you may want to create a startup file that does that automatically every time you start a YAGS session.
On the other hand, your work may involve graphs from more than one graph category. In such a case, it is advisable to continue reading all of this chapter.
The default graph category is only part of the story. When constructing new graphs from existing ones, it may be natural to construct the new graph in the least common category that contains the original graphs, regardless of the DefaultGraphCategory.
For instance, if we have graphs g and h that belong to the categories of SimpleGraphs and OrientedGraphs (respectively), then a new graph which is the BoxTimesProduct (also known as the strong product) of them, should belong to the least common category of both, namely to the LooplessGraphs category (see the diagram at the beginning of the chapter). This is what YAGS does:
gap> SetDefaultGraphCategory(SimpleGraphs); gap> g:=PathGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] ) gap> SetDefaultGraphCategory(OrientedGraphs); gap> h:=PathGraph(4); Graph( Category := OrientedGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 3 ], [ 4 ], [ ] ] ) gap> SetDefaultGraphCategory(UndirectedGraphs); gap> s:=BoxTimesProduct(g,h); Graph( Category := LooplessGraphs, Order := 16, Size := 54, Adjacencies := [ [ 2, 5, 6 ], [ 3, 6, 7 ], [ 4, 7, 8 ], [ 8 ], [ 1, 2, 6, 9, 10 ], [ 2, 3, 7, 10, 11 ], [ 3, 4, 8, 11, 12 ], [ 4, 12 ], [ 5, 6, 10, 13, 14 ], [ 6, 7, 11, 14, 15 ], [ 7, 8, 12, 15, 16 ], [ 8, 16 ], [ 9, 10, 14 ], [ 10, 11, 15 ], [ 11, 12, 16 ], [ 12 ] ] ) gap> s in UndirectedGraphs; s in LooplessGraphs; false true gap> DefaultGraphCategory; <Category "UndirectedGraphs">
Exactly how does YAGS decide this? Well, with very few and evident exceptions (such as Orientations (B.15-4)), YAGS's functions that construct graphs, always calls internally the function TargetGraphCategory (B.20-1), and passes to it those of the original parameters which are graphs.
TargetGraphCategory returns the graph category indicated by GAP's options stack if any (see the next section), else it returns the least common category containing all of its parameters if any, or else (if it is called without parameters), TargetGraphCategory returns the DefaultGraphCategory.
GAP provides a wonderful feature named options stack. Consult GAP's documentation on the topic for a full explanation. For YAGS purposes, the short story is that you may specify the desired graph category directly in the same command used to construct the graph without the need to change the default graph category as in the following example:
gap> SetDefaultGraphCategory(Graphs); gap> DefaultGraphCategory; <Category "Graphs"> gap> g1:=CompleteGraph(4); Graph( Category := Graphs, Order := 4, Size := 16, Adjacencies := [ [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ] ] ) gap> DefaultGraphCategory; <Category "Graphs"> gap> g2:=CompleteGraph(4:GraphCategory:=SimpleGraphs); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) gap> DefaultGraphCategory; <Category "Graphs"> gap> g3:=CompleteGraph(4:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 3, 4 ], [ 4 ], [ ] ] ) gap> DefaultGraphCategory; <Category "Graphs"> gap> h:=DisjointUnion(g2,g3); Graph( Category := LooplessGraphs, Order := 8, Size := 18, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ], [ 6, 7, 8 ], [ 7, 8 ], [ 8 ], [ ] ] ) gap> DefaultGraphCategory; <Category "Graphs"> gap> h2:=DisjointUnion(g2,g3:GraphCategory:=UndirectedGraphs); Graph( Category := UndirectedGraphs, Order := 8, Size := 12, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ], [ 6, 7, 8 ], [ 5, 7, 8 ], [ 5, 6, 8 ], [ 5, 6, 7 ] ] ) gap> DefaultGraphCategory; <Category "Graphs">
This method of specifying the desired category is useful to copy a graph from one category to another using CopyGraph (B.3-20):
gap> SetDefaultGraphCategory(SimpleGraphs); gap> g:=PathGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] ) gap> h:=CopyGraph(g:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 3 ], [ 4 ], [ ] ] )
generated by GAPDoc2HTML