In **Digraphs**, a *clique* of a digraph is a set of mutually adjacent vertices of the digraph, and an *independent set* is a set of mutually non-adjacent vertices of the digraph. A *maximal clique* is a clique which is not properly contained in another clique, and a *maximal independent set* is an independent set which is not properly contained in another independent set. Using this definition in **Digraphs**, cliques and independent sets are both permitted, but not required, to contain vertices at which there is a loop. Another name for a clique is a *complete subgraph*.

**Digraphs** provides extensive functionality for computing cliques and independent sets of a digraph, whether maximal or not. The fundamental algorithm used in most of the methods in **Digraphs** to calculate cliques and independent sets is a version of the Bron-Kerbosch algorithm. Calculating the cliques and independent sets of a digraph is a well-known and hard problem, and searching for cliques or independent sets in a digraph can be very length, even for a digraph with a small number of vertices. **Digraphs** uses several strategies to increase the performance of these calculations.

From the definition of cliques and independent sets, it follows that the presence of loops and multiple edges in a digraph is irrelevant to the existence of cliques and independent sets in the digraph. See `DigraphHasLoops`

(6.1-1) and `IsMultiDigraph`

(6.1-8) for more information about these properties. Therefore given a digraph `digraph`, the cliques and independent sets of `digraph` are equal to the cliques and independent sets of the digraph:

`DigraphRemoveLoops(DigraphRemoveAllMultipleEdges(`

`digraph``))`

.

See `DigraphRemoveLoops`

(3.3-22) and `DigraphRemoveAllMultipleEdges`

(3.3-23) for more information about these attributes. Furthermore, the cliques of this digraph are equal to the cliques of the digraph formed by removing any edge `[u,v]`

for which the corresponding reverse edge `[v,u]`

is not present. Therefore, overall, the cliques of `digraph` are equal to the cliques of the symmetric digraph:

`MaximalSymmetricSubdigraphWithoutLoops(`

`digraph``)`

.

See `MaximalSymmetricSubdigraphWithoutLoops`

(3.3-4) for more information about this attribute. The `AutomorphismGroup`

(7.2-1) of this symmetric digraph contains the automorphism group of `digraph` as a subgroup. By performing the search for maximal cliques with the help of this larger automorphism group to reduce the search space, the computation time may be reduced. The functions and attributes which return representatives of cliques of `digraph` will return orbit representatives of cliques under the action of the automorphism group of the *maximal symmetric subdigraph without loops* on sets of vertices.

The independent sets of a digraph are equal to the independent sets of the `DigraphSymmetricClosure`

(3.3-9). Therefore, overall, the independent sets of `digraph` are equal to the independent sets of the symmetric digraph:

`DigraphSymmetricClosure(DigraphRemoveLoops(DigraphRemoveAllMultipleEdges(`

`digraph``)))`

.

Again, the automorphism group of this symmetric digraph contains the automorphism group of `digraph`. Since a search for independent sets is equal to a search for cliques in the `DigraphDual`

(3.3-8), the methods used in **Digraphs** usually transform a search for independent sets into a search for cliques, as described above. The functions and attributes which return representatives of independent sets of `digraph` will return orbit representatives of independent sets under the action of the automorphism group of the *symmetric closure* of the digraph formed by removing loops and multiple edges.

Please note that in **Digraphs**, cliques and indepedent sets are not required to be maximal. Some authors use the word clique to mean *maximal* clique, and some authors use the phrase independent set to mean *maximal* independent set, but please note that **Digraphs** does not use this definition.

`‣ IsClique` ( digraph, l ) | ( operation ) |

`‣ IsMaximalClique` ( digraph, l ) | ( operation ) |

Returns: `true`

or `false`

.

If `digraph` is a digraph and `l` is a duplicate-free list of vertices of `digraph`, then `IsClique(`

`digraph``,`

`l``)`

returns `true`

if `l` is a *clique* of `digraph` and `false`

if it is not. Similarly, `IsMaximalClique(`

`digraph``,`

`l``)`

returns `true`

if `l` is a *maximal clique* of `digraph` and `false`

if it is not.

A *clique* of a digraph is a set of mutually adjacent vertices of the digraph. A *maximal clique* is a clique which is not properly contained in another clique. A clique is permitted, but not required, to contain vertices at which there is a loop.

gap> gr := CompleteDigraph(4);; gap> IsClique(gr, [1, 3, 2]); true gap> IsMaximalClique(gr, [1, 3, 2]); false gap> IsMaximalClique(gr, DigraphVertices(gr)); true gap> gr := Digraph([[1, 2, 4, 4], [1, 3, 4], [2, 1], [1, 2]]); <multidigraph with 4 vertices, 11 edges> gap> IsClique(gr, [2, 3, 4]); false gap> IsMaximalClique(gr, [1, 2, 4]); true

`‣ CliquesFinder` ( digraph, hook, user_param, limit, include, exclude, max, size, reps ) | ( function ) |

Returns: The argument `user_param`.

This function finds cliques of the digraph `digraph` subject to the conditions imposed by the other arguments as described below. Note that a clique is represented by a list of the vertices which it contains.

Let `G`

denote the automorphism group of the maximal symmetric subdigraph of `digraph` without loops (see `AutomorphismGroup`

(7.2-1) and `MaximalSymmetricSubdigraphWithoutLoops`

(3.3-4)).

`hook`This argument should be a function or

`fail`

.If

`hook`is a function, then it should have two arguments`user_param`(see below) and a clique`c`

. The function

is called every time a new clique`hook`(`user_param`, c)`c`

is found by`CliquesFinder`

.If

`hook`is`fail`

, then a default function is used which simply adds every new clique found by`CliquesFinder`

to`user_param`, which must be a list in this case.`user_param`If

`hook`is a function, then`user_param`can be any**GAP**object. The object`user_param`is used as the first argument for the function`hook`. For example,`user_param`might be a list, and

might add the size of the clique`hook`(`user_param`, c)`c`

to the list`user_param`.If the value of

`hook`is`fail`

, then the value of`user_param`must be a list.`limit`This argument should be a positive integer or

`infinity`

.`CliquesFinder`

will return after it has found`limit`cliques or the search is complete.`include`and`exclude`These arguments should each be a (possibly empty) duplicate-free list of vertices of

`digraph`(i.e. positive integers less than the number of vertices of`digraph`).`CliquesFinder`

will only look for cliques containing all of the vertices in`include`and containing none of the vertices in`exclude`.Note that the search may be much more efficient if each of these lists is invariant under the action of

`G`

on sets of vertices.`max`This argument should be

`true`

or`false`

. If`max`is true then`CliquesFinder`

will only search for*maximal*cliques. If`max`

is`false`

then non-maximal cliques may be found.`size`This argument should be

`fail`

or a positive integer. If`size`is a positive integer then`CliquesFinder`

will only search for cliques which contain precisely`size`vertices. If`size`is`fail`

then cliques of any size may be found.`reps`This argument should be

`true`

or`false`

.If

`reps`is`true`

then the arguments`include`and`exclude`are each required to be invariant under the action of`G`

on sets of vertices. In this case,`CliquesFinder`

will find representatives of the orbits of the desired cliques under the action of`G`

,*although representatives may be returned which are in the same orbit*. If`reps`is false then`CliquesFinder`

will not take this into consideration.For a digraph such that

`G`

is non-trivial, the search for clique representatives can be much more efficient than the search for all cliques.

This function uses a version of the Bron-Kerbosch algorithm.

gap> gr := CompleteDigraph(5); <digraph with 5 vertices, 20 edges> gap> user_param := [];; gap> f := function(a, b) # Calculate size of clique > AddSet(user_param, Size(b)); > end;; gap> CliquesFinder(gr, f, user_param, infinity, [], [], false, fail, > true); [ 1, 2, 3, 4, 5 ] gap> CliquesFinder(gr, fail, [], 5, [2, 4], [3], false, fail, false); [ [ 2, 4 ], [ 1, 2, 4 ], [ 2, 4, 5 ], [ 1, 2, 4, 5 ] ] gap> CliquesFinder(gr, fail, [], 2, [2, 4], [3], false, fail, false); [ [ 2, 4 ], [ 1, 2, 4 ] ] gap> CliquesFinder(gr, fail, [], infinity, [], [], true, 5, false); [ [ 1, 2, 3, 4, 5 ] ] gap> CliquesFinder(gr, fail, [], infinity, [1, 3], [], false, 3, false); [ [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 3, 5 ] ] gap> CliquesFinder(gr, fail, [], infinity, [1, 3], [], true, 3, false); [ ]

`‣ DigraphClique` ( digraph[, include[, exclude[, size]]] ) | ( function ) |

`‣ DigraphMaximalClique` ( digraph[, include[, exclude[, size]]] ) | ( function ) |

Returns: A list of positive integers, or `fail`

.

If `digraph` is a digraph, then these functions returns a clique of `digraph` if one exists which satisfies the arguments, else it returns `fail`

. A clique is defined by the set of vertices which it contains; see `IsClique`

(8.1-1) and `IsMaximalClique`

(8.1-1).

The optional arguments `include` and `exclude` must each be a (possibly empty) duplicate-free list of vertices of `digraph`, and the optional argument `size` must be a positive integer. By default, `include` and `exclude` are empty. These functions will search for a clique of `digraph` which includes the vertices of `include` and which does not include any vertices in `exclude`; if the argument `size` is supplied, then additionally the clique will be required to contain precisely `size` vertices.

If `include` is not a clique, then these functions return `fail`

. Otherwise, the functions behave in the following way, depending on the number of arguments:

**One or two arguments**If one or two arguments are supplied, then

`DigraphClique`

and`DigraphMaximalClique`

greedily enlarge the clique`include`until it can not continue. The result is guaranteed to be a maximal clique. This may or may not return an answer more quickly than using`DigraphMaximalCliques`

(8.1-4). with a limit of 1.**Three arguments**If three arguments are supplied, then

`DigraphClique`

greedily enlarges the clique`include`until it can not continue, although this clique may not be maximal.Given three arguments,

`DigraphMaximalClique`

returns the maximal clique returned by`DigraphMaximalCliques(`

`digraph``,`

`include``,`

`exclude``, 1)`

if one exists, else`fail`

.**Four arguments**If four arguments are supplied, then

`DigraphClique`

returns the clique returned by`DigraphCliques(`

`digraph``,`

`include``,`

`exclude``, 1,`

`size``)`

if one exists, else`fail`

. This clique may not be maximal.Given four arguments,

`DigraphMaximalClique`

returns the maximal clique returned by`DigraphMaximalCliques(`

`digraph``,`

`include``,`

`exclude``, 1,`

`size``)`

if one exists, else`fail`

.

gap> gr := Digraph([[2, 3, 4], [1, 3], [1, 2], [1, 5], []]); <digraph with 5 vertices, 9 edges> gap> IsSymmetricDigraph(gr); false gap> DigraphClique(gr); [ 5 ] gap> DigraphMaximalClique(gr); [ 5 ] gap> DigraphClique(gr, [1, 2]); [ 1, 2, 3 ] gap> DigraphMaximalClique(gr, [1, 3]); [ 1, 3, 2 ] gap> DigraphClique(gr, [1], [2]); [ 1, 4 ] gap> DigraphMaximalClique(gr, [1], [3, 4]); fail gap> DigraphClique(gr, [1, 5]); fail gap> DigraphClique(gr, [], [], 2); [ 1, 2 ]

`‣ DigraphMaximalCliques` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphMaximalCliquesReps` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphCliques` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphCliquesReps` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphMaximalCliquesAttr` ( digraph ) | ( attribute ) |

`‣ DigraphMaximalCliquesRepsAttr` ( digraph ) | ( attribute ) |

Returns: A list of lists of positive integers.

If `digraph` is digraph, then these functions and attributes use `CliquesFinder`

(8.1-2) to return cliques of `digraph`. A clique is defined by the set of vertices which it contains; see `IsClique`

(8.1-1) and `IsMaximalClique`

(8.1-1).

The optional arguments `include` and `exclude` must each be a (possibly empty) list of vertices of `digraph`, the optional argument `limit` must be either a positive integer or `infinity`

, and the optional argument `size` must be a positive integer. If not specified, then `include` and `exclude` are empty lists, and `limit` is `infinity`

.

The functions will return as many suitable cliques as possible, up to the number `limit`. These functions will find cliques which contain all of the vertices of `include` and which do not contain any of the vertices of `exclude`. The argument `size` restricts the search to those cliques which contain precisely `size` vertices. If the function or attribute has `Maximal`

in its name, then only maximal cliques will be returned; otherwise non-maximal cliques may be returned.

Let `G`

denote the automorphism group of maximal symmetric subdigraph of `digraph` without loops (see `AutomorphismGroup`

(7.2-1) and `MaximalSymmetricSubdigraphWithoutLoops`

(3.3-4)).

**Distinct cliques**`DigraphMaximalCliques`

and`DigraphCliques`

each return a duplicate-free list of at most`limit`cliques of`digraph`which satisfy the arguments.The computation may be significantly faster if

`include`and`exclude`are invariant under the action of`G`

on sets of vertices.**Orbit representatives of cliques**To use

`DigraphMaximalCliquesReps`

or`DigraphCliquesReps`

, the arguments`include`and`exclude`must each be invariant under the action of`G`

on sets of vertices.If this is the case, then

`DigraphMaximalCliquesReps`

and`DigraphCliquesReps`

each return a duplicate-free list of at most`limit`orbits representatives (under the action of`G`

on sets vertices) of cliques of`digraph`which satisfy the arguments.The representatives are not guaranteed to be in distinct orbits. However, if

`lim`is not specified, or fewer than`lim`results are returned, then there will be at least one representative from each orbit of maximal cliques.

gap> gr := Digraph([ > [2, 3], [1, 3], [1, 2, 4], [3, 5, 6], [4, 6], [4, 5]]); <digraph with 6 vertices, 14 edges> gap> IsSymmetricDigraph(gr); true gap> G := AutomorphismGroup(gr); Group([ (5,6), (1,2), (1,5)(2,6)(3,4) ]) gap> DigraphMaximalCliques(gr); [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 3, 4 ] ] gap> DigraphMaximalCliquesReps(gr); [ [ 1, 2, 3 ], [ 3, 4 ] ] gap> Orbit(G, [1, 2, 3], OnSets); [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] gap> Orbit(G, [3, 4], OnSets); [ [ 3, 4 ] ] gap> DigraphMaximalCliquesReps(gr, [3, 4], [], 1); [ [ 3, 4 ] ] gap> DigraphMaximalCliques(gr, [1, 2], [5, 6], 1, 2); [ ] gap> DigraphCliques(gr, [1], [5, 6], infinity, 2); [ [ 1, 2 ], [ 1, 3 ] ]

`‣ CliqueNumber` ( digraph ) | ( attribute ) |

Returns: A non-negative integer.

If `digraph` is a digraph, then `CliqueNumber(`

returns the largest integer `digraph`)`n`

such that `digraph` contains a clique with `n`

vertices as an induced subdigraph.

A *clique* of a digraph is a set of mutually adjacent vertices of the digraph. Loops and multiple edges are ignored for the purpose of determining the clique number of a digraph.

gap> gr := CompleteDigraph(4);; gap> CliqueNumber(gr); 4 gap> gr := Digraph([[1, 2, 4, 4], [1, 3, 4], [2, 1], [1, 2]]); <multidigraph with 4 vertices, 11 edges> gap> CliqueNumber(gr); 3

`‣ IsIndependentSet` ( digraph, l ) | ( operation ) |

`‣ IsMaximalIndependentSet` ( digraph, l ) | ( operation ) |

Returns: `true`

or `false`

.

If `digraph` is a digraph and `l` is a duplicate-free list of vertices of `digraph`, then `IsIndependentSet(`

`digraph``,`

`l``)`

returns `true`

if `l` is an *independent set* of `digraph` and `false`

if it is not. Similarly, `IsMaximalIndependentSet(`

`digraph``,`

`l``)`

returns `true`

if `l` is a *maximal independent set* of `digraph` and `false`

if it is not.

An *independent set* of a digraph is a set of mutually non-adjacent vertices of the digraph. A *maximal independent set* is an independent set which is not properly contained in another independent set. An independent set is permitted, but not required, to contain vertices at which there is a loop.

gap> gr := CycleDigraph(4);; gap> IsIndependentSet(gr, [1]); true gap> IsMaximalIndependentSet(gr, [1]); false gap> IsIndependentSet(gr, [1, 4, 3]); false gap> IsIndependentSet(gr, [2, 4]); true gap> IsMaximalIndependentSet(gr, [2, 4]); true

`‣ DigraphIndependentSet` ( digraph[, include[, exclude[, size]]] ) | ( function ) |

`‣ DigraphMaximalIndependentSet` ( digraph[, include[, exclude[, size]]] ) | ( function ) |

Returns: A lists of positive integers, or `fail`

.

If `digraph` is a digraph, then these functions returns a independent set of `digraph` if one exists which satisfies the arguments, else it returns `fail`

. A independent set is defined by the set of vertices which it contains; see `IsIndependentSet`

(8.2-1) and `IsMaximalIndependentSet`

(8.2-1).

The optional arguments `include` and `exclude` must each be a (possibly empty) duplicate-free list of vertices of `digraph`, and the optional argument `size` must be a positive integer. By default, `include` and `exclude` are empty. These functions will search for a independent set of `digraph` which includes the vertices of `include` and which does not include any vertices in `exclude`; if the argument `size` is supplied, then additionally the independent set will be required to contain precisely `size` vertices.

If `include` is not a independent set, then these functions return `fail`

. Otherwise, the functions behave in the following way, depending on the number of arguments:

**One or two arguments**If one or two arguments are supplied, then

`DigraphIndependentSet`

and`DigraphMaximalIndependentSet`

greedily enlarge the independent set`include`until it can not continue. The result is guaranteed to be a maximal independent set. This may or may not return an answer more quickly than using`DigraphMaximalIndependentSets`

(8.2-3). with a limit of 1.**Three arguments**If three arguments are supplied, then

`DigraphIndependentSet`

greedily enlarges the independent set`include`until it can not continue, although this independent set may not be maximal.Given three arguments,

`DigraphMaximalIndependentSet`

returns the maximal independent set returned by`DigraphMaximalIndependentSets(`

`digraph``,`

`include``,`

`exclude``, 1)`

if one exists, else`fail`

.**Four arguments**If four arguments are supplied, then

`DigraphIndependentSet`

returns the independent set returned by`DigraphIndependentSets(`

`digraph``,`

`include``,`

`exclude``, 1,`

`size``)`

if one exists, else`fail`

. This independent set may not be maximal.Given four arguments,

`DigraphMaximalIndependentSet`

returns the maximal independent set returned by`DigraphMaximalIndependentSets(`

`digraph``,`

`include``,`

`exclude``, 1,`

`size``)`

if one exists, else`fail`

.

gap> gr := ChainDigraph(6); <digraph with 6 vertices, 5 edges> gap> DigraphIndependentSet(gr); [ 6, 4, 2 ] gap> DigraphMaximalIndependentSet(gr); [ 6, 4, 2 ] gap> DigraphIndependentSet(gr, [2, 4]); [ 2, 4, 6 ] gap> DigraphMaximalIndependentSet(gr, [1, 3]); [ 1, 3, 6 ] gap> DigraphIndependentSet(gr, [2, 4], [6]); [ 2, 4 ] gap> DigraphMaximalIndependentSet(gr, [2, 4], [6]); fail gap> DigraphIndependentSet(gr, [1], [], 2); [ 1, 3 ] gap> DigraphMaximalIndependentSet(gr, [1], [], 2); fail gap> DigraphMaximalIndependentSet(gr, [1], [], 3); [ 1, 3, 5 ]

`‣ DigraphMaximalIndependentSets` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphMaximalIndependentSetsReps` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphIndependentSets` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphIndependentSetsReps` ( digraph[, include[, exclude[, limit[, size]]]] ) | ( function ) |

`‣ DigraphMaximalIndependentSetsAttr` ( digraph ) | ( attribute ) |

`‣ DigraphMaximalIndependentSetsRepsAttr` ( digraph ) | ( attribute ) |

Returns: A list of lists of positive integers.

If `digraph` is digraph, then these functions and attributes use `CliquesFinder`

(8.1-2) to return independent sets of `digraph`. An independent set is defined by the set of vertices which it contains; see `IsMaximalIndependentSet`

(8.2-1) and `IsIndependentSet`

(8.2-1).

The optional arguments `include` and `exclude` must each be a (possibly empty) list of vertices of `digraph`, the optional argument `limit` must be either a positive integer or `infinity`

, and the optional argument `size` must be a positive integer. If not specified, then `include` and `exclude` are empty lists, and `limit` is `infinity`

.

The functions will return as many suitable independent sets as possible, up to the number `limit`. These functions will find independent sets which contain all of the vertices of `include` and which do not contain any of the vertices of `exclude` The argument `size` restricts the search to those cliques which contain precisely `size` vertices. If the function or attribute has `Maximal`

in its name, then only maximal independent sets will be returned; otherwise non-maximal independent sets may be returned.

Let `G`

denote the `AutomorphismGroup`

(7.2-1) of the `DigraphSymmetricClosure`

(3.3-9) of the digraph formed from `digraph` by removing loops and ignoring the multiplicity of edges.

**Distinct independent sets**`DigraphMaximalIndependentSets`

and`DigraphIndependentSets`

each return a duplicate-free list of at most`limit`independent sets of`digraph`which satisfy the arguments.The computation may be significantly faster if

`include`and`exclude`are invariant under the action of`G`

on sets of vertices.**Representatives of distinct orbits of independent sets**To use

`DigraphMaximalIndependentSetsReps`

or`DigraphIndependentSetsReps`

, the arguments`include`and`exclude`must each be invariant under the action of`G`

on sets of vertices.If this is the case, then

`DigraphMaximalIndependentSetsReps`

and`DigraphIndependentSetsReps`

each return a list of at most`limit`orbits representatives (under the action of`G`

on sets of vertices) of independent sets of`digraph`which satisfy the arguments.The representatives are not guaranteed to be in distinct orbits. However, if

`lim`is not specified, or fewer than`lim`results are returned, then there will be at least one representative from each orbit of maximal independent sets.

gap> gr := CycleDigraph(5); <digraph with 5 vertices, 5 edges> gap> DigraphMaximalIndependentSetsReps(gr); [ [ 1, 3 ] ] gap> DigraphIndependentSetsReps(gr); [ [ 1 ], [ 1, 3 ] ] gap> DigraphMaximalIndependentSets(gr); [ [ 1, 3 ], [ 1, 4 ], [ 2, 5 ], [ 2, 4 ], [ 3, 5 ] ] gap> DigraphMaximalIndependentSets(gr, [1]); [ [ 1, 3 ], [ 1, 4 ] ] gap> DigraphIndependentSets(gr, [], [4, 5]); [ [ 1 ], [ 2 ], [ 3 ], [ 1, 3 ] ] gap> DigraphIndependentSets(gr, [], [4, 5], 1, 2); [ [ 1, 3 ] ]

generated by GAPDoc2HTML