This chapter contains a list of most YAGS's functions, with full definitions, in alphabetical order; but the predefined types of morphisms are best described in their own Section 5.2.
‣ AddEdges( G, E ) | ( operation ) |
Returns a new graph created from graph G by adding the edges in list E.
gap> g:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> AddEdges(g,[[1,3]]); Graph( Category := SimpleGraphs, Order := 4, Size := 5, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3 ] ] ) gap> AddEdges(g,[[1,3],[2,4]]); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] )
‣ AddVerticesByAdjacencies( G, NewAdjList ) | ( operation ) |
Returns a new graph created from graph G by adding as many new vertices as Length(NewAdjList). Each entry in NewAdjList is also a list: the list of neighbors of the corresponding new vertex.
gap> g:=PathGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4 ] ] ) gap> AddVerticesByAdjacencies(g,[[1,2],[4,5]]); Graph( Category := SimpleGraphs, Order := 7, Size := 8, Adjacencies := [ [ 2, 6 ], [ 1, 3, 6 ], [ 2, 4 ], [ 3, 5, 7 ], [ 4, 7 ], [ 1, 2 ], [ 4, 5 ] ] ) gap> AddVerticesByAdjacencies(g,[[1,2,7],[4,5]]); Graph( Category := SimpleGraphs, Order := 7, Size := 9, Adjacencies := [ [ 2, 6 ], [ 1, 3, 6 ], [ 2, 4 ], [ 3, 5, 7 ], [ 4, 7 ], [ 1, 2, 7 ], [ 4, 5, 6 ] ] )
‣ Adjacencies( G ) | ( operation ) |
Returns the adjacency lists of graph G.
gap> g:=PathGraph(3); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) gap> Adjacencies(g); [ [ 2 ], [ 1, 3 ], [ 2 ] ]
‣ Adjacency( G, x ) | ( operation ) |
Returns the adjacency list of vertex x in G.
gap> g:=PathGraph(3); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) gap> Adjacency(g,1); [ 2 ] gap> Adjacency(g,2); [ 1, 3 ]
‣ AdjMatrix( G ) | ( attribute ) |
Returns the adjacency matrix of the graph G.
gap> AdjMatrix(CycleGraph(4)); [ [ false, true, false, true ], [ true, false, true, false ], [ false, true, false, true ], [ true, false, true, false ] ]
‣ AGraph | ( global variable ) |
A 4-cycle with two pendant vertices on consecutive vertices of the cycle.
gap> AGraph; Graph( Category := SimpleGraphs, Order := 6, Size := 6, Adjacencies := [ [ 2 ], [ 1, 3, 5 ], [ 2, 4 ], [ 3, 5 ], [ 2, 4, 6 ], [ 5 ] ] )
‣ AntennaGraph | ( global variable ) |
A HouseGraph with a pendant vertex (antenna) on the roof.
gap> AntennaGraph; Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 1, 4, 6 ], [ 5 ] ] )
‣ AutomorphismGroup( G ) | ( attribute ) |
‣ AutGroupGraph( G ) | ( operation ) |
Returns the group of automorphisms of the graph G. Both forms are synonyms.
gap> AutomorphismGroup(Icosahedron); Group([ (1,3,10,12,8,5)(2,11,9,7,6,4), (1,4,7,8,6)(2,3,11,12,9) ]) gap> AutGroupGraph(Icosahedron); Group([ (1,3,10,12,8,5)(2,11,9,7,6,4), (1,4,7,8,6)(2,3,11,12,9) ])
‣ Backtrack( L, Opts, Chk, Done, Extra ) | ( operation ) |
Generic, user-customizable backtracking algorithm.
The non-expert programmer is advised to read Chapter 6 first.
A backtracking algorithm explores a decision tree in search for solutions to a combinatorial problem. The combinatorial problem and the search strategy are specified by the parameters:
L is just a list that Backtrack uses to keep track of solutions and partial solutions. It is usually set to the empty list as a starting point. After a solution is found, it is returned and stored in L. This value of L is then used as a starting point to search for the next solution in case Backtrack is called again. Partial solutions are also stored in L during the execution of Backtrack.
Extra may be any object, list, record, etc. Backtrack only uses it to pass this data to the user-defined functions Opts, Chk and Done, therefore offering you a way to share data between your functions.
Opts:=function(L,extra) must return the list of continuation options (children) one has after some partial solution (node) L has been reached within the decision tree (Opts may use the extra data Extra as needed). Each of the values in the list returned by Opts(L,extra) will be tried as possible continuations of the partial solution L. If Opts(L,extra) always returns the same list, you can put that list in place of the parameter Opts.
Chk:=function(L,extra) must evaluate the partial solution L possibly using the extra data Extra and must return false when it knows that L can not be extended to a solution of the problem. Otherwise it returns true. Chk may assume that L{[1..Length(L)-1]} already passed the test.
Done:=function(L,extra) returns true if L is already a complete solution and false otherwise. In many combinatorial problems, any partial solution of certain length n is also a solution (and vice versa), so if this is your case, you can put that length in place of the parameter Done.
The following example uses Backtrack in its simplest form to compute derangements (permutations of a set, where none of the elements appears in its original position).
gap> N:=4;;L:=[];;extra:=[];;opts:=[1..N];;done:=N;; gap> chk:=function(L,extra) local i; i:=Length(L); > return not L[i] in L{[1..i-1]} and L[i]<> i; end;; gap> Backtrack(L,opts,chk,done,extra); [ 2, 1, 4, 3 ] gap> Backtrack(L,opts,chk,done,extra); [ 2, 3, 4, 1 ] gap> Backtrack(L,opts,chk,done,extra); [ 2, 4, 1, 3 ] gap> Backtrack(L,opts,chk,done,extra); [ 3, 1, 4, 2 ] gap> Backtrack(L,opts,chk,done,extra); [ 3, 4, 1, 2 ] gap> Backtrack(L,opts,chk,done,extra); [ 3, 4, 2, 1 ] gap> Backtrack(L,opts,chk,done,extra); [ 4, 1, 2, 3 ] gap> Backtrack(L,opts,chk,done,extra); [ 4, 3, 1, 2 ] gap> Backtrack(L,opts,chk,done,extra); [ 4, 3, 2, 1 ] gap> Backtrack(L,opts,chk,done,extra); fail
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
Extensive information on Backtrack and BacktrackBag can be found in Chapter 6.
‣ BacktrackBag( Opts, Chk, Done, Extra ) | ( operation ) |
Returns the list of all solutions that would be returned one at a time by Backtrack.
The following example computes all derangements of order 4.
gap> N:=4;; gap> chk:=function(L,extra) local i; i:=Length(L); > return not L[i] in L{[1..i-1]} and L[i]<> i; end;; gap> BacktrackBag([1..N],chk,N,[]); [ [ 2, 1, 4, 3 ], [ 2, 3, 4, 1 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ], [ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ], [ 4, 1, 2, 3 ], [ 4, 3, 1, 2 ], [ 4, 3, 2, 1 ] ]
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
Extensive information on Backtrack and BacktrackBag can be found in Chapter 6.
‣ Basement( G, KnG, x ) | ( operation ) |
‣ Basement( G, KnG, V ) | ( operation ) |
Given a graph G, some iterated clique graph KnG of G and a vertex x of KnG, the operation returns the basement of x with respect to G [23]. Loosely speaking, the basement of x is the set of vertices of G that constitutes the iterated clique x.
gap> g:=Icosahedron;;Cliques(g); [ [ 1, 2, 3 ], [ 1, 2, 6 ], [ 1, 3, 4 ], [ 1, 4, 5 ], [ 1, 5, 6 ], [ 4, 5, 7 ], [ 4, 7, 11 ], [ 5, 7, 8 ], [ 7, 8, 12 ], [ 7, 11, 12 ], [ 5, 6, 8 ], [ 6, 8, 9 ], [ 8, 9, 12 ], [ 2, 6, 9 ], [ 2, 9, 10 ], [ 9, 10, 12 ], [ 2, 3, 10 ], [ 3, 10, 11 ], [ 10, 11, 12 ], [ 3, 4, 11 ] ] gap> kg:=CliqueGraph(g);; k2g:=CliqueGraph(kg);; gap> Basement(g,k2g,1);Basement(g,k2g,2); [ 1, 2, 3, 4, 5, 6 ] [ 1, 2, 3, 4, 6, 10 ]
Formally, taking m=n-1, the basement is defined as follows:
Basement(G,G,x):=x; |
Basement(G,KG,x):=VertexNames(KG)[x]; |
Basement(G,KnG,x):= Union(List(VertexNames(KnG)[x]), z->Basement(G,KmG,z)); |
In its second form, V is a set of vertices of KnG, in that case, the basement is simply the union of the basements of the vertices in V.
gap> Basement(g,k2g,[1,2]); [ 1, 2, 3, 4, 5, 6, 10 ]
Basements have been used to study distances and diameters of clique graphs in [3] and [23].
‣ BoundaryVertices( G ) | ( attribute ) |
When G is (an underlying graph of a Whitney triangulation of) a compact surface, it returns the list of vertices in the boundary (of the triangulation) of the surface. That is, the list of vertices of G whose link is isomorphic to a path of length at least 2. It returns fail if G is not a compact surface.
gap> BoundaryVertices(WheelGraph(4,2)); [ 6, 7, 8, 9 ] gap> BoundaryVertices(Octahedron); [ ]
‣ BoxProduct( G, H ) | ( operation ) |
Returns the box product, G□H, of two graphs G and H (also known as the Cartesian product).
The box product is calculated as follows:
For each pair of vertices x ∈ G, y ∈ H we create a vertex (x,y). Given two such vertices (x,y) and (x',y') they are adjacent iff x = x and y ∼ y' or x ∼ x' and y = y'.
gap> g:=PathGraph(3);h:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> gh:=BoxProduct(g,h); Graph( Category := SimpleGraphs, Order := 12, Size := 20, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3, 6 ], [ 2, 4, 7 ], [ 1, 3, 8 ], [ 1, 6, 8, 9 ], [ 2, 5, 7, 10 ], [ 3, 6, 8, 11 ], [ 4, 5, 7, 12 ], [ 5, 10, 12 ], [ 6, 9, 11 ], [ 7, 10, 12 ], [ 8, 9, 11 ] ] ) gap> VertexNames(gh); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ] ]
‣ BoxTimesProduct( G, H ) | ( operation ) |
Returns the boxtimes product, G ⊠ H, of two graphs G and H (also known as the strong product).
The boxtimes product is calculated as follows:
For each pair of vertices x ∈ G, y ∈ H we create a vertex (x,y). Given two such vertices (x,y) and (x',y') such that (x,y) ≠ (x',y') they are adjacent iff x ≃ x' and y ≃ y'.
gap> g:=PathGraph(3);h:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> gh:=BoxTimesProduct(g,h); Graph( Category := SimpleGraphs, Order := 12, Size := 36, Adjacencies := [ [ 2, 4, 5, 6, 8 ], [ 1, 3, 5, 6, 7 ], [ 2, 4, 6, 7, 8 ], [ 1, 3, 5, 7, 8 ], [ 1, 2, 4, 6, 8, 9, 10, 12 ], [ 1, 2, 3, 5, 7, 9, 10, 11 ], [ 2, 3, 4, 6, 8, 10, 11, 12 ], [ 1, 3, 4, 5, 7, 9, 11, 12 ], [ 5, 6, 8, 10, 12 ], [ 5, 6, 7, 9, 11 ], [ 6, 7, 8, 10, 12 ], [ 5, 7, 8, 9, 11 ] ] ) gap> VertexNames(gh); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ] ]
‣ BullGraph | ( global variable ) |
A triangle with two pendant vertices (horns).
gap> BullGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2 ], [ 1, 3, 4 ], [ 2, 4 ], [ 2, 3, 5 ], [ 4 ] ] )
‣ CayleyGraph( Grp, Elms ) | ( operation ) |
‣ CayleyGraph( Grp ) | ( operation ) |
Returns the graph G whose vertices are the elements of the group Grp such that x is adjacent to y iff x*g=y for some g in the list Elms. If Elms is not provided, then the generators of G are used instead.
gap> grp:=Group((1,2,3),(1,2)); Group([ (1,2,3), (1,2) ]) gap> CayleyGraph(grp); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 3, 4, 5 ], [ 3, 5, 6 ], [ 1, 2, 6 ], [ 1, 5, 6 ], [ 1, 2, 4 ], [ 2, 3, 4 ] ] ) gap> CayleyGraph(grp,[(1,2),(2,3)]); Graph( Category := SimpleGraphs, Order := 6, Size := 6, Adjacencies := [ [ 2, 3 ], [ 1, 5 ], [ 1, 4 ], [ 3, 6 ], [ 2, 6 ], [ 4, 5 ] ] ) gap> VertexNames(last); [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
‣ ChairGraph | ( global variable ) |
The tree with degree sequence 3,2,1,1,1.
gap> ChairGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3, 4 ], [ 2 ], [ 2, 5 ], [ 4 ] ] )
‣ Circulant( n, Jumps ) | ( operation ) |
Returns the graph G whose vertices are [1..n] such that x is adjacent to y iff x+z=y mod n for some z in the list Jumps.
gap> Circulant(6,[1,2]); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 2, 3, 5, 6 ], [ 1, 3, 4, 6 ], [ 1, 2, 4, 5 ], [ 2, 3, 5, 6 ], [ 1, 3, 4, 6 ], [ 1, 2, 4, 5 ] ] )
‣ ClawGraph | ( global variable ) |
The graph on 4 vertices, 3 edges, and maximum degree 3.
gap> ClawGraph; Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2, 3, 4 ], [ 1 ], [ 1 ], [ 1 ] ] )
‣ CliqueGraph( G ) | ( attribute ) |
‣ CliqueGraph( G, maxNumCli ) | ( operation ) |
Returns the intersection graph, K(G), of all the (maximal) cliques of G.
The additional parameter maxNumCli aborts the computation when maxNumCli cliques are found, even if they are all the cliques of G. If the bound maxNumCli is reached, fail is returned. However, the clique graph of G is returned if it has been computed earlier, regardless of the value of maxNumCli.
gap> CliqueGraph(Cube); Graph( Category := SimpleGraphs, Order := 12, Size := 24, Adjacencies := [ [ 2, 3, 5, 7 ], [ 1, 3, 4, 11 ], [ 1, 2, 8, 10 ], [ 2, 5, 6, 11 ], [ 1, 4, 6, 7 ], [ 4, 5, 9, 12 ], [ 1, 5, 8, 9 ], [ 3, 7, 9, 10 ], [ 6, 7, 8, 12 ], [ 3, 8, 11, 12 ], [ 2, 4, 10, 12 ], [ 6, 9, 10, 11 ] ] ) gap> CliqueGraph(Octahedron,8); fail gap> CliqueGraph(Octahedron,9); Graph( Category := SimpleGraphs, Order := 8, Size := 24, Adjacencies := [ [ 2, 3, 4, 5, 6, 7 ], [ 1, 3, 4, 5, 6, 8 ], [ 1, 2, 4, 5, 7, 8 ], [ 1, 2, 3, 6, 7, 8 ], [ 1, 2, 3, 6, 7, 8 ], [ 1, 2, 4, 5, 7, 8 ], [ 1, 3, 4, 5, 6, 8 ], [ 2, 3, 4, 5, 6, 7 ] ] ) gap> CliqueGraph(Octahedron,8); Graph( Category := SimpleGraphs, Order := 8, Size := 24, Adjacencies := [ [ 2, 3, 4, 5, 6, 7 ], [ 1, 3, 4, 5, 6, 8 ], [ 1, 2, 4, 5, 7, 8 ], [ 1, 2, 3, 6, 7, 8 ], [ 1, 2, 3, 6, 7, 8 ], [ 1, 2, 4, 5, 7, 8 ], [ 1, 3, 4, 5, 6, 8 ], [ 2, 3, 4, 5, 6, 7 ] ] )
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ CliqueNumber( G ) | ( attribute ) |
Returns the order, ω( G ), of a maximum clique of G.
gap> g:=SunGraph(4); Graph( Category := SimpleGraphs, Order := 8, Size := 14, Adjacencies := [ [ 2, 8 ], [ 1, 3, 4, 6, 8 ], [ 2, 4 ], [ 2, 3, 5, 6, 8 ], [ 4, 6 ], [ 2, 4, 5, 7, 8 ], [ 6, 8 ], [ 1, 2, 4, 6, 7 ] ] ) gap> Cliques(g); [ [ 2, 4, 6, 8 ], [ 2, 3, 4 ], [ 1, 2, 8 ], [ 4, 5, 6 ], [ 6, 7, 8 ] ] gap> CliqueNumber(g); 4
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ Cliques( G ) | ( attribute ) |
‣ Cliques( G, maxNumCli ) | ( operation ) |
Returns the set of all (maximal) cliques of a graph G. A clique is a maximal complete subgraph. Here, we use the Bron-Kerbosch algorithm [4].
In the second form, It stops computing cliques after maxNumCli of them have been found.
gap> Cliques(Octahedron); [ [ 1, 3, 5 ], [ 1, 3, 6 ], [ 1, 4, 5 ], [ 1, 4, 6 ], [ 2, 3, 5 ], [ 2, 3, 6 ], [ 2, 4, 5 ], [ 2, 4, 6 ] ] gap> Cliques(Octahedron,4); [ [ 1, 3, 5 ], [ 1, 3, 6 ], [ 1, 4, 5 ], [ 1, 4, 6 ] ]
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ ClockworkGraph( NNFSList ) | ( operation ) |
‣ ClockworkGraph( NNFSList, rank ) | ( operation ) |
‣ ClockworkGraph( NNFSList, Perm ) | ( operation ) |
‣ ClockworkGraph( NNFSList, rank, Perm ) | ( operation ) |
Returns the clockwork graph [13][15] specified by its parameters.
Clockwork graphs have been very useful in constructing examples and counter-examples in clique graph theory. In particular, they have been used to construct examples of clique-periodic graphs of all possible periods [6], clique-divergent graphs of linear and polynomial growth rate [16][13], clique-convergent graphs whose period is not invariant under removal of dominated vertices [8], clique-convergent graphs which become clique-divergent by just gluing a 4-cycle to a vertex [7], rank-divergent graphs [17], etc.
A clockwork graph consists of two parts: the crown and the core, both of them are cyclically segmented. When not specified, the rank is assumed to be 2 and the return permutation, Perm, is assumed to be trivial, let us assume this is our case. Consider the following examples:
gap> ClockworkGraph([[0],[0],[0],[0]]); Graph( Category := SimpleGraphs, Order := 12, Size := 28, Adjacencies := [ [ 2, 3, 4, 10, 12 ], [ 1, 3, 5, 11, 12 ], [ 1, 2, 4, 5 ], [ 1, 3, 5, 6, 7 ], [ 2, 3, 4, 6, 8 ], [ 4, 5, 7, 8 ], [ 4, 6, 8, 9, 10 ], [ 5, 6, 7, 9, 11 ], [ 7, 8, 10, 11 ], [ 1, 7, 9, 11, 12 ], [ 2, 8, 9, 10, 12 ], [ 1, 2, 10, 11 ] ] ) gap> ClockworkGraph([[1],[1],[1],[1]]); Graph( Category := SimpleGraphs, Order := 12, Size := 32, Adjacencies := [ [ 2, 3, 4, 10, 12 ], [ 1, 3, 5, 11, 12 ], [ 1, 2, 4, 5, 6, 12 ], [ 1, 3, 5, 6, 7 ], [ 2, 3, 4, 6, 8 ], [ 3, 4, 5, 7, 8, 9 ], [ 4, 6, 8, 9, 10 ], [ 5, 6, 7, 9, 11 ], [ 6, 7, 8, 10, 11, 12 ], [ 1, 7, 9, 11, 12 ], [ 2, 8, 9, 10, 12 ], [ 1, 2, 3, 9, 10, 11 ] ] )
In both cases, the crown is the subgraph induced by the vertices {1,2,4,5,7,8,10,11} and the core is induced by {3,6,9,12}. Also in both cases the cyclic segmentations (partitions) of the crown and the core are {{1,2},{4,5},{7,8},{10,11}} and {{3},{6},{9},{12}} respectively. The number of segments s is specified by s:=Length(NNFSList) which is 4 in these cases. The crown is isomorphic to BoxProduct(CycleGraph(s),Completegraph(rank)): All the crown segments are complete subgraphs and the vertices of cyclically consecutive segments are joined by a perfect matching. The adjacencies between crown and core vertices are simple to describe: Cyclically intercalate crown and core segments, making each core vertex adjacent to the vertices in the previous and the following crown segments. Hence in our examples vertex 3 is adjacent to vertices 1 and 2 (previous segment), but also 4 and 5 (following segment). Note that since the segmentations and intercalations are cyclic, we have that vertex 12 is adjacent to 10 and 11, but also to 1 and 2. Finally the edges between core vertices are as follows: first each core segment is a complete subgraph; the vertices within each core segment are linearly ordered and for vertex number t in segment number s there is a non-negative integer NNFSList[s][t] which specifies, the Number of Neighbors in the Following core Segment for that vertex (hence the name NNFSList) (Since the vertices in core segments are linearly ordered, it is enough to specify the number of neighbors in the following segment and the first ones of those are selected as the neighbors). Hence in our two examples above, each core segment consists of exactly one vertex. In the first example each core segment is adjacent to no vertex in the following segment (e.g. 3 is not adjacent to 6) but in the second one, each core segment is adjacent to exactly one vertex in the following segment (e.g. 3 is adjacent to 6).
A more complicated example should be now mostly self-explanatory:
gap> ClockworkGraph([[2],[0,1,3],[0,1,1],[1]]); Graph( Category := SimpleGraphs, Order := 16, Size := 59, Adjacencies := [ [ 2, 3, 4, 14, 16 ], [ 1, 3, 5, 15, 16 ], [ 1, 2, 4, 5, 6, 7, 16 ], [ 1, 3, 5, 6, 7, 8, 9 ], [ 2, 3, 4, 6, 7, 8, 10 ], [ 3, 4, 5, 7, 8, 9, 10 ], [ 3, 4, 5, 6, 8, 9, 10, 11 ], [ 4, 5, 6, 7, 9, 10, 11, 12, 13 ], [ 4, 6, 7, 8, 10, 11, 12, 13, 14 ], [ 5, 6, 7, 8, 9, 11, 12, 13, 15 ], [ 7, 8, 9, 10, 12, 13, 14, 15 ], [ 8, 9, 10, 11, 13, 14, 15, 16 ], [ 8, 9, 10, 11, 12, 14, 15, 16 ], [ 1, 9, 11, 12, 13, 15, 16 ], [ 2, 10, 11, 12, 13, 14, 16 ], [ 1, 2, 3, 12, 13, 14, 15 ] ] )
The crown and core segmentations are {{1,2},{4,5},{9,10},{14,15}} and {{3},{6,7,8},{11,12,13},{16}} respectively and the adjacencies specified by the NNFSList are: 3 is adjacent to 6 and 7; 6 is adjacent to none (in the following core segment); 7 is adjacent to 11; 8 to 11, 12 and 13; 11 to none; 12 to 16; 13 to 16 and 16 to 3.
When rank and/or Perm are specified, they have the following effects: rank (which must be at least 2) is the number of vertices in each crown segment, and Perm (which must belong to SymmetricGroup( rank )) specifies the perfect matching joining the vertices in the last crown segment with the vertices in the first crown segment: The k-th vertex in the last crown segment k∈ {1,2,...,rank} is made adjacent to the Perm(k)-th vertex of the first crown segment.
A number of requisites are put forward in the literature for a graph to be a clockwork graph but this operation does not enforce those conditions, on the contrary, it tries to make sense of the data provided as much as possible. For instance NNFSList:=[[2],[2],[2],[2]] would be inconsistent since there are not enough vertices in each core segment to provide for the required 2 neighbors. However, the result is just the same as with NNFSList:=[[1],[1],[1],[1]]. The requisites that are mandatory are exactly these: the rank must be at least 2, Perm must belong to SymmetricGroup(rank), NNFSList must be a list of lists of non-negative integers, and the number of segments (= Length(NNFSList)) must be at least 3. A call to ClockworkGraph which fails to conform to these requisites will produce an error.
‣ ComplementGraph( G ) | ( attribute ) |
Returns the new graph H such that V( H )=V( G ) and xy∈ E( H ) <=> xy not\in E( G ).
gap> g:=ClawGraph; Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2, 3, 4 ], [ 1 ], [ 1 ], [ 1 ] ] ) gap> ComplementGraph(g); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ ], [ 3, 4 ], [ 2, 4 ], [ 2, 3 ] ] )
‣ CompleteBipartiteGraph( n, m ) | ( function ) |
Returns the complete bipartite whose parts have order n and m respectively. This is the joint (Zykov sum) of two discrete graphs of order n and m.
gap> CompleteBipartiteGraph(2,3); Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 3, 4, 5 ], [ 3, 4, 5 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ] ] )
‣ CompleteGraph( n ) | ( function ) |
Returns the complete graph of order n. A complete graph is a graph where all vertices are connected to each other.
gap> CompleteGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] )
‣ CompletelyParedGraph( G ) | ( operation ) |
Returns the completely pared graph of G, which is obtained by repeatedly applying ParedGraph until no more dominated vertices remain.
gap> g:=PathGraph(6); Graph( Category := SimpleGraphs, Order := 6, Size := 5, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4, 6 ], [ 5 ] ] ) gap> CompletelyParedGraph(g); Graph( Category := SimpleGraphs, Order := 1, Size := 0, Adjacencies := [ [ ] ] )
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ CompleteMultipartiteGraph( n1, n2[, n3, ...] ) | ( function ) |
Returns the complete multipartite graph where the orders of the parts are n1, n2, ... It is also the Zykov sum of discrete graphs of order n1, n2, ...
gap> CompleteMultipartiteGraph(2,2,2); 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 ] ] )
‣ CompletesOfGivenOrder( G, ord ) | ( operation ) |
Returns the list of vertex sets of all complete subgraphs of order ord of G.
gap> g:=SunGraph(4); Graph( Category := SimpleGraphs, Order := 8, Size := 14, Adjacencies := [ [ 2, 8 ], [ 1, 3, 4, 6, 8 ], [ 2, 4 ], [ 2, 3, 5, 6, 8 ], [ 4, 6 ], [ 2, 4, 5, 7, 8 ], [ 6, 8 ], [ 1, 2, 4, 6, 7 ] ] ) gap> CompletesOfGivenOrder(g,3); [ [ 1, 2, 8 ], [ 2, 3, 4 ], [ 2, 4, 6 ], [ 2, 4, 8 ], [ 2, 6, 8 ], [ 4, 5, 6 ], [ 4, 6, 8 ], [ 6, 7, 8 ] ] gap> CompletesOfGivenOrder(g,4); [ [ 2, 4, 6, 8 ] ]
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
‣ Composition( G, H ) | ( operation ) |
Returns the composition G[H] of two graphs G and H.
A composition of graphs is obtained by calculating the GraphSum of G with Order(G) copies of H, G[H] = GraphSum(G, [H, ..., H]).
gap> g:=CycleGraph(4);;h:=DiscreteGraph(2);; gap> Composition(g,h); Graph( Category := SimpleGraphs, Order := 8, Size := 16, Adjacencies := [ [ 3, 4, 7, 8 ], [ 3, 4, 7, 8 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 3, 4, 7, 8 ], [ 3, 4, 7, 8 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ] ] )
‣ Cone( G ) | ( operation ) |
Returns the cone of graph G. The cone of G is the graph obtained from G by adding a new vertex which is adjacent to every vertex of G. The new vertex is the first one in the new graph.
gap> Cone(CycleGraph(4)); Graph( Category := SimpleGraphs, Order := 5, Size := 8, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 5 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 2, 4 ] ] )
‣ ConnectedComponents( G ) | ( attribute ) |
Returns the connected components of G.
Two vertices in a graph are reachable (from each other) if there is a path connecting them. Two vertices are in the same connected component iff they are reachable from each other. This operation thus computes the equivalence partition of the equivalence relation "reachable".
gap> g:=GraphByWalks([3,1,4],[5,2]); Graph( Category := SimpleGraphs, Order := 5, Size := 3, Adjacencies := [ [ 3, 4 ], [ 5 ], [ 1 ], [ 1 ], [ 2 ] ] ) gap> ConnectedComponents(g); [ [ 1, 3, 4 ], [ 2, 5 ] ] gap> g1:=Composition(DiscreteGraph(3),g); Graph( Category := SimpleGraphs, Order := 15, Size := 9, Adjacencies := [ [ 3, 4 ], [ 5 ], [ 1 ], [ 1 ], [ 2 ], [ 8, 9 ], [ 10 ], [ 6 ], [ 6 ], [ 7 ], [ 13, 14 ], [ 15 ], [ 11 ], [ 11 ], [ 12 ] ] ) gap> ConnectedComponents(g1); [ [ 1, 3, 4 ], [ 2, 5 ], [ 6, 8, 9 ], [ 7, 10 ], [ 11, 13, 14 ], [ 12, 15 ] ]
‣ ConnectedGraphsOfGivenOrder( n ) | ( operation ) |
Returns the list of all connected graphs of order n (up to isomorphism). This operation uses Brendan McKay's data published here:
https://cs.anu.edu.au/people/Brendan.McKay/data/graphs.html.
The data are included with the YAGS distribution in its data directory. Hence this operation simply reads the corresponding file in that directory using ImportGraph6( Filename ). Therefore, the integer n must be in the range from 1 up to 9.
gap> ConnectedGraphsOfGivenOrder(3); [ Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 3 ], [ 3 ], [ 1, 2 ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) ] gap> ConnectedGraphsOfGivenOrder(4); [ Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 4 ], [ 4 ], [ 4 ], [ 1, 2, 3 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 3, 4 ], [ 4 ], [ 1 ], [ 1, 2 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 3, 4 ], [ 4 ], [ 1, 4 ], [ 1, 2, 3 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 3, 4 ], [ 3, 4 ], [ 1, 2 ], [ 1, 2 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 5, Adjacencies := [ [ 3, 4 ], [ 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) ] gap> Length(ConnectedGraphsOfGivenOrder(9)); 261080
Data for graphs on 10 vertices is also available, but not included with YAGS, it may not be practical to use that data, but if you would like to try, all you have to do is to copy (and to uncompress) the corresponding file into the directory YAGS-DIR/data/.
gap> ConnectedGraphsOfGivenOrder(10); #W Unreadable File: /opt/gap4r8/pkg/yags/data/graph10c.g6 fail
‣ Coordinates( G ) | ( operation ) |
Gets the coordinates of the vertices of G, which are used to draw G by Draw( G ). If the coordinates have not been previously set, Coordinates returns fail.
gap> g:=CycleGraph(4);; gap> Coordinates(g); fail gap> SetCoordinates(g,[[-10,-10 ],[-10,20],[20,-10 ], [20,20]]); gap> Coordinates(g); [ [ -10, -10 ], [ -10, 20 ], [ 20, -10 ], [ 20, 20 ] ]
‣ CopyGraph( G ) | ( operation ) |
Returns a fresh copy of the graph G. Only the order and adjacency information is copied, all other known attributes of G are not. Mainly used to transform a graph from one category to another. The new graph will be forced to comply with the TargetGraphCategory.
gap> g:=CompleteGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) gap> g1:=CopyGraph(g:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 3, 4 ], [ 4 ], [ ] ] ) gap> CopyGraph(g1:GraphCategory:=SimpleGraphs); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] )
‣ Cube | ( global variable ) |
The 1-skeleton of Plato's cube.
gap> Cube; Graph( Category := SimpleGraphs, Order := 8, Size := 12, Adjacencies := [ [ 2, 3, 5 ], [ 1, 4, 6 ], [ 1, 4, 7 ], [ 2, 3, 8 ], [ 1, 6, 7 ], [ 2, 5, 8 ], [ 3, 5, 8 ], [ 4, 6, 7 ] ] )
‣ CubeGraph( n ) | ( function ) |
Returns the hypercube of dimension n. This is the box product (Cartesian product) of n copies of K_2 (an edge).
gap> CubeGraph(3); Graph( Category := SimpleGraphs, Order := 8, Size := 12, Adjacencies := [ [ 2, 3, 5 ], [ 1, 4, 6 ], [ 1, 4, 7 ], [ 2, 3, 8 ], [ 1, 6, 7 ], [ 2, 5, 8 ], [ 3, 5, 8 ], [ 4, 6, 7 ] ] )
‣ CycleGraph( n ) | ( function ) |
Returns the cyclic graph on n vertices.
gap> CycleGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] )
‣ CylinderGraph( b, h ) | ( function ) |
Returns a cylinder of base b and height h. The order of this graph is b(h+1) and it is constructed by taking h+1 copies of the cyclic graph on b vertices, ordering these cycles linearly and then joining consecutive cycles by a zigzagging (2b)-cycle. This graph is a triangulation of the cylinder where all internal vertices are of degree 6 and the boundary vertices are of degree 4.
gap> g:=CylinderGraph(4,1); Graph( Category := SimpleGraphs, Order := 8, Size := 16, Adjacencies := [ [ 2, 4, 5, 6 ], [ 1, 3, 6, 7 ], [ 2, 4, 7, 8 ], [ 1, 3, 5, 8 ], [ 1, 4, 6, 8 ], [ 1, 2, 5, 7 ], [ 2, 3, 6, 8 ], [ 3, 4, 5, 7 ] ] ) gap> g:=CylinderGraph(4,2); Graph( Category := SimpleGraphs, Order := 12, Size := 28, Adjacencies := [ [ 2, 4, 5, 6 ], [ 1, 3, 6, 7 ], [ 2, 4, 7, 8 ], [ 1, 3, 5, 8 ], [ 1, 4, 6, 8, 9, 10 ], [ 1, 2, 5, 7, 10, 11 ], [ 2, 3, 6, 8, 11, 12 ], [ 3, 4, 5, 7, 9, 12 ], [ 5, 8, 10, 12 ], [ 5, 6, 9, 11 ], [ 6, 7, 10, 12 ], [ 7, 8, 9, 11 ] ] )
‣ DartGraph | ( global variable ) |
A diamond with a pendant vertex and maximum degree 4.
gap> DartGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2 ], [ 1, 3, 4, 5 ], [ 2, 4, 5 ], [ 2, 3 ], [ 2, 3 ] ] )
‣ DeclareQtfyProperty( Name, Filter ) | ( function ) |
For internal use.
Declares a YAGS quantifiable property named Name for filter Filter. This in turns, declares a Boolean GAP property Name and an integer GAP attribute QtfyName.
The user must provide the method Name(Obj, qtfy). If qtfy is false, the method must return a Boolean indicating whether the property holds, otherwise, the method must return a non-negative integer quantifying how far is the object from satisfying the property. In the latter case, returning 0 actually means that the object does satisfy the property.
gap> DeclareQtfyProperty("Is2Regular",Graphs); gap> InstallMethod(Is2Regular,"for graphs",true,[Graphs,IsBool],0, > function(G,qtfy) > local x,count; > count:=0; > for x in Vertices(G) do > if VertexDegree(G,x)<> 2 then > if not qtfy then > return false; > fi; > count:=count+1; > fi; > od; > if not qtfy then return true; fi; > return count; > end); gap> Is2Regular(CycleGraph(4)); true gap> QtfyIs2Regular(CycleGraph(4)); 0 gap> Is2Regular(DiamondGraph); false gap> QtfyIs2Regular(DiamondGraph); 2
‣ Diameter( G ) | ( attribute ) |
Returns the maximum among the distances between pairs of vertices of G.
gap> g:=CycleGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ) gap> Diameter(g); 2
‣ DiamondGraph | ( global variable ) |
The graph on 4 vertices and 5 edges.
gap> DiamondGraph; Graph( Category := SimpleGraphs, Order := 4, Size := 5, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3 ] ] )
‣ DiscreteGraph( n ) | ( function ) |
Returns the discrete graph of order n. A discrete graph is a graph without edges.
gap> DiscreteGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 0, Adjacencies := [ [ ], [ ], [ ], [ ] ] )
‣ DisjointUnion( G, H ) | ( operation ) |
Returns the disjoint union of two graphs G and H, G ∪ H.
gap> g:=PathGraph(3);h:=PathGraph(2); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> DisjointUnion(g,h); Graph( Category := SimpleGraphs, Order := 5, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ], [ 5 ], [ 4 ] ] )
‣ Distance( G, x, y ) | ( operation ) |
Returns the minimum length of a path connecting x to y in G.
gap> Distance(CycleGraph(5),1,3); 2 gap> Distance(CycleGraph(5),1,5); 1
‣ Distances( G, A, B ) | ( operation ) |
Given two lists of vertices A, B of a graph G, Distances returns the list of distances for every pair in the Cartesian product of A and B. The order of the vertices in lists A and B affects the order of the list of distances returned.
gap> g:=CycleGraph(5);; gap> Distances(g, [1,3], [2,4]); [ 1, 2, 1, 1 ] gap> Distances(g, [3,1], [2,4]); [ 1, 1, 1, 2 ]
‣ DistanceGraph( G, Dist ) | ( operation ) |
Given a graph G and a list of distances Dist, DistanceGraph returns the new graph constructed on the vertices of G where two vertices are adjacent iff the distance (in G) between them belongs to the list Dist.
gap> g:=CycleGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ) gap> DistanceGraph(g,[2]); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 3, 4 ], [ 4, 5 ], [ 1, 5 ], [ 1, 2 ], [ 2, 3 ] ] ) gap> DistanceGraph(g,[1,2]); 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 ] ] )
‣ DistanceMatrix( G ) | ( attribute ) |
Returns the distance matrix D of a graph G: D[x][y] is the distance in G from vertex x to vertex y. The matrix may be asymmetric if the graph is not simple. An infinite entry in the matrix means that there is no path between the vertices. Floyd's algorithm is used to compute the matrix.
gap> g:=PathGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] ) gap> Display(DistanceMatrix(g)); [ [ 0, 1, 2, 3 ], [ 1, 0, 1, 2 ], [ 2, 1, 0, 1 ], [ 3, 2, 1, 0 ] ] gap> g:=PathGraph(4:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 3 ], [ 4 ], [ ] ] ) gap> Display(DistanceMatrix(g)); [ [ 0, 1, 2, 3 ], [ infinity, 0, 1, 2 ], [ infinity, infinity, 0, 1 ], [ infinity, infinity, infinity, 0 ] ]
‣ DistanceSet( G, A, B ) | ( operation ) |
Given two subsets of vertices A, B of a graph G, DistanceSet returns the set of distances for every pair in the Cartesian product of A and B.
gap> g:=CycleGraph(5);; gap> DistanceSet(g, [1,3], [2,4]); [ 1, 2 ]
‣ Dodecahedron | ( global variable ) |
The 1-skeleton of Plato's dodecahedron.
gap> Dodecahedron; Graph( Category := SimpleGraphs, Order := 20, Size := 30, Adjacencies := [ [ 2, 5, 6 ], [ 1, 3, 7 ], [ 2, 4, 8 ], [ 3, 5, 9 ], [ 1, 4, 10 ], [ 1, 11, 15 ], [ 2, 11, 12 ], [ 3, 12, 13 ], [ 4, 13, 14 ], [ 5, 14, 15 ], [ 6, 7, 16 ], [ 7, 8, 17 ], [ 8, 9, 18 ], [ 9, 10, 19 ], [ 6, 10, 20 ], [ 11, 17, 20 ], [ 12, 16, 18 ], [ 13, 17, 19 ], [ 14, 18, 20 ], [ 15, 16, 19 ] ] )
‣ DominatedVertices( G ) | ( attribute ) |
Returns the set of dominated vertices of G.
A vertex x is dominated by another vertex y when the closed neighborhood of x is contained in that of y. However, when there are twin vertices (mutually dominated vertices), exactly one of them (in each equivalent class of mutually dominated vertices) does not appear in the returned set.
gap> g1:=PathGraph(3); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) gap> DominatedVertices(g1); [ 1, 3 ] gap> g2:=PathGraph(2); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> DominatedVertices(g2); [ 2 ]
‣ DominoGraph | ( global variable ) |
Two squares glued by an edge.
gap> DominoGraph; Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 4, 6 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 4, 6 ], [ 1, 5 ] ] )
‣ Draw( G ) | ( operation ) |
‣ Draw( G, Highlighted ) | ( operation ) |
Takes a graph G and makes a drawing of it in a separate window possibly with a list of Highlighted vertices. The user can then view and modify the drawing and finally save the vertex coordinates of the drawing into the graph G.
Within the separate window, type h to toggle on/off the help menu. Besides the keyboard commands indicated in the help menu, the user may also move vertices (by dragging them), move the whole drawing (by dragging the background) and scale the drawing (by using the mouse wheel).
gap> Coordinates(Icosahedron); fail gap> Draw(Icosahedron); gap> Coordinates(Icosahedron); [ [ 29, -107 ], [ 65, -239 ], [ 240, -62 ], [ 78, 79 ], [ -107, 28 ], [ -174, -176 ], [ -65, 239 ], [ -239, 62 ], [ -78, -79 ], [ 107, -28 ], [ 174, 176 ], [ -29, 107 ] ]
In its second form, Highlighted is a list of vertices of G and those vertices are drawn in a highlighted color by Draw().
gap> Draw(Cube,[1,4,6,7]);
Draw() uses an external Java program (included with YAGS) and hence, may not work on some platforms.
Current version has been tested successfully on GNU/Linux, Mac OS X and Windows7. For other platforms (specially 32-bit platforms), you should probably (at least) set up correctly the variables YAGSInfo.Draw.prog and YAGSInfo.Draw.opts. The former is a string representing the external binary program path and name; the latter is a list of strings representing the required command line options. Java binaries are provided for 32 and 64 bit versions of GNU/Linux (which also works for Mac OS X) and of MS Windows.
gap> YAGSInfo.Draw.prog; YAGSInfo.Draw.opts; "/opt/gap4r8/pkg/yags/bin/draw/application.linux64/draw" [ ]
The source code for the external program, made using processing (http://processing.org version 2.2.1; version 3 is not working well for us), is YAGS-DIR/bin/draw/draw.pde
‣ DumpObject( Obj ) | ( operation ) |
Dumps all information available for object Obj. This information includes to which categories it belongs as well as its type and hashing information used by GAP.
gap> DumpObject( true ); Object( TypeObj := NewType( NewFamily( "BooleanFamily", [ 11 ], [ 11 ] ), [ 11, 34 ] ), Categories := [ "IS_BOOL" ] )
‣ EasyExec( Dir, ProgName, InString ) | ( operation ) |
‣ EasyExec( ProgName, InString ) | ( operation ) |
Calls external program ProgName located in directory Dir, feeding it with InString as input and returning the output of the external program as a string. Dir must be a directory object or a list of directory objects. If Dir is not provided, ProgName must be in the system's binary PATH. If the program could not be located, fail is returned.
gap> s:=EasyExec("date","");; gap> s; "Sun Nov 9 10:36:16 CST 2014\n" gap> s:=EasyExec("sort","4\n2\n3\n1");; gap> s; "1\n2\n3\n4\n"
This operation have not been tested on MS Windows.
‣ Eccentricity( G, x ) | ( function ) |
Returns the distance from a vertex x in graph G to its most distant vertex in G.
gap> g:=PathGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4 ] ] ) gap> Eccentricity(g,1); 4 gap> Eccentricity(g,3); 2
‣ Edges( G ) | ( operation ) |
Returns the list of edges of the graph G in the case of SimpleGraphs.
gap> g1:=CompleteGraph(3); Graph( Category := SimpleGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) gap> Edges(g1); [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
In the case of UndirectedGraphs, it also returns the loops. While in the other categories, Edges actually does not return the edges, but the loops and arrows of G.
gap> g2:=CompleteGraph(3:GraphCategory:=UndirectedGraphs); Graph( Category := UndirectedGraphs, Order := 3, Size := 6, Adjacencies := [ [ 1, 2, 3 ], [ 1, 2, 3 ], [ 1, 2, 3 ] ] ) gap> Edges(g2); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 3, 3 ] ] gap> g3:=CompleteGraph(3:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 9, Adjacencies := [ [ 1, 2, 3 ], [ 1, 2, 3 ], [ 1, 2, 3 ] ] ) gap> Edges(g3); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ]
‣ EquivalenceRepresentatives( L, Eqiv ) | ( operation ) |
Returns a sublist of L, which is a complete list of representatives of L under the equivalent relation Equiv.
gap> L:=[10,2,6,5,9,7,3,1,4,8]; [ 10, 2, 6, 5, 9, 7, 3, 1, 4, 8 ] gap> EquivalenceRepresentatives(L,function(x,y) return (x mod 4)=(y mod 4); end); [ 10, 5, 7, 4 ] gap> L:=Links(SnubDisphenoid);;Length(L); 8 gap> L:=EquivalenceRepresentatives(L,IsIsomorphicGraph);;Length(L); 2 gap> L; [ Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 3 ], [ 1, 4 ], [ 1, 4 ], [ 2, 3 ] ] ) ]
‣ FanGraph( n ) | ( function ) |
Returns the n-fan: The join of a vertex and a (n+1)-path.
gap> FanGraph(4); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 2, 3, 4, 5, 6 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 4, 6 ], [ 1, 5 ] ] )
‣ FishGraph | ( global variable ) |
A square and a triangle glued by a vertex.
gap> FishGraph; Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 3, 4, 6 ], [ 1, 3 ], [ 1, 2 ], [ 1, 5 ], [ 4, 6 ], [ 1, 5 ] ] )
‣ GemGraph | ( global variable ) |
The 3-fan graph.
gap> GemGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 7, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] )
‣ Girth( G ) | ( attribute ) |
Returns the length of a minimum cycle in G. At this time, Girth is defined only for SimpleGraphs (B.19-3) and UndirectedGraphs (B.21-3). If G has loops, its girth is 1 by definition.
gap> Girth(Octahedron); 3 gap> Girth(PetersenGraph); 5 gap> Girth(Cube); 4 gap> Girth(PathGraph(5)); infinity gap> g:=AddEdges(CycleGraph(4),[[3,3]]:GraphCategory:=UndirectedGraphs); Graph( Category := UndirectedGraphs, Order := 4, Size := 5, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 3, 4 ], [ 1, 3 ] ] ) gap> Girth(g); 1
‣ Graph( Rec ) | ( operation ) |
Returns a new graph created from the record Rec. The record must provide the field Category and either the field Adjacencies or the field AdjMatrix.
gap> Graph(rec(Category:=SimpleGraphs,Adjacencies:=[[2],[1]])); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> Graph(rec(Category:=SimpleGraphs,AdjMatrix:=[[false, true],[true, false]])); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] )
Its main purpose is to import graphs from files, which could have been previously exported using PrintTo.
gap> g:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> Print(g); Graph( rec( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) ) gap> PrintTo("aux.g","h:=",g,";"); gap> Read("aux.g"); gap> h; Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] )
‣ GraphAttributeStatistics( OrderList, ProbList, Attribute ) | ( function ) |
Returns statistics for graph attribute Attribute. For each of the orders n in OrderList and for each of the probabilities p in ProbList this function generates 100 random graphs of order n and edge probability p and then evaluates the graph attribute Attribute on each of them. The function then returns statistical data on these experiments. The form in which the statistical data is reported depend on a number of issues and is best explained by examples.
First let us consider the case where Attribute is a Boolean attribute (always returns true or false) and where OrderList and ProbList consist of a unique value. In this case, the respective lists may be replaced by the corresponding unique values on invocation:
gap> GraphAttributeStatistics(10,1/2,IsCliqueHelly); 32
This tells us that 32 of the 100 examined random graphs resulted to be clique-Helly; The random sample was constructed using graphs of order 10 and edge probability 1/2.
Now we can specify a list of probabilities to be examined:
gap> GraphAttributeStatistics(10,1/10*[1..9],IsCliqueHelly); [ 100, 100, 94, 63, 34, 16, 30, 76, 95 ]
The last example tells us that, for graphs on 10 vertices, the property IsCliqueHelly is least probable to be true for graphs with edge probabilities 5/10 6/10 and 7/10, being 6/10 the probability that reaches the minimum in the random sample. Note that the 34 in the previous example does not match the 32 in the first one, this is to be expected as the statistics are compiled from a random sample of graphs. Also, note that in the previous example, 900 random graphs where generated and examined.
We can also specify a list of orders to consider:
gap> GraphAttributeStatistics([10,12..20],1/10*[1..9],IsCliqueHelly); [ [ 100, 100, 92, 62, 37, 16, 36, 70, 97 ], [ 100, 99, 83, 34, 8, 1, 19, 68, 97 ], [ 100, 96, 54, 4, 2, 0, 6, 54, 98 ], [ 100, 89, 26, 2, 0, 0, 9, 42, 96 ], [ 100, 70, 13, 1, 0, 0, 6, 24, 94 ], [ 99, 70, 5, 0, 0, 0, 4, 22, 92 ] ] gap> Display(last); [ [ 100, 100, 92, 62, 37, 16, 36, 70, 97 ], [ 100, 99, 83, 34, 8, 1, 19, 68, 97 ], [ 100, 96, 54, 4, 2, 0, 6, 54, 98 ], [ 100, 89, 26, 2, 0, 0, 9, 42, 96 ], [ 100, 70, 13, 1, 0, 0, 6, 24, 94 ], [ 99, 70, 5, 0, 0, 0, 4, 22, 92 ] ]
Which tell us that the observed bimodal distribution is even more pronounced when the order of the graphs considered grows.
In the case of a non-Boolean attribute GraphAttributeStatistics() reports the values that Attribute took on the sample as well as the number of times that each of these values where obtained:
gap> GraphAttributeStatistics(10,1/2,Diameter); [ [ 2, 34 ], [ 3, 59 ], [ 4, 5 ], [ 5, 1 ], [ infinity, 1 ] ]
The returned statistics mean that among the 100 generated random graphs on 10 vertices with edge probability 1/2, there were 34 graphs with diameter 2, 59 graphs of diameter 3, 5 of 4, 1 of 5 and there was one graph which was not connected.
Now it should be evident the format of the returned statistics when we specify a list of probabilities and/or a list of orders to be considered for a non-Boolean Attribute:
gap> GraphAttributeStatistics(10,1/5*[1..4],Diameter); [ [ [ 3, 1 ], [ 4, 7 ], [ 5, 8 ], [ 6, 6 ], [ infinity, 78 ] ], [ [ 2, 6 ], [ 3, 55 ], [ 4, 21 ], [ 5, 1 ], [ 6, 1 ], [ infinity, 16 ] ], [ [ 2, 74 ], [ 3, 25 ], [ 4, 1 ] ], [ [ 2, 100 ] ] ] gap> GraphAttributeStatistics([10,12,14],1/5*[1..4],Diameter); [ [ [ [ 3, 2 ], [ 4, 8 ], [ 5, 11 ], [ 6, 5 ], [ 7, 1 ], [ infinity, 73 ] ], [ [ 2, 6 ], [ 3, 56 ], [ 4, 23 ], [ 5, 7 ], [ infinity, 8 ] ], [ [ 2, 72 ], [ 3, 27 ], [ infinity, 1 ] ], [ [ 2, 99 ], [ 3, 1 ] ] ], [ [ [ 3, 4 ], [ 4, 13 ], [ 5, 10 ], [ 6, 6 ], [ 7, 3 ], [ infinity, 64 ] ], [ [ 2, 7 ], [ 3, 69 ], [ 4, 17 ], [ infinity, 7 ] ], [ [ 2, 76 ], [ 3, 24 ] ], [ [ 2, 100 ] ] ], [ [ [ 4, 12 ], [ 5, 16 ], [ 6, 7 ], [ 7, 3 ], [ infinity, 62 ] ], [ [ 2, 8 ], [ 3, 86 ], [ 4, 4 ], [ infinity, 2 ] ], [ [ 2, 86 ], [ 3, 14 ] ], [ [ 2, 100 ] ] ] ]
‣ Graph6ToGraph( String ) | ( operation ) |
Returns the graph represented by String which is encoded using Brendan McKay's graph6 format. This operation allows us to read data in databases which use this format. Several such databases can be found here: https://cs.anu.edu.au/people/Brendan.McKay/data/graphs.html.
The graph6 format is described here:
https://cs.anu.edu.au/people/Brendan.McKay/data/formats.txt.
gap> Graph6ToGraph("D?{"); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 5 ], [ 5 ], [ 5 ], [ 5 ], [ 1, 2, 3, 4 ] ] ) gap> Graph6ToGraph("FUzvW"); Graph( Category := SimpleGraphs, Order := 7, Size := 15, Adjacencies := [ [ 3, 4, 5, 6, 7 ], [ 4, 5, 6, 7 ], [ 1, 5, 6, 7 ], [ 1, 2, 6 ], [ 1, 2, 3, 7 ], [ 1, 2, 3, 4, 7 ], [ 1, 2, 3, 5, 6 ] ] ) gap> Graph6ToGraph("HUzv~z}"); Graph( Category := SimpleGraphs, Order := 9, Size := 29, Adjacencies := [ [ 3, 4, 5, 6, 7, 8, 9 ], [ 4, 5, 6, 7, 8, 9 ], [ 1, 5, 6, 7, 8, 9 ], [ 1, 2, 6, 7, 8, 9 ], [ 1, 2, 3, 7, 8, 9 ], [ 1, 2, 3, 4, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 9 ], [ 1, 2, 3, 4, 5, 6 ], [ 1, 2, 3, 4, 5, 6, 7 ] ] )
See also ImportGraph6 (B.9-2).
‣ GraphByAdjacencies( AdjList ) | ( function ) |
Returns a new graph having AdjList as its list of adjacencies. The order of the created graph is Length(AdjList), and the set of neighbors of vertex x is AdjList[x].
gap> GraphByAdjacencies([[2],[1,3],[2]]); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] )
Note, however, that the graph is forced to comply with the TargetGraphCategory.
gap> GraphByAdjacencies([[1,2,3],[],[]]); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2, 3 ], [ 1 ], [ 1 ] ] )
‣ GraphByAdjMatrix( Mat ) | ( function ) |
Returns a new graph created from an adjacency matrix Mat. The matrix Mat must be a square boolean matrix.
gap> m:=[ [ false, true, false ], [ true, false, true ], [ false, true, false ] ];; gap> g:=GraphByAdjMatrix(m); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) gap> AdjMatrix(g); [ [ false, true, false ], [ true, false, true ], [ false, true, false ] ]
Note, however, that the graph is forced to comply with the TargetGraphCategory.
gap> m:=[ [ true, true], [ false, false ] ];; gap> g:=GraphByAdjMatrix(m); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> AdjMatrix(g); [ [ false, true ], [ true, false ] ]
‣ GraphByCompleteCover( Cover ) | ( function ) |
Returns the minimal graph where the elements of Cover are (the vertex sets of) complete subgraphs.
gap> GraphByCompleteCover([[1,2,3,4],[4,6,7]]); Graph( Category := SimpleGraphs, Order := 7, Size := 9, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3, 6, 7 ], [ ], [ 4, 7 ], [ 4, 6 ] ] )
‣ GraphByEdges( L ) | ( function ) |
Returns the minimal graph such that the pairs in L are edges.
gap> GraphByEdges([[1,2],[1,3],[1,4],[4,5]]); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2, 3, 4 ], [ 1 ], [ 1 ], [ 1, 5 ], [ 4 ] ] )
The vertices of the constructed graph range from 1 to the maximum of the numbers appearing in L.
gap> GraphByEdges([[4,3],[4,5]]); Graph( Category := SimpleGraphs, Order := 5, Size := 2, Adjacencies := [ [ ], [ ], [ 4 ], [ 3, 5 ], [ 4 ] ] )
Note that GraphByWalks (B.7-11) can do the same and much more.
‣ GraphByRelation( V, Rel ) | ( function ) |
‣ GraphByRelation( n, Rel ) | ( function ) |
Returns a new graph created from a set of vertices V and a binary relation Rel, where x∼ y iff Rel(x,y)=true. In the second form, n is an integer and V is assumed to be {1, 2, ..., n}.
gap> Rel:=function(x,y) return Intersection(x,y)<>[]; end;; gap> GraphByRelation([[1,2,3],[3,4,5],[5,6,7]],Rel); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) gap> GraphByRelation(8,function(x,y) return AbsInt(x-y)<=2; end); Graph( Category := SimpleGraphs, Order := 8, Size := 13, Adjacencies := [ [ 2, 3 ], [ 1, 3, 4 ], [ 1, 2, 4, 5 ], [ 2, 3, 5, 6 ], [ 3, 4, 6, 7 ], [ 4, 5, 7, 8 ], [ 5, 6, 8 ], [ 6, 7 ] ] )
‣ GraphByWalks( Walk1, Walk2, ... ) | ( function ) |
Returns the minimal graph such that Walk1, Walk2, etc are Walks.
gap> GraphByWalks([1,2,3,4,1],[1,5,6]); Graph( Category := SimpleGraphs, Order := 6, Size := 6, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ], [ 1, 6 ], [ 5 ] ] )
Walks can be nested, which greatly improves the versatility of this function.
gap> GraphByWalks([1,[2,3,4],5],[5,6]); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 5 ], [ 1, 2, 4, 5 ], [ 1, 3, 5 ], [ 2, 3, 4, 6 ], [ 5 ] ] )
The vertices in the constructed graph range from 1 to the maximum of the numbers appearing in Walk1, Walk2, ... etc.
gap> GraphByWalks([4,2],[3,6]); Graph( Category := SimpleGraphs, Order := 6, Size := 2, Adjacencies := [ [ ], [ 4 ], [ 6 ], [ 2 ], [ ], [ 3 ] ] )
‣ GraphCategory( [G, ...] ) | ( function ) |
For internal use. Returns the minimal common graph category to a list of graphs. If the list of graphs is empty, the default category is returned. The partial order (by inclusion) among graph categories is as follows:
Graphs
/ \
UndirectedGraphs LooplessGraphs
\ / \
SimpleGraphs OrientedGraphs
gap> g1:=CompleteGraph(2:GraphCategory:=SimpleGraphs); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> g2:=CompleteGraph(2:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ ] ] ) gap> g3:=CompleteGraph(2:GraphCategory:=UndirectedGraphs); Graph( Category := UndirectedGraphs, Order := 2, Size := 3, Adjacencies := [ [ 1, 2 ], [ 1, 2 ] ] ) gap> GraphCategory([g1,g2,g3]); <Category "Graphs"> gap> GraphCategory([g1,g2]); <Category "LooplessGraphs"> gap> GraphCategory([g1,g3]); <Category "UndirectedGraphs">
‣ Graphs( G ) | ( function ) |
Graphs is the most general graph category in YAGS. This category contains all graphs that can be represented in YAGS. A graph in this category may contain loops, arrows and edges (which in YAGS are exactly the same as two opposite arrows between some pair of vertices). This graph category has no parent category.
gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 4, Adjacencies := [ [ 1, 2 ], [ 1 ], [ 2 ] ] ) gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=SimpleGraphs); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] )
‣ GraphsOfGivenOrder( n ) | ( operation ) |
Returns the list of all graphs of order n (up to isomorphism). This operation uses Brendan McKay's data published here:
https://cs.anu.edu.au/people/Brendan.McKay/data/graphs.html.
These data are included with the YAGS distribution in its data directory. Hence this operation simply reads the corresponding file in that directory using ImportGraph6( Filename ). Therefore, the integer n must be in the range from 1 up to 9.
gap> GraphsOfGivenOrder(2); [ Graph( Category := SimpleGraphs, Order := 2, Size := 0, Adjacencies := [ [ ], [ ] ] ), Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) ] gap> GraphsOfGivenOrder(3); [ Graph( Category := SimpleGraphs, Order := 3, Size := 0, Adjacencies := [ [ ], [ ], [ ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 1, Adjacencies := [ [ 3 ], [ ], [ 1 ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 3 ], [ 3 ], [ 1, 2 ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) ] gap> Length(GraphsOfGivenOrder(9)); 274668
Data for graphs on 10 vertices is also available, but not included with YAGS, it may not be practical to use that data, but if you would like to try, all you have to do is to copy (and to uncompress) the corresponding file into the directory YAGS-DIR/data/.
gap> GraphsOfGivenOrder(10); #W Unreadable File: /opt/gap4r8/pkg/yags/data/graph10.g6 fail
‣ GraphSum( G, L ) | ( operation ) |
Returns the lexicographic sum of a list of graphs L over a graph G.
The lexicographic sum is computed as follows:
Given G, with Order( G )=n and a list of n graphs L = [G_1, ..., G_n], we take the disjoint union of G_1,G_2, ...,G_n and then we add all the edges between G_i and G_j whenever [i,j] is and edge of G.
If L contains holes, the trivial graph is used in place.
gap> t:=TrivialGraph;; g:=CycleGraph(4);; gap> GraphSum(PathGraph(3),[t,g,t]); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 5, 6 ], [ 1, 2, 4, 6 ], [ 1, 3, 5, 6 ], [ 1, 2, 4, 6 ], [ 2, 3, 4, 5 ] ] ) gap> GraphSum(PathGraph(3),[,g,]); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 5, 6 ], [ 1, 2, 4, 6 ], [ 1, 3, 5, 6 ], [ 1, 2, 4, 6 ], [ 2, 3, 4, 5 ] ] )
‣ GraphToRaw( FileName, G ) | ( operation ) |
‣ GraphToRaw( FileName, G, Highlighted ) | ( operation ) |
Converts a YAGS graph G into a raw format (number of vertices, coordinates, adjacency matrix, number of highlighted vertices and list of highlighted vertices) and writes the converted data to the file FileName. For use by the external program draw (see Draw (B.4-15) ). Intended for internal use only.
gap> g:=CycleGraph(4);; gap> GraphToRaw("mygraph.raw",g);
If Highlighted is not specified, it is assumed to be the empty list. The vertices listed in Highlighted are drawn in a highlighted color by Draw().
‣ GraphUpdateFromRaw( FileName, G ) | ( operation ) |
Updates the coordinates of G from a file FileName in raw format as written by draw (see Draw (B.4-15) ). Intended for internal use only.
‣ GroupGraph( G, Grp, Act ) | ( operation ) |
‣ GroupGraph( G, Grp ) | ( operation ) |
Given a graph G, a group Grp and an action Act of Grp on some set S which contains Vertices( G ), GroupGraph returns a new graph with vertex set {Act(v,g) : g ∈ Grp, v ∈ Vertices( G )} and edge set {{Act(v,g),Act(u,g)}: g∈ Grp, {u,v}∈ Edges( G )}.
If Act is omitted, the standard GAP action OnPoints is used.
gap> GroupGraph(GraphByWalks([1,2]),Group([(1,2,3,4,5),(2,5)(3,4)])); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] )
‣ HararyToMcKay( Spec ) | ( operation ) |
‣ McKayToHarary( index ) | ( operation ) |
Returns the McKay's index of a Harary's graph specification Spec and vice versa. Frank Harary published in his book [10], a list of all 208 simple graphs of order up to 6 (up to isomorphism). Each of them had a label (which we call Harary's graph specification) of the form [ n, m, s ] where n is the number of vertices, m is the number of edges, and s is a consecutive integer which uniquely identifies the graph from the others with the same n and m. On the other hand, Brendan McKay published data sets containing a list of all graphs of order up to 10 (also up to isomorphism), here:
https://cs.anu.edu.au/people/Brendan.McKay/data/graphs.html
Each graph in these data sets appears in some specific position (which we call McKay's index). We found it convenient to have an automated way to convert from Harary's graph specifications to McKay's indexes and vice versa.
gap> HararyToMcKay([1,0,1]); 1 gap> HararyToMcKay([1,0,2]); fail gap> HararyToMcKay([5,5,2]); 31 gap> HararyToMcKay([5,5,3]); 34 gap> HararyToMcKay([5,5,5]); 30 gap> HararyToMcKay([5,5,6]); 45 gap> HararyToMcKay([5,5,7]); fail gap> HararyToMcKay([6,15,1]); 208 gap> HararyToMcKay([6,15,2]); fail
gap> List([1..208],McKayToHarary); [ [ 1, 0, 1 ], [ 2, 0, 1 ], [ 2, 1, 1 ], [ 3, 0, 1 ], [ 3, 1, 1 ], [ 3, 2, 1 ], [ 3, 3, 1 ], [ 4, 0, 1 ], [ 4, 1, 1 ], [ 4, 2, 1 ], [ 4, 3, 3 ], [ 4, 2, 2 ], [ 4, 3, 1 ], [ 4, 3, 2 ], [ 4, 4, 1 ], --- many more lines here --- [ 6, 10, 10 ], [ 6, 10, 7 ], [ 6, 11, 3 ], [ 6, 12, 1 ], [ 6, 13, 1 ], [ 6, 11, 7 ], [ 6, 11, 9 ], [ 6, 11, 8 ], [ 6, 12, 4 ], [ 6, 12, 5 ], [ 6, 13, 2 ], [ 6, 14, 1 ], [ 6, 15, 1 ] ] gap> McKayToHarary(209); fail
‣ HouseGraph | ( global variable ) |
A 4-cycle and a triangle glued by an edge.
gap> HouseGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2, 4, 5 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] )
‣ Icosahedron | ( global variable ) |
The 1-skeleton of Plato's icosahedron.
gap> Icosahedron; Graph( Category := SimpleGraphs, Order := 12, Size := 30, Adjacencies := [ [ 2, 3, 4, 5, 6 ], [ 1, 3, 6, 9, 10 ], [ 1, 2, 4, 10, 11 ], [ 1, 3, 5, 7, 11 ], [ 1, 4, 6, 7, 8 ], [ 1, 2, 5, 8, 9 ], [ 4, 5, 8, 11, 12 ], [ 5, 6, 7, 9, 12 ], [ 2, 6, 8, 10, 12 ], [ 2, 3, 9, 11, 12 ], [ 3, 4, 7, 10, 12 ], [ 7, 8, 9, 10, 11 ] ] )
‣ ImportGraph6( Filename ) | ( operation ) |
Returns the list of graphs represented in Filename which are encoded using Brendan McKay's graph6 format. This operation allows us to read data in databases which use this format. Several such databases can be found here:
https://cs.anu.edu.au/people/Brendan.McKay/data/graphs.html.
The graph6 format is described here:
https://cs.anu.edu.au/people/Brendan.McKay/data/formats.txt.
The following example assumes that you have a file named graph3.g6 in your working directory which encodes graphs in graph6 format; the contents of this file is assumed to be as indicated after the first command in the example. It is also assumed that your Operative System is a Unix-like system.
gap> Exec("cat graph3.g6"); B? BO BW Bw gap> ImportGraph6("graph3.g6"); [ Graph( Category := SimpleGraphs, Order := 3, Size := 0, Adjacencies := [ [ ], [ ], [ ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 1, Adjacencies := [ [ 3 ], [ ], [ 1 ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 3 ], [ 3 ], [ 1, 2 ] ] ), Graph( Category := SimpleGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) ]
See also Graph6ToGraph (B.7-5).
‣ in( G, Catgy ) | ( operation ) |
Returns true if graph G belongs to category Catgy and false otherwise.
gap> g:=WheelGraph(4); Graph( Category := SimpleGraphs, Order := 5, Size := 8, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 5 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 2, 4 ] ] ) gap> g in SimpleGraphs; true gap> g in Graphs; true gap> g in OrientedGraphs; false
‣ InducedSubgraph( G, V ) | ( operation ) |
Returns the subgraph of the graph G induced by the vertex set V.
gap> g:=CycleGraph(6); Graph( Category := SimpleGraphs, Order := 6, Size := 6, Adjacencies := [ [ 2, 6 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4, 6 ], [ 1, 5 ] ] ) gap> InducedSubgraph(g,[3,4,6]); Graph( Category := SimpleGraphs, Order := 3, Size := 1, Adjacencies := [ [ 2 ], [ 1 ], [ ] ] )
The order of the elements in V does matter.
gap> InducedSubgraph(g,[6,3,4]); Graph( Category := SimpleGraphs, Order := 3, Size := 1, Adjacencies := [ [ ], [ 3 ], [ 2 ] ] )
‣ InNeigh( G, x ) | ( operation ) |
Returns the list of in-neighbors of x in G.
gap> tt:=CompleteGraph(5:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 5, Size := 10, Adjacencies := [ [ 2, 3, 4, 5 ], [ 3, 4, 5 ], [ 4, 5 ], [ 5 ], [ ] ] ) gap> InNeigh(tt,3); [ 1, 2 ] gap> OutNeigh(tt,3); [ 4, 5 ]
‣ InteriorVertices( G ) | ( attribute ) |
When G is (an underlying graph of a Whitney triangulation of) a compact surface, it returns the list of vertices in the interior (of the triangulation) of the surface. That is, the list of vertices of G that have links isomorphic to a cycle. It returns fail if G is not a compact surface.
gap> InteriorVertices(WheelGraph(4,2)); [ 1, 2, 3, 4, 5 ] gap> InteriorVertices(Octahedron); [ 1, 2, 3, 4, 5, 6 ]
‣ IntersectionGraph( L ) | ( function ) |
Returns the intersection graph of the family of sets L. This graph has a vertex for every set in L, and two such vertices are adjacent iff the corresponding sets have non-empty intersection.
gap> IntersectionGraph([[1,2,3],[3,4,5],[5,6,7]]); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] )
‣ IsBoolean( Obj ) | ( function ) |
Returns true if object Obj is true or false and false otherwise.
gap> IsBoolean( true ); IsBoolean( fail ); IsBoolean ( false ); true false true
‣ IsCliqueGated( G ) | ( property ) |
Returns true if G is a clique gated graph [9].
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ IsCliqueHelly( G ) | ( property ) |
Returns true if the set of (maximal) cliques G satisfy the Helly property.
The Helly property is defined as follows:
A non-empty family F of non-empty sets satisfies the Helly property if every pairwise intersecting subfamily of F has a non-empty total intersection.
Here we use the Dragan-Szwarcfiter characterization [5][28] to compute the Helly property.
gap> g:=SunGraph(3); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 2, 6 ], [ 1, 3, 4, 6 ], [ 2, 4 ], [ 2, 3, 5, 6 ], [ 4, 6 ], [ 1, 2, 4, 5 ] ] ) gap> IsCliqueHelly(g); false
‣ IsCompactSurface( G ) | ( property ) |
Returns true if every link of G is either an n-cycle, for n≥ 4 or an m-path, for m≥ 2. (not necessarily the same n/m for all vertices); it returns false otherwise.
This notion correspond to Whitney triangulations of compact surfaces [14] in which the (maximal) cliques of the graph are exactly the triangles of the triangulation.
gap> IsCompactSurface(Icosahedron); true gap> IsCompactSurface(RemoveVertices(Icosahedron,[1])); true gap> IsCompactSurface(WheelGraph(4,2)); true gap> IsCompactSurface(Tetrahedron); false gap> IsCompactSurface(CompleteGraph(2)); false gap> IsCompactSurface(CompleteGraph(3)); true gap> IsCompactSurface(CompleteGraph(4)); false
Topologically, the difference between a surface and a compact surface is that the points of a surface always have a open neighborhood homeomorphic to an open disk, whereas a compact surface may also contain points with open neighborhoods homeomorphic to a closed half-plane.
‣ IsComplete( G, L ) | ( operation ) |
Returns true if L induces a complete subgraph of G.
gap> IsComplete(DiamondGraph,[1,2,3]); true gap> IsComplete(DiamondGraph,[1,2,4]); false
‣ IsCompleteGraph( G ) | ( property ) |
Returns true if graph G is a complete graph, false otherwise. In a complete graph every pair of vertices is an edge.
‣ IsDiamondFree( G ) | ( property ) |
Returns true if G is free from induced diamonds (see DiamondGraph (B.4-4)); false otherwise.
gap> IsDiamondFree(Cube); true gap> IsDiamondFree(Octahedron); false
‣ IsEdge( G, x, y ) | ( operation ) |
‣ IsEdge( G, e ) | ( operation ) |
Returns true if e:=[x,y] is an edge of G.
gap> IsEdge(PathGraph(3),1,2); true gap> IsEdge(PathGraph(3),[1,2]); true gap> IsEdge(PathGraph(3),1,3); false gap> IsEdge(PathGraph(3),[1,3]); false
The first form, IsEdge(G, x, y), is a bit faster and hence more suitable for use in algorithms which make extensive use of this operation. On the other hand, the first form does no error checking at all, and hence, it may produce an error where the second form returns false (for instance when x is not a vertex of G). The second form is therefore a bit slower, but more robust.
gap> IsEdge(PathGraph(3),[7,3]); false gap> IsEdge(PathGraph(3),7,3); Error, List Element: <list>[7] must have an assigned value
‣ IsIsomorphicGraph( G, H ) | ( operation ) |
Returns true when G is isomorphic to H and false otherwise.
gap> g:=PowerGraph(CycleGraph(6),2);;h:=Octahedron;; gap> IsIsomorphicGraph(g,h); true
‣ IsLocallyConstant( G ) | ( property ) |
Returns true if all the links of G are isomorphic to each other; false otherwise.
gap> IsLocallyConstant(PathGraph(2)); true gap> IsLocallyConstant(PathGraph(3)); false gap> IsLocallyConstant(CompleteGraph(3)); true gap> IsLocallyConstant(CycleGraph(4)); true gap> IsLocallyConstant(Icosahedron); true gap> IsLocallyConstant(TorusGraph(5,4)); true gap> IsLocallyConstant(WheelGraph(4,2)); false gap> IsLocallyConstant(SnubDisphenoid); false
‣ IsLocallyH( G, H ) | ( operation ) |
Returns true if all the links of G are isomorphic to H; false otherwise.
gap> IsLocallyH(Octahedron,CycleGraph(4)); true gap> IsLocallyH(Octahedron,CycleGraph(5)); false gap> IsLocallyH(Icosahedron,CycleGraph(5)); true gap> IsLocallyH(TorusGraph(4,4),CycleGraph(6)); true
‣ IsLoopless( G ) | ( property ) |
Returns true if the graph G have no loops; false otherwise. Loops are edges from a vertex to itself.
‣ IsoMorphism( G, H ) | ( operation ) |
Returns one isomorphism from G to H or fail if none exists. If G has n vertices, an isomorphisms f : G→ H is represented as the list F=[f(1), f(2), ..., f(n)].
gap> g:=CycleGraph(4);;h:=CompleteBipartiteGraph(2,2);; gap> f:=IsoMorphism(g,h); [ 1, 3, 2, 4 ]
See NextIsoMorphism (B.14-1).
‣ IsoMorphisms( G, H ) | ( operation ) |
Returns the list of all isomorphism from G to H. If G has n vertices, an isomorphisms f:G→ H is represented as the list F=[f(1), f(2), ..., f(n)].
gap> g:=CycleGraph(4);;h:=CompleteBipartiteGraph(2,2);; gap> IsoMorphisms(g,h); [ [ 1, 3, 2, 4 ], [ 1, 4, 2, 3 ], [ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ], [ 3, 2, 4, 1 ], [ 4, 1, 3, 2 ], [ 4, 2, 3, 1 ] ]
‣ IsOriented( G ) | ( property ) |
Returns true if the graph G is an oriented graph, false otherwise. Regardless of the categories that G belongs to, G is oriented if whenever [x,y] is an edge of G, [y,x] is not.
‣ IsSimple( G ) | ( property ) |
Returns true if the graph G is a simple graph, false otherwise. Regardless of the categories that G belongs to, G is simple if and only if G is undirected and loopless.
‣ IsSurface( G ) | ( property ) |
Returns true if every link of G is an n-cycle, for n≥ 4 (not necessarily the same n for all vertices); false otherwise.
This notion correspond to Whitney triangulations of (closed) surfaces [14] in which the (maximal) cliques of the graph are exactly the triangles of the triangulation.
gap> IsSurface(SnubDisphenoid); true gap> IsSurface(Icosahedron); true gap> IsSurface(RemoveVertices(Icosahedron,[1])); false gap> IsSurface(TorusGraph(4,5)); true gap> IsSurface(WheelGraph(4,2)); false gap> IsSurface(Tetrahedron); false
Topologically, the difference between a (closed) surface and a compact surface is that the points of a surface always have a open neighborhood homeomorphic to an open disk, whereas a compact surface may also contain points with open neighborhoods homeomorphic to a closed half-plane.
‣ IsTournament( G ) | ( property ) |
Returns true if G is a tournament. A tournament is a graph without loops and such that for every pair of vertices x, y, either [x,y] is an arrow of G , or [y,x] is an arrow of G, but not both.
gap> tt:=CompleteGraph(5:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 5, Size := 10, Adjacencies := [ [ 2, 3, 4, 5 ], [ 3, 4, 5 ], [ 4, 5 ], [ 5 ], [ ] ] ) gap> IsTournament(tt); true
‣ IsTransitiveTournament( G ) | ( property ) |
Returns true if G is a transitive tournament. A tournament is a transitive tournament if whenever [x,y] and [y,z] are arrows of the tournament, [x,z] is also an arrow of the tournament.
gap> tt:=CompleteGraph(5:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 5, Size := 10, Adjacencies := [ [ 2, 3, 4, 5 ], [ 3, 4, 5 ], [ 4, 5 ], [ 5 ], [ ] ] ) gap> IsTransitiveTournament(tt); true
‣ IsUndirected( G ) | ( property ) |
Returns true if the graph G is an undirected graph; false otherwise. Regardless of the categories that G belongs to, G is undirected if whenever [x,y] is an edge of G, [y,x] is also an edge of G.
‣ JohnsonGraph( n, r ) | ( function ) |
Returns the Johnson graph J(n,r). The Johnson graph is the graph whose vertices are r-subset of the set {1, 2, ..., n}, two of them being adjacent iff they intersect in exactly r-1 elements.
gap> g:=JohnsonGraph(4,2); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 3, 4, 6 ], [ 2, 3, 4, 5 ] ] ) gap> VertexNames(g); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
‣ Join( G, H ) | ( operation ) |
Returns the join graph G + H of G and H (also known as the Zykov sum); it is the graph obtained from the disjoint union of G and H by adding every possible edge from every vertex in G to every vertex in H.
gap> g:=DiscreteGraph(2);h:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 2, Size := 0, Adjacencies := [ [ ], [ ] ] ) Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> Join(g,h); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 3, 4, 5, 6 ], [ 3, 4, 5, 6 ], [ 1, 2, 4, 6 ], [ 1, 2, 3, 5 ], [ 1, 2, 4, 6 ], [ 1, 2, 3, 5 ] ] )
‣ KiteGraph | ( global variable ) |
A diamond (see DiamondGraph (B.4-4)) with a pendant vertex and maximum degree 3.
gap> KiteGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2 ], [ 1, 3, 4 ], [ 2, 4, 5 ], [ 2, 3, 5 ], [ 3, 4 ] ] )
‣ LineGraph( G ) | ( operation ) |
Returns the line graph, L(G), of graph G. The line graph is the intersection graph of the edges of G, i.e. the vertices of L(G) are the edges of G two of them being adjacent iff they are incident.
gap> g:=Tetrahedron; Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) gap> LineGraph(g); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 3, 4, 6 ], [ 2, 3, 4, 5 ] ] )
‣ Link( G, x ) | ( operation ) |
Returns the subgraph of G induced by the neighbors of x.
gap> Link(SnubDisphenoid,1); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ) gap> Link(SnubDisphenoid,3); Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 3 ], [ 1, 4 ], [ 1, 4 ], [ 2, 3 ] ] )
‣ Links( G ) | ( attribute ) |
Returns the list of subgraphs of G induced by the neighbors of each vertex of G.
gap> Links(SnubDisphenoid); [ Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ), Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 3 ], [ 1, 4 ], [ 1, 4 ], [ 2, 3 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 3 ], [ 1, 4 ], [ 1, 4 ], [ 2, 3 ] ] ), Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ), Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 3, 4 ], [ 3, 4 ], [ 1, 2 ], [ 1, 2 ] ] ), Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 3 ], [ 1, 4 ], [ 1, 4 ], [ 2, 3 ] ] ) ]
‣ LooplessGraphs( G ) | ( function ) |
LooplessGraphs is a graph category in YAGS. A graph in this category may contain arrows and edges but no loops. The parent of this category is Graphs.
gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 4, Adjacencies := [ [ 1, 2 ], [ 1 ], [ 2 ] ] ) gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=LooplessGraphs); Graph( Category := LooplessGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2 ], [ 1 ], [ 2 ] ] )
‣ MaxDegree( G ) | ( operation ) |
Returns the maximum degree of a vertex in the graph G.
gap> g:=GemGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 7, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] ) gap> MaxDegree(g); 4
‣ MinDegree( G ) | ( operation ) |
Returns the minimum degree of a vertex in the graph G.
gap> g:=GemGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 7, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] ) gap> MinDegree(g); 2
‣ NextIsoMorphism( G, H, F ) | ( operation ) |
Returns the next isomorphism (after F) from G to H in the lexicographic order; returns fail if there are no more isomorphisms. If G has n vertices, an isomorphisms f : G→ H is represented as the list F=[f(1), f(2), ..., f(n)].
gap> g:=CycleGraph(4);;h:=CompleteBipartiteGraph(2,2);; gap> f:=IsoMorphism(g,h); [ 1, 3, 2, 4 ] gap> NextIsoMorphism(g,h,f); [ 1, 4, 2, 3 ] gap> NextIsoMorphism(g,h,f); [ 2, 3, 1, 4 ] gap> NextIsoMorphism(g,h,f); [ 2, 4, 1, 3 ]
‣ NextPropertyMorphism( G, H, F, PropList ) | ( operation ) |
Returns the next morphism (in lexicographic order) from G to H satisfying the list of properties PropList starting with (possibly incomplete) morphism F. The morphism found will be returned and stored in F in order to use it as the next starting point, in case NextPropertyMorphism is called again. The operation returns fail if there are no more morphisms of the specified type (but, for technical reasons, F stores the list [fail] instead).
A number of preprogrammed properties are provided by YAGS, and the user may create additional ones. The properties provided are: CHK_WEAK, CHK_MORPH, CHK_METRIC, CHK_CMPLT, CHK_MONO and CHK_EPI.
If G has n vertices and f:G→ H is a morphism, it is represented as F=[f(1), f(2), ..., f(n)].
gap> g:=CycleGraph(4);;h:=CompleteBipartiteGraph(2,2);; gap> f:=[];; PropList:=[CHK_MORPH,CHK_MONO];; gap> NextPropertyMorphism(g,h,f,PropList); [ 1, 3, 2, 4 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 1, 4, 2, 3 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 2, 3, 1, 4 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 2, 4, 1, 3 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 3, 1, 4, 2 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 3, 2, 4, 1 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 4, 1, 3, 2 ] gap> NextPropertyMorphism(g,h,f,PropList); [ 4, 2, 3, 1 ] gap> NextPropertyMorphism(g,h,f,PropList); fail
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
Extensive information about graph morphisms can be found in Chapter 5.
‣ NumberOfCliques( G ) | ( attribute ) |
‣ NumberOfCliques( G, maxNumCli ) | ( operation ) |
Returns the number of (maximal) cliques of G. In the second form, it stops computing cliques after maxNumCli of them have been counted and returns maxNumCli in case G has maxNumCli or more cliques.
gap> NumberOfCliques(Icosahedron,15); 15 gap> NumberOfCliques(Icosahedron); 20 gap> NumberOfCliques(Icosahedron,50); 20
This implementation discards the cliques once counted hence, given enough time, it can compute the number of cliques of G even if the set of cliques does not fit in memory. This test may take several minutes to complete:
gap> NumberOfCliques(OctahedralGraph(30)); 1073741824
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ NumberOfConnectedComponents( G ) | ( attribute ) |
Returns the number of connected components of G. See ConnectedComponents (B.3-17).
‣ OctahedralGraph( n ) | ( function ) |
Return the n-dimensional octahedron. This is the complement of n copies of K_2 (an edge). It is also the (2n-2)-regular graph on 2n vertices.
gap> OctahedralGraph(3); 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 ] ] )
‣ Octahedron | ( global variable ) |
The 1-skeleton of Plato's octahedron.
gap> Octahedron; 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 ] ] )
‣ Order( G ) | ( attribute ) |
Returns the number of vertices, of the graph G.
gap> Order(Icosahedron); 12
‣ Orientations( G ) | ( operation ) |
Returns the list of all the oriented graphs that are obtained from G by replacing (in every possible way) each edge [x,y] of G by one arrow: either [x,y] or [y,x]. In each of these orientations the loops are removed and existing arrows of G are left untouched.
Note that this operation will use time and memory which is exponential on the number of edges of G.
gap> g:=GraphByWalks([1,1,2,3,1,3,2]:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 6, Adjacencies := [ [ 1, 2, 3 ], [ 3 ], [ 1, 2 ] ] ) gap> Orientations(g); [ Graph( Category := OrientedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2 ], [ ], [ 1, 2 ] ] ), Graph( Category := OrientedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2 ], [ 3 ], [ 1 ] ] ), Graph( Category := OrientedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2, 3 ], [ ], [ 2 ] ] ), Graph( Category := OrientedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2, 3 ], [ 3 ], [ ] ] ) ] gap> Length(Orientations(Octahedron)); 4096
Note that Orientations( G ) returns a list of graphs, each of them in the category OrientedGraphs regardless of the TargetGraphCategory.
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
‣ OrientedGraphs( G ) | ( function ) |
OrientedGraphs is a graph category in YAGS. A graph in this category may contain arrows, but no loops or edges. The parent of this category is LooplessGraphs.
gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 4, Adjacencies := [ [ 1, 2 ], [ 1 ], [ 2 ] ] ) gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ ], [ 2 ] ] )
‣ OutNeigh( G, x ) | ( operation ) |
Returns the list of out-neighbors of x in G.
gap> tt:=CompleteGraph(5:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 5, Size := 10, Adjacencies := [ [ 2, 3, 4, 5 ], [ 3, 4, 5 ], [ 4, 5 ], [ 5 ], [ ] ] ) gap> InNeigh(tt,3); [ 1, 2 ] gap> OutNeigh(tt,3); [ 4, 5 ]
‣ PaleyTournament( prime ) | ( operation ) |
Returns the Paley tournament associated with prime number prime. The prime must be congruent to 3 mod 4. The Paley tournament is the oriented circulant whose jumps are all the squares of the ring ℤ_p.
gap> Filtered([1..30],x -> 0=((x-3) mod 4) and IsPrime(x)); [ 3, 7, 11, 19, 23 ] gap> PaleyTournament(3);PaleyTournament(7);PaleyTournament(11); Graph( Category := OrientedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2 ], [ 3 ], [ 1 ] ] ) Graph( Category := OrientedGraphs, Order := 7, Size := 21, Adjacencies := [ [ 2, 3, 5 ], [ 3, 4, 6 ], [ 4, 5, 7 ], [ 1, 5, 6 ], [ 2, 6, 7 ], [ 1, 3, 7 ], [ 1, 2, 4 ] ] ) Graph( Category := OrientedGraphs, Order := 11, Size := 55, Adjacencies := [ [ 2, 4, 5, 6, 10 ], [ 3, 5, 6, 7, 11 ], [ 1, 4, 6, 7, 8 ], [ 2, 5, 7, 8, 9 ], [ 3, 6, 8, 9, 10 ], [ 4, 7, 9, 10, 11 ], [ 1, 5, 8, 10, 11 ], [ 1, 2, 6, 9, 11 ], [ 1, 2, 3, 7, 10 ], [ 2, 3, 4, 8, 11 ], [ 1, 3, 4, 5, 9 ] ] ) gap> PaleyTournament(5); fail
Note that PaleyTournament( prime ) returns a graph in the category OrientedGraphs regardless of the TargetGraphCategory.
‣ ParachuteGraph | ( global variable ) |
The complement of a ParapluieGraph; The suspension of a 4-path with a pendant vertex attached to the south pole.
gap> ParachuteGraph; Graph( Category := SimpleGraphs, Order := 7, Size := 12, Adjacencies := [ [ 2 ], [ 1, 3, 4, 5, 6 ], [ 2, 4, 7 ], [ 2, 3, 5, 7 ], [ 2, 4, 6, 7 ], [ 2, 5, 7 ], [ 3, 4, 5, 6 ] ] )
‣ ParapluieGraph | ( global variable ) |
A 3-fan graph with a 3-path attached to the universal vertex.
gap> ParapluieGraph; 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 ] ] )
‣ ParedGraph( G ) | ( operation ) |
Returns the pared graph of G. This is the induced subgraph obtained from G by removing its dominated vertices. When there are twin vertices (mutually dominated vertices), exactly one of them survives the paring in each equivalent class of mutually dominated vertices.
gap> g1:=PathGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] ) gap> ParedGraph(g1); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> g2:=PathGraph(2); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> ParedGraph(g2); Graph( Category := SimpleGraphs, Order := 1, Size := 0, Adjacencies := [ [ ] ] )
This operation reports progress at InfoLevel 1 (see B.24-3).
‣ PathGraph( n ) | ( function ) |
Returns the path graph on n vertices.
gap> PathGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] )
‣ PawGraph | ( global variable ) |
The graph on 4 vertices, 4 edges and maximum degree 3: A triangle with a pendant vertex.
gap> PawGraph; Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3, 4 ], [ 2, 4 ], [ 2, 3 ] ] )
‣ PetersenGraph | ( global variable ) |
The 3-regular graph on 10 vertices having girth 5.
gap> PetersenGraph; Graph( Category := SimpleGraphs, Order := 10, Size := 15, Adjacencies := [ [ 2, 5, 6 ], [ 1, 3, 7 ], [ 2, 4, 8 ], [ 3, 5, 9 ], [ 1, 4, 10 ], [ 1, 8, 9 ], [ 2, 9, 10 ], [ 3, 6, 10 ], [ 4, 6, 7 ], [ 5, 7, 8 ] ] )
‣ PowerGraph( G, exp ) | ( operation ) |
Returns the DistanceGraph (B.4-9) of G using [0, 1, ..., exp] as the list of distances. Note that the distance 0 in the list produces loops in the new graph only when the TargetGraphCategory admits loops.
gap> g:=PathGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4 ] ] ) gap> PowerGraph(g,1); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4 ] ] ) gap> PowerGraph(g,1:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 5, Size := 13, Adjacencies := [ [ 1, 2 ], [ 1, 2, 3 ], [ 2, 3, 4 ], [ 3, 4, 5 ], [ 4, 5 ] ] )
‣ PropertyMorphism( G, H, PropList ) | ( operation ) |
Returns the first morphism (in lexicographic order) from G to H satisfying the list of properties PropList.
A number of preprogrammed properties are provided by YAGS, and the user may create additional ones. The properties provided are: CHK_WEAK, CHK_MORPH, CHK_METRIC, CHK_CMPLT, CHK_MONO and CHK_EPI.
If G has n vertices and f:G→ H is a morphism, it is represented as F=[f(1), f(2), ..., f(n)].
gap> g:=CycleGraph(4);;h:=CompleteBipartiteGraph(2,2);; gap> PropList:=[CHK_MORPH];; gap> PropertyMorphism(g,h,PropList); [ 1, 3, 1, 3 ]
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
Extensive information about graph morphisms can be found in Chapter 5.
‣ PropertyMorphisms( G, H, PropList ) | ( operation ) |
Returns all morphisms from G to H satisfying the list of properties PropList.
A number of preprogrammed properties are provided by YAGS, and the user may create additional ones. The properties provided are: CHK_WEAK, CHK_MORPH, CHK_METRIC, CHK_CMPLT, CHK_MONO and CHK_EPI.
If G has n vertices and f:G→ H is a morphism, it is represented as F=[f(1), f(2), ..., f(n)].
gap> g:=CycleGraph(4);;h:=CompleteBipartiteGraph(2,2);; gap> PropList:=[CHK_WEAK,CHK_MONO];; gap> PropertyMorphisms(g,h,PropList); [ [ 1, 3, 2, 4 ], [ 1, 4, 2, 3 ], [ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ], [ 3, 2, 4, 1 ], [ 4, 1, 3, 2 ], [ 4, 2, 3, 1 ] ]
This operation reports progress at InfoLevel 3 (see B.24-3 and Section 6.4).
Extensive information about graph morphisms can be found in Chapter 5.
‣ QtfyIsSimple( G ) | ( attribute ) |
For internal use. Returns a non-negative integer indicating how far is the graph G from being a simple graph. The return value of 0 means the graph that the graph is simple.
‣ QuadraticRingGraph( Rng ) | ( operation ) |
Returns the graph G whose vertices are the elements of Rng such that x is adjacent to y iff x+z^2=y for some z in Rng.
gap> QuadraticRingGraph(ZmodnZ(8)); Graph( Category := SimpleGraphs, Order := 8, Size := 12, Adjacencies := [ [ 2, 5, 8 ], [ 1, 3, 6 ], [ 2, 4, 7 ], [ 3, 5, 8 ], [ 1, 4, 6 ], [ 2, 5, 7 ], [ 3, 6, 8 ], [ 1, 4, 7 ] ] )
‣ QuotientGraph( G, Part ) | ( operation ) |
‣ QuotientGraph( G, L1, L2 ) | ( operation ) |
Returns the quotient graph of graph G given a vertex partition Part, by identifying any two vertices in the same part. The vertices of the quotient graph are the parts in the partition Part two of them being adjacent iff any vertex in one part is adjacent to any vertex in the other part. Singletons may be omitted in Part.
gap> g:=PathGraph(8);; gap> QuotientGraph(g,[[1,5,8],[2],[3],[4],[6],[7]]); Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 4, 5, 6 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ], [ 1, 6 ], [ 1, 5 ] ] ) gap> QuotientGraph(g,[[1,5,8]]); Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 4, 5, 6 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ], [ 1, 6 ], [ 1, 5 ] ] )
In its second form, QuotientGraph identifies each vertex in list L1, with the corresponding vertex in list L2. L1 and L2 must have the same length, but any or both of them may have repetitions.
gap> g:=PathGraph(8);; gap> QuotientGraph(g,[[1,7],[4,8]]); Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 4, 6 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 4, 6 ], [ 1, 5 ] ] ) gap> QuotientGraph(g,[1,4],[7,8]); Graph( Category := SimpleGraphs, Order := 6, Size := 7, Adjacencies := [ [ 2, 4, 6 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3, 5 ], [ 4, 6 ], [ 1, 5 ] ] )
‣ Radius( G ) | ( attribute ) |
Returns the minimal eccentricity among the vertices of the graph G.
gap> Radius(PathGraph(5)); 2
‣ RandomCirculant( n ) | ( operation ) |
‣ RandomCirculant( n, k ) | ( operation ) |
‣ RandomCirculant( n, p ) | ( operation ) |
Returns a circulant on n vertices with its jumps selected randomly. In its third form, each possible jump has probability p of being selected. In its second form, when k is a positive integer, exactly k jumps are selected (provided there are at least k possible jumps to select from). The first form is equivalent to specifying p=1/2. In the ambiguous case when the second parameter is 1, it is interpreted as the value of k.
gap> RandomCirculant(11,2); Graph( Category := SimpleGraphs, Order := 11, Size := 22, Adjacencies := [ [ 5, 6, 7, 8 ], [ 6, 7, 8, 9 ], [ 7, 8, 9, 10 ], [ 8, 9, 10, 11 ], [ 1, 9, 10, 11 ], [ 1, 2, 10, 11 ], [ 1, 2, 3, 11 ], [ 1, 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 3, 4, 5, 6 ], [ 4, 5, 6, 7 ] ] ) gap> RandomCirculant(11,2); Graph( Category := SimpleGraphs, Order := 11, Size := 22, Adjacencies := [ [ 2, 3, 10, 11 ], [ 1, 3, 4, 11 ], [ 1, 2, 4, 5 ], [ 2, 3, 5, 6 ], [ 3, 4, 6, 7 ], [ 4, 5, 7, 8 ], [ 5, 6, 8, 9 ], [ 6, 7, 9, 10 ], [ 7, 8, 10, 11 ], [ 1, 8, 9, 11 ], [ 1, 2, 9, 10 ] ] ) gap> RandomCirculant(11,1/2); Graph( Category := SimpleGraphs, Order := 11, Size := 44, Adjacencies := [ [ 2, 4, 5, 6, 7, 8, 9, 11 ], [ 1, 3, 5, 6, 7, 8, 9, 10 ], [ 2, 4, 6, 7, 8, 9, 10, 11 ], [ 1, 3, 5, 7, 8, 9, 10, 11 ], [ 1, 2, 4, 6, 8, 9, 10, 11 ], [ 1, 2, 3, 5, 7, 9, 10, 11 ], [ 1, 2, 3, 4, 6, 8, 10, 11 ], [ 1, 2, 3, 4, 5, 7, 9, 11 ], [ 1, 2, 3, 4, 5, 6, 8, 10 ], [ 2, 3, 4, 5, 6, 7, 9, 11 ], [ 1, 3, 4, 5, 6, 7, 8, 10 ] ] ) gap> RandomCirculant(11,1/2); Graph( Category := SimpleGraphs, Order := 11, Size := 11, Adjacencies := [ [ 5, 8 ], [ 6, 9 ], [ 7, 10 ], [ 8, 11 ], [ 1, 9 ], [ 2, 10 ], [ 3, 11 ], [ 1, 4 ], [ 2, 5 ], [ 3, 6 ], [ 4, 7 ] ] ) gap> RandomCirculant(11,1/2); Graph( Category := SimpleGraphs, Order := 11, Size := 33, Adjacencies := [ [ 2, 3, 6, 7, 10, 11 ], [ 1, 3, 4, 7, 8, 11 ], [ 1, 2, 4, 5, 8, 9 ], [ 2, 3, 5, 6, 9, 10 ], [ 3, 4, 6, 7, 10, 11 ], [ 1, 4, 5, 7, 8, 11 ], [ 1, 2, 5, 6, 8, 9 ], [ 2, 3, 6, 7, 9, 10 ], [ 3, 4, 7, 8, 10, 11 ], [ 1, 4, 5, 8, 9, 11 ], [ 1, 2, 5, 6, 9, 10 ] ] )
‣ RandomGraph( n, p ) | ( function ) |
‣ RandomGraph( n ) | ( function ) |
Returns a random graph of order n taking the rational p∈ [0,1] as the edge probability.
gap> RandomGraph(5,1/3); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 3, 5 ], [ 1, 5 ], [ 1, 4 ], [ 3 ], [ 1, 2 ] ] ) gap> RandomGraph(5,2/3); Graph( Category := SimpleGraphs, Order := 5, Size := 7, Adjacencies := [ [ 2, 3 ], [ 1, 3, 4, 5 ], [ 1, 2, 4, 5 ], [ 2, 3 ], [ 2, 3 ] ] ) gap> RandomGraph(5,1/2); Graph( Category := SimpleGraphs, Order := 5, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 5 ], [ 1, 2 ], [ 3 ] ] )
If p is omitted, the edge probability is taken to be 1/2.
gap> RandomGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 9, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 5 ], [ 1, 2, 4, 5 ], [ 1, 3, 5 ], [ 1, 2, 3, 4 ] ] ) gap> RandomGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2 ], [ 1, 3, 5 ], [ 2, 4 ], [ 3, 5 ], [ 2, 4 ] ] )
‣ RandomPermutation( n ) | ( operation ) |
Returns a random permutation of the list [1, 2, ... n].
gap> RandomPermutation(12); (1,8,5,6,7,3,9,10,2,11,4)
‣ RandomSubset( Set ) | ( operation ) |
‣ RandomSubset( Set, k ) | ( operation ) |
‣ RandomSubset( Set, p ) | ( operation ) |
Returns a random subset of the set Set. When the positive integer k is provided, the returned subset has k elements (or fail if Set does not have at least k elements). When the probability p is provided, each element of Set has probability p of being selected for inclusion in the returned subset. When k and p are both missing, it is equivalent to specifying p=1/2. In the ambiguous case when the second parameter is 1, it is interpreted as the value of k.
gap> RandomSubset([1..10],5); [ 1, 6, 7, 9, 10 ] gap> RandomSubset([1..10],5); [ 7, 8, 3, 1, 5 ] gap> RandomSubset([1..10],5); [ 6, 7, 9, 3, 1 ] gap> RandomSubset([1..10],5); [ 3, 4, 2, 8, 5 ] gap> RandomSubset([1..10],1/2); [ 2, 4, 5, 6, 7, 8, 9, 10 ] gap> RandomSubset([1..10],1/2); [ 5, 6, 7, 8 ] gap> RandomSubset([1..10],1/2); [ 3, 6 ] gap> RandomSubset([1..10],1/2); [ 4, 5, 6, 7, 8, 10 ]
Even if this operation is intended to be applied to sets, it does not impose this condition on its operand, and can be applied to lists as well.
gap> RandomSubset([1,3,2,2,3,2,1]); [ 2, 1 ] gap> RandomSubset([1,3,2,2,3,2,1]); [ 3, 2, 2, 3, 1 ]
‣ RandomlyPermuted( Obj ) | ( operation ) |
Returns a copy of Obj with the order of its elements permuted randomly. Currently, the operation is implemented for lists and graphs.
gap> RandomlyPermuted([1..9]); [ 8, 7, 1, 9, 4, 2, 5, 6, 3 ] gap> g:=PathGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3 ] ] ) gap> RandomlyPermuted(g); Graph( Category := SimpleGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2, 3 ], [ 1 ], [ 1, 4 ], [ 3 ] ] )
‣ RemoveEdges( G, E ) | ( operation ) |
Returns a new graph created from graph G by removing the edges in list E.
gap> g:=CompleteGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) gap> RemoveEdges(g,[[1,2]]); Graph( Category := SimpleGraphs, Order := 4, Size := 5, Adjacencies := [ [ 3, 4 ], [ 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] ) gap> RemoveEdges(g,[[1,2],[3,4]]); Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 3, 4 ], [ 3, 4 ], [ 1, 2 ], [ 1, 2 ] ] )
‣ RemoveVertices( G, V ) | ( operation ) |
Returns a new graph created from graph G by removing the vertices in list V.
gap> g:=PathGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 4, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 4 ] ] ) gap> RemoveVertices(g,[3]); Graph( Category := SimpleGraphs, Order := 4, Size := 2, Adjacencies := [ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ] ) gap> RemoveVertices(g,[1,3]); Graph( Category := SimpleGraphs, Order := 3, Size := 1, Adjacencies := [ [ ], [ 3 ], [ 2 ] ] )
‣ RGraph | ( global variable ) |
A square with two pendant vertices attached to the same vertex of the square.
gap> RGraph; Graph( Category := SimpleGraphs, Order := 6, Size := 6, Adjacencies := [ [ 2 ], [ 1, 3, 5, 6 ], [ 2, 4 ], [ 3, 5 ], [ 2, 4 ], [ 2 ] ] )
‣ RingGraph( Rng, Elms ) | ( operation ) |
Returns the graph G whose vertices are the elements of the ring Rng such that x is adjacent to y iff x+r=y for some r in Elms.
gap> r:=FiniteField(8);Elements(r); GF(2^3) [ 0*Z(2), Z(2)^0, Z(2^3), Z(2^3)^2, Z(2^3)^3, Z(2^3)^4, Z(2^3)^5, Z(2^3)^6 ] gap> RingGraph(r,[Z(2^3),Z(2^3)^4]); Graph( Category := SimpleGraphs, Order := 8, Size := 8, Adjacencies := [ [ 3, 6 ], [ 5, 7 ], [ 1, 4 ], [ 3, 6 ], [ 2, 8 ], [ 1, 4 ], [ 2, 8 ], [ 5, 7 ] ] )
‣ SetCoordinates( G, Coord ) | ( operation ) |
Sets the coordinates of the vertices of G, which are used to draw G by Draw (B.4-15).
gap> g:=CycleGraph(4);; gap> Coordinates(g); fail gap> SetCoordinates(g,[[-10,-10 ],[-10,20],[20,-10 ], [20,20]]); gap> Coordinates(g); [ [ -10, -10 ], [ -10, 20 ], [ 20, -10 ], [ 20, 20 ] ]
‣ SetDefaultGraphCategory( Catgy ) | ( function ) |
Sets the default graph category to Catgy. The default graph category is used when constructing new graphs when no other graph category is indicated. New graphs are always forced to comply with the TargetGraphCategory, so loops may be removed, and arrows may replaced by edges or vice versa, depending on the category that the new graph belongs to.
The available graph categories are: SimpleGraphs, OrientedGraphs, UndirectedGraphs, LooplessGraphs, and Graphs.
gap> SetDefaultGraphCategory(Graphs); gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]); Graph( Category := Graphs, Order := 3, Size := 4, Adjacencies := [ [ 1, 2 ], [ 1 ], [ 2 ] ] ) gap> SetDefaultGraphCategory(LooplessGraphs); gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]); Graph( Category := LooplessGraphs, Order := 3, Size := 3, Adjacencies := [ [ 2 ], [ 1 ], [ 2 ] ] ) gap> SetDefaultGraphCategory(UndirectedGraphs); gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]); Graph( Category := UndirectedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 1, 2 ], [ 1, 3 ], [ 2 ] ] ) gap> SetDefaultGraphCategory(OrientedGraphs); gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]); Graph( Category := OrientedGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ ], [ 2 ] ] ) gap> SetDefaultGraphCategory(SimpleGraphs); gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] )
‣ SimpleGraphs( G ) | ( function ) |
SimpleGraphs is a graph category in YAGS. A graph in this category may contain edges, but no loops or arrows. This category has two parents: LooplessGraphs and UndirectedGraphs.
gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 4, Adjacencies := [ [ 1, 2 ], [ 1 ], [ 2 ] ] ) gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=SimpleGraphs); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] )
‣ Size( G ) | ( attribute ) |
Returns the number of edges of the graph G. Note that the returned value depends not only on the structure of the graph, but also on the category to which it belongs.
gap> g1:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> g2:=CopyGraph(g1:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 4, Size := 8, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> Size(g1); 4 gap> Size(g2); 8
‣ SnubDisphenoid | ( global variable ) |
The 1-skeleton of the 84th Johnson solid.
gap> SnubDisphenoid; Graph( Category := SimpleGraphs, Order := 8, Size := 18, Adjacencies := [ [ 2, 3, 4, 5, 8 ], [ 1, 3, 6, 7, 8 ], [ 1, 2, 4, 6 ], [ 1, 3, 5, 6 ], [ 1, 4, 6, 7, 8 ], [ 2, 3, 4, 5, 7 ], [ 2, 5, 6, 8 ], [ 1, 2, 5, 7 ] ] )
‣ SpanningForest( G ) | ( operation ) |
Returns the a maximal spanning forest of G. Since the forest is maximal, it is composed of a spanning tree for each connected component of G. In particular, this operation actually returns a spanning tree whenever the graph is connected.
‣ SpanningForestEdges( G ) | ( operation ) |
Returns the edges of a maximal spanning forest of G. Since the forest is maximal, it is composed of a spanning tree for each connected component of G. In particular, this operation actually returns the edges of a spanning tree whenever the graph is connected.
‣ SpikyGraph( n ) | ( function ) |
The spiky graph is constructed as follows: Take a complete graph on n vertices, K_n, and then, for each the n subsets of Vertices(K_n) of order n-1, add an additional vertex which is adjacent precisely to this subset of Vertices(K_n).
gap> SpikyGraph(3); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 2, 5, 6 ], [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] )
‣ SunGraph( n ) | ( function ) |
Returns the n-Sun: A complete graph on n vertices, K_n, with a corona made with a zigzagging 2n-cycle glued to a n-cycle of the K_n.
gap> SunGraph(3); Graph( Category := SimpleGraphs, Order := 6, Size := 9, Adjacencies := [ [ 2, 6 ], [ 1, 3, 4, 6 ], [ 2, 4 ], [ 2, 3, 5, 6 ], [ 4, 6 ], [ 1, 2, 4, 5 ] ] ) gap> SunGraph(4); Graph( Category := SimpleGraphs, Order := 8, Size := 14, Adjacencies := [ [ 2, 8 ], [ 1, 3, 4, 6, 8 ], [ 2, 4 ], [ 2, 3, 5, 6, 8 ], [ 4, 6 ], [ 2, 4, 5, 7, 8 ], [ 6, 8 ], [ 1, 2, 4, 6, 7 ] ] )
‣ Suspension( G ) | ( operation ) |
Returns the suspension of graph G. The suspension of G is the graph obtained from G by adding two new vertices which are adjacent to every vertex of G but not to each other. The new vertices are the first ones in the new graph.
gap> Suspension(CycleGraph(4)); Graph( Category := SimpleGraphs, Order := 6, Size := 12, Adjacencies := [ [ 3, 4, 5, 6 ], [ 3, 4, 5, 6 ], [ 1, 2, 4, 6 ], [ 1, 2, 3, 5 ], [ 1, 2, 4, 6 ], [ 1, 2, 3, 5 ] ] )
‣ TargetGraphCategory( [G, ...] ) | ( function ) |
For internal use. Returns the graph category indicated in the options stack if any, otherwise if the list of graphs provided is not empty, returns the minimal common graph category for the graphs in the list, else returns the default graph category. The partial order (by inclusion) among graph categories is as follows:
Graphs
/ \
UndirectedGraphs LooplessGraphs
\ / \
SimpleGraphs OrientedGraphs
This function is internally called by all graph constructing operations in YAGS to decide the graph category that the newly constructed graph is going to belong. New graphs are always forced to comply with the TargetGraphCategory, so loops may be removed, and arrows may replaced by edges or vice versa, depending on the category that the new graph belongs to.
The options stack is a mechanism provided by GAP to pass implicit parameters and is used by TargetGraphCategory so that the user may indicate the graph category she/he wants for the new graph.
gap> SetDefaultGraphCategory(SimpleGraphs); gap> g1:=CompleteGraph(2); Graph( Category := SimpleGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ 1 ] ] ) gap> g2:=CompleteGraph(2:GraphCategory:=OrientedGraphs); Graph( Category := OrientedGraphs, Order := 2, Size := 1, Adjacencies := [ [ 2 ], [ ] ] ) gap> DisjointUnion(g1,g2); Graph( Category := LooplessGraphs, Order := 4, Size := 3, Adjacencies := [ [ 2 ], [ 1 ], [ 4 ], [ ] ] ) gap> DisjointUnion(g1,g2:GraphCategory:=UndirectedGraphs); Graph( Category := UndirectedGraphs, Order := 4, Size := 2, Adjacencies := [ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ] )
In the previous examples, TargetGraphCategory was called internally exactly once for each new graph constructed with the following parameters:
gap> TargetGraphCategory(); <Category "SimpleGraphs"> gap> TargetGraphCategory(:GraphCategory:=OrientedGraphs); <Category "OrientedGraphs"> gap> TargetGraphCategory([g1,g2]); <Category "LooplessGraphs"> gap> TargetGraphCategory([g1,g2]:GraphCategory:=UndirectedGraphs); <Category "UndirectedGraphs">
‣ Tetrahedron | ( global variable ) |
The 1-skeleton of Plato's tetrahedron.
gap> Tetrahedron; Graph( Category := SimpleGraphs, Order := 4, Size := 6, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4 ], [ 1, 2, 4 ], [ 1, 2, 3 ] ] )
‣ TimeInSeconds( ) | ( operation ) |
Returns the time in seconds since 1970-01-01 00:00:00 UTC as an integer. This is useful to measure execution time. It can also be used to impose time constraints on the execution of algorithms. Note however that the time reported is the wall time, not necessarily the time spent in the process you intend to measure.
gap> TimeInSeconds(); 1415551598 gap> K:=CliqueGraph;;NumCli:=NumberOfCliques;;I:=Icosahedron;; gap> t1:=TimeInSeconds();NumCli(K(K(K(K(I)))));TimeInSeconds()-t1; 1415551608 44644 103
Currently, this operation does not work on MS Windows.
‣ TimesProduct( G, H ) | ( operation ) |
Returns the times product, G×H, of two graphs G and H (also known as the tensor product).
The times product is computed as follows:
For each pair of vertices x ∈ G, y ∈ H we create a vertex (x,y). Given two such vertices (x,y) and (x',y') they are adjacent iff x ∼ x' and y ∼ y'.
gap> g:=PathGraph(3);h:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> gh:=TimesProduct(g,h); Graph( Category := SimpleGraphs, Order := 12, Size := 16, Adjacencies := [ [ 6, 8 ], [ 5, 7 ], [ 6, 8 ], [ 5, 7 ], [ 2, 4, 10, 12 ], [ 1, 3, 9, 11 ], [ 2, 4, 10, 12 ], [ 1, 3, 9, 11 ], [ 6, 8 ], [ 5, 7 ], [ 6, 8 ], [ 5, 7 ] ] ) gap> VertexNames(gh); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ] ]
‣ TorusGraph( n, m ) | ( function ) |
Returns (the underlying graph of) a triangulation of the torus on nm vertices. This graph is constructed using {1,2,..., n}×{1,2,..., m} as the vertex set; two of them being adjacent if their difference belongs to {(1,0),(0,1),(1,1)} module ℤ_n×ℤ_m. Hence, in the category of simple graphs, TorusGraph is a 6-regular graph when n,m≥ 3.
TorusGraph(4,4); Graph( Category := SimpleGraphs, Order := 16, Size := 48, Adjacencies := [ [ 2, 4, 5, 6, 13, 16 ], [ 1, 3, 6, 7, 13, 14 ], [ 2, 4, 7, 8, 14, 15 ], [ 1, 3, 5, 8, 15, 16 ], [ 1, 4, 6, 8, 9, 10 ], [ 1, 2, 5, 7, 10, 11 ], [ 2, 3, 6, 8, 11, 12 ], [ 3, 4, 5, 7, 9, 12 ], [ 5, 8, 10, 12, 13, 14 ], [ 5, 6, 9, 11, 14, 15 ], [ 6, 7, 10, 12, 15, 16 ], [ 7, 8, 9, 11, 13, 16 ], [ 1, 2, 9, 12, 14, 16 ], [ 2, 3, 9, 10, 13, 15 ], [ 3, 4, 10, 11, 14, 16 ], [ 1, 4, 11, 12, 13, 15 ] ] )
When n,m≥ 4, TorusGraph( n, m ) is actually a Whitney triangulation: the (maximal) cliques of the graph are exactly the triangles of the triangulation. The clique behavior of these graphs were extensively studied in [12]. However, this operation constructs the described graph for all n,m ≥ 1.
gap> TorusGraph(2,4); Graph( Category := SimpleGraphs, Order := 8, Size := 20, Adjacencies := [ [ 2, 4, 5, 6, 8 ], [ 1, 3, 5, 6, 7 ], [ 2, 4, 6, 7, 8 ], [ 1, 3, 5, 7, 8 ], [ 1, 2, 4, 6, 8 ], [ 1, 2, 3, 5, 7 ], [ 2, 3, 4, 6, 8 ], [ 1, 3, 4, 5, 7 ] ] ) gap> TorusGraph(2,3); Graph( Category := SimpleGraphs, Order := 6, Size := 15, Adjacencies := [ [ 2, 3, 4, 5, 6 ], [ 1, 3, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ], [ 1, 2, 3, 5, 6 ], [ 1, 2, 3, 4, 6 ], [ 1, 2, 3, 4, 5 ] ] )
Note that in these cases, TorusGraph( n, m ) is not 6-regular nor a Whitney triangulation.
‣ TreeGraph( arity, depth ) | ( operation ) |
‣ TreeGraph( ArityList ) | ( operation ) |
Returns a tree, a connected cycle-free graph. In its second form, the vertices at depth k (the root vertex has depth 1 here) have ArityList[k] children. In its first form, all vertices, but the leaves, have arity children and the depth of the leaves is depth+1.
gap> TreeGraph(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> TreeGraph([3,2,2]); Graph( Category := SimpleGraphs, Order := 22, Size := 21, Adjacencies := [ [ 2, 3, 4 ], [ 1, 5, 6 ], [ 1, 7, 8 ], [ 1, 9, 10 ], [ 2, 11, 12 ], [ 2, 13, 14 ], [ 3, 15, 16 ], [ 3, 17, 18 ], [ 4, 19, 20 ], [ 4, 21, 22 ], [ 5 ], [ 5 ], [ 6 ], [ 6 ], [ 7 ], [ 7 ], [ 8 ], [ 8 ], [ 9 ], [ 9 ], [ 10 ], [ 10 ] ] )
‣ TrivialGraph | ( global variable ) |
The one vertex graph.
gap> TrivialGraph; Graph( Category := SimpleGraphs, Order := 1, Size := 0, Adjacencies := [ [ ] ] )
‣ UFFind( UFS, x ) | ( function ) |
For internal use. Implements the find operation on the union-find structure.
‣ UFUnite( UFS, x, y ) | ( function ) |
For internal use. Implements the unite operation on the union-find structure.
‣ UndirectedGraphs( G ) | ( function ) |
UndirectedGraphs is a graph category in YAGS. A graph in this category may contain edges and loops, but no arrows. The parent of this category is Graphs.
gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=Graphs); Graph( Category := Graphs, Order := 3, Size := 4, Adjacencies := [ [ 1, 2 ], [ 1 ], [ 2 ] ] ) gap> GraphByWalks([1,1],[1,2],[2,1],[3,2]:GraphCategory:=UndirectedGraphs); Graph( Category := UndirectedGraphs, Order := 3, Size := 3, Adjacencies := [ [ 1, 2 ], [ 1, 3 ], [ 2 ] ] )
‣ UnitsRingGraph( Rng ) | ( operation ) |
Returns the graph G whose vertices are the elements of Rng such that x is adjacent to y iff x+z=y for some unit z of Rng.
gap> UnitsRingGraph(ZmodnZ(8)); Graph( Category := SimpleGraphs, Order := 8, Size := 16, Adjacencies := [ [ 2, 4, 6, 8 ], [ 1, 3, 5, 7 ], [ 2, 4, 6, 8 ], [ 1, 3, 5, 7 ], [ 2, 4, 6, 8 ], [ 1, 3, 5, 7 ], [ 2, 4, 6, 8 ], [ 1, 3, 5, 7 ] ] )
‣ VertexDegree( G, x ) | ( operation ) |
Returns the degree of vertex x in Graph G.
gap> g:=PathGraph(3); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) gap> VertexDegree(g,1); 1 gap> VertexDegree(g,2); 2
‣ VertexDegrees( G ) | ( operation ) |
Returns the list of degrees of the vertices in graph G.
gap> g:=GemGraph; Graph( Category := SimpleGraphs, Order := 5, Size := 7, Adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 4 ] ] ) gap> VertexDegrees(g); [ 4, 2, 3, 3, 2 ]
‣ VertexNames( G ) | ( attribute ) |
Return the list of names of the vertices of G. The vertices of a graph in YAGS are always {1,2, ...,Order(G)}, but depending on how the graph was constructed, its vertices may have also some names, that help us identify the origin of the vertices. YAGS will always try to store meaningful names for the vertices. For example, in the case of the LineGraph, the vertex names of the new graph are the edges of the old graph.
gap> g:=LineGraph(DiamondGraph); Graph( Category := SimpleGraphs, Order := 5, Size := 8, Adjacencies := [ [ 2, 3, 4 ], [ 1, 3, 4, 5 ], [ 1, 2, 5 ], [ 1, 2, 5 ], [ 2, 3, 4 ] ] ) gap> VertexNames(g); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ] ] gap> Edges(DiamondGraph); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ] ]
‣ Vertices( G ) | ( operation ) |
Returns the list [1..Order( G )].
gap> Vertices(Icosahedron); [ 1 .. 12 ]
‣ WheelGraph( n ) | ( operation ) |
‣ WheelGraph( n, r ) | ( operation ) |
In its first form WheelGraph returns the wheel graph on n+1 vertices. This is the cone of a cycle: a central vertex adjacent to all the vertices of an n-cycle.
gap> WheelGraph(5); Graph( Category := SimpleGraphs, Order := 6, Size := 10, Adjacencies := [ [ 2, 3, 4, 5, 6 ], [ 1, 3, 6 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 4, 6 ], [ 1, 2, 5 ] ] )
In its second form, WheelGraph returns returns the wheel graph, but adding r-1 layers, each layer is a new n-cycle joined to the previous layer by a zigzagging 2n-cycle. This graph is a triangulation of the disk.
gap> WheelGraph(5,2); Graph( Category := SimpleGraphs, Order := 11, Size := 25, Adjacencies := [ [ 2, 3, 4, 5, 6 ], [ 1, 3, 6, 7, 8 ], [ 1, 2, 4, 8, 9 ], [ 1, 3, 5, 9, 10 ], [ 1, 4, 6, 10, 11 ], [ 1, 2, 5, 7, 11 ], [ 2, 6, 8, 11 ], [ 2, 3, 7, 9 ], [ 3, 4, 8, 10 ], [ 4, 5, 9, 11 ], [ 5, 6, 7, 10 ] ] ) gap> WheelGraph(5,3); Graph( Category := SimpleGraphs, Order := 16, Size := 40, Adjacencies := [ [ 2, 3, 4, 5, 6 ], [ 1, 3, 6, 7, 8 ], [ 1, 2, 4, 8, 9 ], [ 1, 3, 5, 9, 10 ], [ 1, 4, 6, 10, 11 ], [ 1, 2, 5, 7, 11 ], [ 2, 6, 8, 11, 12, 13 ], [ 2, 3, 7, 9, 13, 14 ], [ 3, 4, 8, 10, 14, 15 ], [ 4, 5, 9, 11, 15, 16 ], [ 5, 6, 7, 10, 12, 16 ], [ 7, 11, 13, 16 ], [ 7, 8, 12, 14 ], [ 8, 9, 13, 15 ], [ 9, 10, 14, 16 ], [ 10, 11, 12, 15 ] ] )
‣ YAGSExec( ProgName, InString ) | ( operation ) |
For internal use. Calls external program ProgName located in directory YAGS-DIR/bin/ feeding it with InString as input and returning the output of the external program as a string. fail is returned if the program could not be located.
gap> YAGSExec("time",""); "1415551127\n" gap> YAGSExec("nauty","l=0$=1dacn=5 g1,2,3. xbzq"); "(4,5)\n(2,3)\n[2,3,4,5,1]\n[\"cb0c\",\"484f264\",\"b0e19f1\"]\n"
This operation have not been tested on MS Windows.
‣ YAGSInfo | ( global variable ) |
A global record where much YAGS-related information is stored. This is intended for internal use, and much of this information is undocumented, but some of the data stored here could possibly be useful for advanced users.
However, storing user information in this record and/or changing the values of the stored information is discouraged and may produce unpredictable results and an unstable system.
gap> YAGSInfo; rec( Arch := 1, DataDirectory := "/opt/gap4r8/pkg/yags/data", Directory := "/opt/gap4r8/pkg/yags", Draw := rec( opts := [ ], prog := "/opt/gap4r8/pkg/yags/bin/draw/application.linux64/draw" ), InfoClass := YAGSInfoClass, InfoOutput := "*stdout*", Version := "0.0.4", graph6 := rec( BinListToNum := function( L ) ... end, BinListToNumList := function( L ) ... end, HararyList := [ [ 1, 0, 1 ], [ 2, 0, 1 ], [ 2, 1, 1 ], [ 3, 0, 1 ], [ 3, 1, 1 ], [ 3, 2, 1 ], [ 3, 3, 1 ], [ 4, 0, 1 ], [ 4, 1, 1 ], [ 4, 2, 1 ], [ 4, 3, 3 ], [ 4, 2, 2 ], [ 4, 3, 1 ], [ 4, 3, 2 ], [ 4, 4, 1 ], --- many more lines here --- [ 6, 13, 1 ], [ 6, 11, 7 ], [ 6, 11, 9 ], [ 6, 11, 8 ], [ 6, 12, 4 ], [ 6, 12, 5 ], [ 6, 13, 2 ], [ 6, 14, 1 ], [ 6, 15, 1 ] ], McKayN := function( n ) ... end, McKayR := function( L ) ... end, NumListToString := function( L ) ... end, NumToBinList := function( n ) ... end, PadLeftnSplitList6 := function( L ) ... end, PadRightnSplitList6 := function( L ) ... end, StringToBinList := function( Str ) ... end ) )
‣ YAGSInfo.InfoClass | ( global variable ) |
YAGS uses the Reference: InfoLevel mechanism in some algorithms for progress reporting. This is useful in algorithms that may take a lot of time to finish, so the user is informed about how much work is already done and how much work remains to be done; this way, the user can decide whether to wait for the response or not.
Enabling and disabling progress reporting is done by changing the InfoLevel of YAGSInfo.InfoClass to the appropriate level. The default InfoLevel for YAGSInfo.InfoClass is 0, and 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)); [ ]
The algorithms that report progress at InfoLevel 1 are ParedGraph (B.16-4) and Cliques (B.3-7), and also the algorithms that use those, namely: CliqueGraph (B.3-5), CliqueNumber (B.3-6), CompletelyParedGraph (B.3-12), IsCliqueGated (B.9-9) and NumberOfCliques (B.14-3).
The algorithms that report at InfoLevel 3 are Backtrack (B.2-1) and the algorithms that use that one, namely: BacktrackBag (B.2-2), CompletesOfGivenOrder (B.3-14), Orientations (B.15-4) and all the morphism-related operations in Chapter 5. The meaning of the progress strings reported in all these functions are described in Section 6.4.
The output of the progress info may be redirected to a file or character device by setting the variable YAGSInfo.InfoOutput (B.24-4) accordingly.
‣ YAGSInfo.InfoOutput | ( global variable ) |
The output of the progress info reported by some algorithms (see YAGSInfo.InfoClass (B.24-3)) may be redirected to a file by setting the variable YAGSInfo.InfoOutput accordingly. The default value of YAGSInfo.InfoOutput:="*stdout*" means the console; but setting the name of a file as the value of YAGSInfo.InfoOutput sends the output to that file. In Unix-like systems, we can also use the name of a character device (like "/dev/null", "/dev/tty" or "/dev/pts/1") to redirect the progress info output to that device.
‣ YAGSPositionsTrueBlist( Blist ) | ( function ) |
For internal use. The same as ListBlist([1..Length(Blist)],Blist);
gap> YAGSPositionsTrueBlist([false, true, true, false, true]); [ 2, 3, 5 ]
generated by GAPDoc2HTML