Cliques, independent sets and colouring

Type of the function that receives cliques from the callback searches.

typedef og_error_t og_clique_handler_t(
    const og_vector_int_t *clique,
    void *arg
);

clique holds the vertex ids of one clique. It belongs to the search and is only valid during the call. arg is the pointer given to the search function. The return value steers the search: OG_SUCCESS continues, OG_STOP ends it normally, any other code aborts it and is returned by the search function.

Parameters

• clique The clique found (read only, valid during the call).
• arg The extra pointer passed to the search function.

Returns

OG_SUCCESS to continue, OG_STOP to end the search normally, or an error code to abort it.

Checked

Type; tested through cliques_callback and maximal_cliques_callback.

C name

og_clique_handler_t

In notebooks

Og.CliqueHandler

igraph 1.0

igraph_clique_handler_t

See also

cliques_callback, maximal_cliques_callback

Which uncoloured vertex vertex_coloring_greedy takes next.

typedef enum og_coloring_greedy_t {
    OG_COLORING_GREEDY_COLORED_NEIGHBORS = 0, /* most coloured neighbours */
    OG_COLORING_GREEDY_DSATUR = 1             /* most distinct neighbour colours */
} og_coloring_greedy_t;

Other values make vertex_coloring_greedy fail with OG_EINVAL.

Parameters

• OG_COLORING_GREEDY_COLORED_NEIGHBORS 0: the uncoloured vertex with the most coloured neighbours.
• OG_COLORING_GREEDY_DSATUR 1: the uncoloured vertex whose neighbours use the most distinct colours (saturation degree).

Checked

Enum; both values and an invalid one are tested with vertex_coloring_greedy.

C name

og_coloring_greedy_t

In notebooks

Og.ColoringGreedy

igraph 1.0

igraph_coloring_greedy_t

See also

vertex_coloring_greedy

Tells whether every pair of distinct vertices is joined by an edge.

og_error_t og_is_complete(const og_t *graph, og_bool_t *res);

A complete graph has an edge between each pair of distinct vertices. In a directed graph both u -> v and v -> u must be present for every pair. Self-loops and repeated edges do not count. The null graph and the one-vertex graph are complete.

The edge count is compared with the number of vertex pairs first, so most incomplete graphs are rejected without walking the adjacency lists.

Parameters

• graph The input graph.
• res Output: true when the graph is complete.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Complexity

O(|V| + |E|).

Checked

Same answer as python-igraph's Graph.is_complete on 245 graphs (null graph, one vertex, loops, multi-edges, directed).

C name

og_is_complete

In notebooks

Og.IsComplete

igraph 1.0

igraph_is_complete

See also

is_clique, clique_number

Tests whether the selected vertices are pairwise adjacent.

og_error_t og_is_clique(
    const og_t *graph,
    og_vs_t candidate,
    og_bool_t directed,
    og_bool_t *res
);

Repeated ids in candidate count once, and the empty set is a clique. Self-loops and edge multiplicities play no role. On a directed graph with directed = true every pair needs edges in both directions; with directed = false, or on an undirected graph, one edge between the two vertices in either direction is enough.

Parameters

• graph The input graph.
• candidate Vertex selector with the vertices to test.
• directed Directed graphs only: require edges in both directions between each pair.
• res Output: true when the vertices form a clique.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID candidate names a vertex that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(k log k + k^2 log d), k the number of distinct candidate vertices and d the largest degree: each pair is a binary search in the sorted adjacency.

Checked

Same answer as python-igraph's Graph.is_clique on 2,940 candidates (both values of directed, repeated ids, empty candidate).

C name

og_is_clique

In notebooks

Og.IsClique

igraph 1.0

igraph_is_clique

See also

is_independent_vertex_set, is_complete, cliques

Lists every clique whose size lies in a given range.

og_error_t og_cliques(
    const og_t *graph,
    og_vector_int_list_t *res,
    og_int_t min_size,
    og_int_t max_size,
    og_int_t max_results
);

A clique is a set of pairwise adjacent vertices. This function lists all of them in the size range, not only the maximal ones; each clique is a vector of vertex ids in res. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

The search is a depth-first enumeration over a fixed vertex order in which a clique is only extended by later vertices, so every clique comes out exactly once (Chiba and Nishizeki 1985); the size limits prune it. The order of the list is Open Graph's own: python-igraph lists the same cliques in another order. Cliquer, which igraph uses here, is not used.

Parameters

• graph The input graph.
• res Output: the cliques, one vertex-id vector each; cleared first.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL min_size and max_size are both positive and max_size < min_size.
• OG_ENOMEM Memory runs out.

Complexity

Proportional to the number of cliques listed times their size and the degrees involved; exponential in the worst case, as a graph can have exponentially many cliques.

Checked

Same cliques as python-igraph on 245 graphs and size ranges, compared as sets; python-igraph's list order is not reproduced.

C name

og_cliques

In notebooks

Og.Cliques

igraph 1.0

igraph_cliques

See also

cliques_callback, clique_size_hist, maximal_cliques, weighted_cliques

Counts the cliques of each size.

og_error_t og_clique_size_hist(
    const og_t *graph,
    og_vector_t *hist,
    og_int_t min_size,
    og_int_t max_size
);

Runs the enumeration of cliques without storing the cliques. hist[i] receives the number of cliques with i + 1 vertices; the vector is as long as the largest clique counted, and entries below min_size stay 0. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• hist Output: hist[i] is the number of cliques with i + 1 vertices.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL min_size and max_size are both positive and max_size < min_size.
• OG_ENOMEM Memory runs out.

Complexity

As cliques.

Checked

Equals the size distribution of python-igraph's Graph.cliques on 245 graphs (python-igraph has no direct histogram call).

C name

og_clique_size_hist

In notebooks

Og.CliqueSizeHist

igraph 1.0

igraph_clique_size_hist

See also

cliques, maximal_cliques_hist

Passes every clique in a size range to a function instead of storing it.

og_error_t og_cliques_callback(
    const og_t *graph,
    og_int_t min_size,
    og_int_t max_size,
    og_clique_handler_t *cliquehandler_fn,
    void *arg
);

Each clique the cliques enumeration finds is handed to cliquehandler_fn together with arg. The vector belongs to the search and is reused, so copy it to keep it. The handler returns OG_SUCCESS to go on, OG_STOP to end the search (the function then returns OG_SUCCESS), or any other code, which ends the search and is returned. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• cliquehandler_fn The handler (see clique_handler_t); must not be NULL.
• arg Passed unchanged to every handler call.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL cliquehandler_fn is NULL, or max_size < min_size with both positive.
• handler's code: The handler returned a code other than OG_SUCCESS and OG_STOP.
• OG_ENOMEM Memory runs out.

Complexity

As cliques, plus the handler's own work.

Checked

Same cliques as cliques, compared as sets; OG_STOP, error returns and a NULL handler are unit-tested.

C name

og_cliques_callback

In notebooks

Og.CliquesCallback

igraph 1.0

igraph_cliques_callback

See also

clique_handler_t, cliques, maximal_cliques_callback

Finds all cliques of the largest size.

og_error_t og_largest_cliques(const og_t *graph, og_vector_int_list_t *res);

Returns every clique whose size equals the clique number; several can tie. The maximal clique search of maximal_cliques runs with pruning on the best size found so far. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so. The null graph gives an empty list. The order of the list, and of the vertices inside each clique, follows python-igraph's on sparse, block and structured graphs; on small dense graphs it can differ (the cliques themselves are the same).

Parameters

• graph The input graph.
• res Output: the largest cliques; cleared first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

Worst case as maximal_cliques; the pruning usually makes it much faster.

Checked

Same cliques as python-igraph on every graph tested; same order on 260 of 263 fixture graphs and on all sparse and structured graphs of the independent check, a different order on 45 of 1,066 (all dense).

C name

og_largest_cliques

In notebooks

Og.LargestCliques

igraph 1.0

igraph_largest_cliques

See also

clique_number, maximal_cliques, largest_weighted_cliques

Size of the largest clique.

og_error_t og_clique_number(const og_t *graph, og_int_t *no);

The clique number, often written omega(G). The maximal clique search runs with pruning on the best size so far. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so. The null graph gives 0; any other graph at least 1.

Parameters

• graph The input graph.
• no Output (may be NULL): the size of a largest clique.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

Worst case as maximal_cliques; usually much less because of the pruning.

Checked

Same value as python-igraph's Graph.clique_number on 263 graphs.

C name

og_clique_number

In notebooks

Og.CliqueNumber

igraph 1.0

igraph_clique_number

See also

largest_cliques, weighted_clique_number, independence_number

Lists the cliques that no further vertex can join.

og_error_t og_maximal_cliques(
    const og_t *graph,
    og_vector_int_list_t *res,
    og_int_t min_size,
    og_int_t max_size,
    og_int_t max_results
);

A maximal clique is a clique that cannot be extended by another vertex. The search follows Eppstein, Löffler and Strash (2010): every vertex in turn is a start vertex, taken in order of k-core number, and runs a Bron-Kerbosch search with Tomita's pivot rule (Tomita, Tanaka, Takahashi 2006) inside its own neighbourhood, so each maximal clique is found exactly once. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

min_size and max_size filter by size; max_results stops the search early. The order of the list, and of the vertices inside each clique, follows python-igraph's on sparse, block and structured graphs; on small dense graphs it can differ (the cliques themselves are the same). On such graphs a max_results limit can therefore keep a different subset than python-igraph.

Parameters

• graph The input graph.
• res Output: the maximal cliques, one vertex-id vector each; cleared first.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

O(d |V| 3^(d/3)), d the degeneracy of the graph (the Eppstein-Löffler-Strash bound).

Checked

Used by OpenBI's engine. Same cliques as python-igraph on all 263 fixture graphs and 1,066 independent ones; same order on every sparse, block and structured graph, not on 64 of the 1,066 (mostly 5-20 vertices at 65-95% density). 0.13-0.73x python-igraph's time on graphs of 60k-100k edges.

C name

og_maximal_cliques

In notebooks

Og.MaximalCliques

igraph 1.0

igraph_maximal_cliques

See also

maximal_cliques_count, maximal_cliques_callback, maximal_cliques_subset, largest_cliques, cliques

#include "og.h"
#include <stdio.h>

/* Nine people and who is friends with whom: which circles all know one another? */
enum { ANNA, BO, CARL, DINA, EMIL, FRIDA, GUNNAR, HEDDA, IVAR };   /* 0 to 8 */

int main(void) {
    og_t friends;
    og_vector_int_list_t circles;
    og_int_t i, j;

    og_small(&friends, 9, OG_UNDIRECTED,
             ANNA,BO, ANNA,CARL, ANNA,DINA, BO,CARL, BO,DINA, CARL,DINA,  /* classmates */
             DINA,EMIL, DINA,FRIDA, EMIL,FRIDA,                         /* runners */
             FRIDA,GUNNAR, FRIDA,HEDDA, GUNNAR,HEDDA,                   /* colleagues */
             HEDDA,IVAR, -1);
    og_vector_int_list_init(&circles, 0);
    /* circles of three or more: a lone friendship is not a circle */
    og_maximal_cliques(&friends, &circles, 3, 0, OG_UNLIMITED);
    for (i = 0; i < og_vector_int_list_size(&circles); i++) {
        const og_vector_int_t *members = og_vector_int_list_get_ptr(&circles, i);
        printf("%" OG_PRId " people:", og_vector_int_size(members));
        for (j = 0; j < og_vector_int_size(members); j++) {
            printf(" %" OG_PRId, OG_VECTOR(*members)[j]);
        }
        printf("\n");
    }
    /* prints
       3 people: 4 3 5      Emil, Dina and Frida
       3 people: 5 6 7      Frida, Gunnar and Hedda
       4 people: 1 0 3 2    Bo, Anna, Dina and Carl */
    og_vector_int_list_destroy(&circles);
    og_destroy(&friends);
    return 0;
}

Counts the maximal cliques in a size range without listing them.

og_error_t og_maximal_cliques_count(
    const og_t *graph,
    og_int_t *res,
    og_int_t min_size,
    og_int_t max_size
);

Runs the search of maximal_cliques and only counts. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• res Output (may be NULL): how many maximal cliques fall in the size range.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As maximal_cliques.

Checked

Equals the length of python-igraph's maximal_cliques list, size ranges included, on 263 graphs.

C name

og_maximal_cliques_count

In notebooks

Og.MaximalCliquesCount

igraph 1.0

igraph_maximal_cliques_count

See also

maximal_cliques, maximal_cliques_hist

Writes the maximal cliques to an open file, one per line.

og_error_t og_maximal_cliques_file(
    const og_t *graph,
    FILE *outfile,
    og_int_t min_size,
    og_int_t max_size,
    og_int_t max_results
);

Each clique becomes one text line: its vertex ids in decimal, separated by single spaces, ended by a newline. The lines come in the order of maximal_cliques. The file must be open for writing; it is neither flushed nor closed here. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• outfile An open FILE * to write to; must not be NULL.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL outfile is NULL.
• OG_EFILE Writing to the file failed.
• OG_ENOMEM Memory runs out.

Complexity

As maximal_cliques, plus the output.

Checked

Byte-identical to the text python-igraph writes with maximal_cliques(file=...) on 83 graphs; on dense graphs the line order follows maximal_cliques and can differ (3 of 236 files in the independent check).

C name

og_maximal_cliques_file

In notebooks

Og.MaximalCliquesFile

igraph 1.0

igraph_maximal_cliques_file

See also

maximal_cliques, maximal_cliques_subset

Runs the maximal clique search from chosen start vertices only.

og_error_t og_maximal_cliques_subset(
    const og_t *graph,
    const og_vector_int_t *subset,
    og_vector_int_list_t *res,
    og_int_t *no,
    FILE *outfile,
    og_int_t min_size,
    og_int_t max_size,
    og_int_t max_results
);

maximal_cliques gives each maximal clique to exactly one start vertex. This function runs only the searches of the vertices in subset, in the order given. Splitting all vertices into parts and calling it once per part therefore yields every maximal clique exactly once, and the parts can be processed independently (on several threads of the caller, for example).

Results go to any of res (a list), no (a count) and outfile (one clique per line, as maximal_cliques_file); each may be NULL. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• subset Start vertex ids; must not be NULL.
• res Output (may be NULL): the cliques found; cleared first.
• no Output (may be NULL): the number of cliques found.
• outfile Open FILE * (may be NULL) that receives one clique per line.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL subset is NULL.
• OG_EINVVID subset names a vertex that is not in the graph (checked even when max_results is 0).
• OG_EFILE Writing to outfile failed.
• OG_ENOMEM Memory runs out.

Complexity

As maximal_cliques, limited to the searches of the chosen start vertices.

Checked

python-igraph has no subset call. Tested: a partition of the start vertices yields every maximal clique of maximal_cliques exactly once; list, count and file outputs agree.

C name

og_maximal_cliques_subset

In notebooks

Og.MaximalCliquesSubset

igraph 1.0

igraph_maximal_cliques_subset

See also

maximal_cliques, maximal_cliques_file

Histogram of maximal clique sizes.

og_error_t og_maximal_cliques_hist(
    const og_t *graph,
    og_vector_t *hist,
    og_int_t min_size,
    og_int_t max_size
);

hist[i] receives how many maximal cliques have i + 1 vertices; the vector is as long as the largest maximal clique counted, and entries outside the size range stay 0. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• hist Output: hist[i] counts the maximal cliques with i + 1 vertices.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As maximal_cliques.

Checked

Equals the size distribution of python-igraph's maximal_cliques on 263 graphs (python-igraph has no direct histogram call).

C name

og_maximal_cliques_hist

In notebooks

Og.MaximalCliquesHist

igraph 1.0

igraph_maximal_cliques_hist

See also

maximal_cliques, clique_size_hist

Passes every maximal clique in a size range to a function instead of storing it.

og_error_t og_maximal_cliques_callback(
    const og_t *graph,
    og_int_t min_size,
    og_int_t max_size,
    og_clique_handler_t *cliquehandler_fn,
    void *arg
);

Each maximal clique is handed to cliquehandler_fn with arg, in the order of maximal_cliques. The vector belongs to the search: copy it to keep it. OG_SUCCESS from the handler continues, OG_STOP ends the search with success, any other code ends it and is returned. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• cliquehandler_fn The handler (see clique_handler_t); must not be NULL.
• arg Passed unchanged to every handler call.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL cliquehandler_fn is NULL.
• handler's code: The handler returned a code other than OG_SUCCESS and OG_STOP.
• OG_ENOMEM Memory runs out.

Complexity

As maximal_cliques, plus the handler's own work.

Checked

Same cliques and order as maximal_cliques (with its caveat for dense graphs); OG_STOP and error returns tested.

C name

og_maximal_cliques_callback

In notebooks

Og.MaximalCliquesCallback

igraph 1.0

igraph_maximal_cliques_callback

See also

clique_handler_t, maximal_cliques, cliques_callback

Lists cliques, or maximal cliques, whose total vertex weight lies in a range.

og_error_t og_weighted_cliques(
    const og_t *graph,
    const og_vector_t *vertex_weights,
    og_vector_int_list_t *res,
    og_bool_t maximal,
    og_real_t min_weight,
    og_real_t max_weight,
    og_int_t max_results
);

The weight of a clique is the sum of its vertex weights. Weights are integers of at least 1: fractional parts are dropped with a warning, and NULL gives every vertex weight 1. With maximal = true only maximal cliques are listed, otherwise every clique. min_weight and max_weight bound the total; 0 or less means no bound, and positive limits are cut to their integer part, so 0 < max_weight < 1 admits no clique. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

The non-maximal form is the depth-first enumeration of cliques with weight bounds, the maximal form the search of maximal_cliques with weight limits. The list order is Open Graph's own. Cliquer, which igraph uses here, is not used.

Parameters

• graph The input graph.
• vertex_weights Weight of every vertex (integers of at least 1), or NULL for weight 1 everywhere.
• res Output: the cliques found; cleared first.
• maximal true: maximal cliques only; false: every clique.
• min_weight Smallest total weight to report; 0 or less means no bound.
• max_weight Largest total weight to report; 0 or less means no bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL A weight limit is NaN, or both limits are positive and max_weight < min_weight.
• OG_EINVAL vertex_weights does not have one entry per vertex, or a weight is NaN or below 1.
• OG_EOVERFLOW A weight is so large that a clique's total could overflow.
• OG_ENOMEM Memory runs out.

Complexity

Exponential in the worst case, like the unweighted searches it builds on.

Checked

python-igraph has no weighted cliques. Checked as sets against a reference built from python-igraph's unweighted cliques weighed by hand: 657 queries over 162 weighted graphs plus the NULL-weights path.

C name

og_weighted_cliques

In notebooks

Og.WeightedCliques

igraph 1.0

igraph_weighted_cliques

See also

largest_weighted_cliques, weighted_clique_number, cliques, maximal_cliques

Finds the cliques of the largest total vertex weight.

og_error_t og_largest_weighted_cliques(
    const og_t *graph,
    const og_vector_t *vertex_weights,
    og_vector_int_list_t *res
);

Lists every clique whose weight equals the largest clique weight (such a clique is always maximal, as weights are positive). Weights as in weighted_cliques. The maximal clique search prunes on the weight the remaining candidates could still add. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• vertex_weights Weight of every vertex (integers of at least 1), or NULL for weight 1 everywhere.
• res Output: the heaviest cliques; cleared first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL vertex_weights does not have one entry per vertex, or a weight is NaN or below 1.
• OG_EOVERFLOW A weight is so large that a clique's total could overflow.
• OG_ENOMEM Memory runs out.

Complexity

Worst case as maximal_cliques.

Checked

Checked as sets against the brute-force reference of weighted_cliques.

C name

og_largest_weighted_cliques

In notebooks

Og.LargestWeightedCliques

igraph 1.0

igraph_largest_weighted_cliques

See also

weighted_cliques, weighted_clique_number, largest_cliques

Largest total vertex weight of a clique.

og_error_t og_weighted_clique_number(
    const og_t *graph,
    const og_vector_t *vertex_weights,
    og_real_t *res
);

res receives the weight as a real number with an integer value. With NULL weights it equals clique_number; the null graph gives 0. Weights as in weighted_cliques. Edge directions, self-loops and edge multiplicities are ignored; a directed graph gets a warning saying so.

Parameters

• graph The input graph.
• vertex_weights Weight of every vertex (integers of at least 1), or NULL for weight 1 everywhere.
• res Output: the largest clique weight.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL vertex_weights does not have one entry per vertex, or a weight is NaN or below 1.
• OG_EOVERFLOW A weight is so large that a clique's total could overflow.
• OG_ENOMEM Memory runs out.

Complexity

Worst case as maximal_cliques.

Checked

Checked against the brute-force reference of weighted_cliques.

C name

og_weighted_clique_number

In notebooks

Og.WeightedCliqueNumber

igraph 1.0

igraph_weighted_clique_number

See also

weighted_cliques, largest_weighted_cliques, clique_number

Tests whether no two of the selected vertices are adjacent.

og_error_t og_is_independent_vertex_set(
    const og_t *graph,
    og_vs_t candidate,
    og_bool_t *res
);

Repeated ids count once, self-loops and edge directions are ignored, and the empty set is independent.

Parameters

• graph The input graph.
• candidate Vertex selector with the vertices to test.
• res Output: true when no two of them are adjacent.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID candidate names a vertex that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(k log k + k^2 log d), k the number of distinct candidate vertices and d the largest degree.

Checked

Same answer as python-igraph's Graph.is_independent_vertex_set on 1,175 candidates.

C name

og_is_independent_vertex_set

In notebooks

Og.IsIndependentVertexSet

igraph 1.0

igraph_is_independent_vertex_set

See also

is_clique, independent_vertex_sets

Lists every independent vertex set in a size range.

og_error_t og_independent_vertex_sets(
    const og_t *graph,
    og_vector_int_list_t *res,
    og_int_t min_size,
    og_int_t max_size,
    og_int_t max_results
);

An independent set has no edge between any two of its vertices. All of them in the size range are listed, not only the maximal ones. The list is ordered by size, then lexicographically, and each set lists its vertices in increasing order. min_size of 0 or less means 1, so the empty set is never listed; max_size of 0 or less means the vertex count. Edge directions (with a warning), self-loops and multi-edges are ignored.

Parameters

• graph The input graph.
• res Output: the independent sets; cleared first.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

Proportional to the number of sets listed times their size; exponential in the worst case.

Checked

python-igraph's exact order (by size, then lexicographic) on 126 graphs, with size ranges and max_results.

C name

og_independent_vertex_sets

In notebooks

Og.IndependentVertexSets

igraph 1.0

igraph_independent_vertex_sets

See also

maximal_independent_vertex_sets, largest_independent_vertex_sets, cliques

Every independent vertex set of maximum size.

og_error_t og_largest_independent_vertex_sets(
    const og_t *graph,
    og_vector_int_list_t *res
);

Lists every independent set whose size equals the independence number, using the search of maximal_independent_vertex_sets and keeping the largest sets; the order matches python-igraph's. The null graph gives one set, the empty one. Edge directions (with a warning), self-loops and multi-edges are ignored.

Parameters

• graph The input graph.
• res Output: the largest independent sets; cleared first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As maximal_independent_vertex_sets.

Checked

python-igraph's exact order on 207 graphs (the order was inferred black-box: Tsukiyama et al. search).

C name

og_largest_independent_vertex_sets

In notebooks

Og.LargestIndependentVertexSets

igraph 1.0

igraph_largest_independent_vertex_sets

See also

independence_number, maximal_independent_vertex_sets, largest_cliques

Lists the independent vertex sets that no further vertex can join.

og_error_t og_maximal_independent_vertex_sets(
    const og_t *graph,
    og_vector_int_list_t *res,
    og_int_t min_size,
    og_int_t max_size,
    og_int_t max_results
);

A maximal independent set cannot take another vertex without gaining an edge inside. The search follows Tsukiyama, Ide, Ariyoshi and Shirakawa (1977): the maximal sets of the graph on vertices 0..i grow from those on 0..i-1, and every set has one parent, so each is produced once. It uses an explicit stack, not recursion, so large graphs cannot exhaust the call stack. The order matches python-igraph's. The null graph has one maximal independent set, the empty one. Edge directions (with a warning), self-loops and multi-edges are ignored.

Parameters

• graph The input graph.
• res Output: the maximal independent sets; cleared first.
• min_size Smallest size to report; 0 or less means no lower bound.
• max_size Largest size to report; 0 or less means no upper bound.
• max_results Stop after this many results; a negative value (OG_UNLIMITED) means no limit, 0 gives an empty result.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

Polynomial time per set produced (O(|V| |E|) per set in Tsukiyama et al.'s analysis); the number of sets can be exponential.

Checked

python-igraph's exact order on 207 graphs, with size ranges and max_results; 200,000 isolated vertices run without deep recursion.

C name

og_maximal_independent_vertex_sets

In notebooks

Og.MaximalIndependentVertexSets

igraph 1.0

igraph_maximal_independent_vertex_sets

See also

largest_independent_vertex_sets, independent_vertex_sets, independence_number

Independence number: how many vertices a maximum independent set has.

og_error_t og_independence_number(const og_t *graph, og_int_t *no);

Often written alpha(G). Self-loops are ignored, as everywhere in this chapter, so the result always equals the size of the sets largest_independent_vertex_sets returns. The null graph gives 0.

Parameters

• graph The input graph.
• no Output: the independence number.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As maximal_independent_vertex_sets.

Checked

Equals python-igraph on every loop-free graph. Differs by design with self-loops: python-igraph 1.0 can report more than the size of its own largest independent sets there (2 vertices, edges 0-1, 0-0, 1-1: it gives 2, Open Graph 1).

C name

og_independence_number

In notebooks

Og.IndependenceNumber

igraph 1.0

igraph_independence_number

See also

largest_independent_vertex_sets, clique_number

Colours the vertices greedily so that adjacent vertices get different colours.

og_error_t og_vertex_coloring_greedy(
    const og_t *graph,
    og_vector_int_t *colors,
    og_coloring_greedy_t heuristic
);

Colours are 0, 1, 2, ...; each vertex in turn gets the smallest colour that none of its coloured neighbours has. heuristic picks the next vertex. OG_COLORING_GREEDY_COLORED_NEIGHBORS starts at a vertex of largest degree and then always takes an uncoloured vertex with the most coloured neighbours (bucket queue). OG_COLORING_GREEDY_DSATUR (Brélaz 1979) takes the vertex whose neighbours already show the most distinct colours, ties broken by the most uncoloured neighbours and then the lowest id.

Edge directions, self-loops and multi-edges are ignored. The result is always a proper colouring with at most (largest degree + 1) colours, usually far fewer, but not necessarily the fewest possible.

Parameters

• graph The input graph.
• colors Output: the colour of every vertex; resized to the vertex count.
• heuristic OG_COLORING_GREEDY_COLORED_NEIGHBORS or OG_COLORING_GREEDY_DSATUR.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL heuristic is not one of the two values.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|) for COLORED_NEIGHBORS; O((|V| + |E|) log |V|) for DSATUR (binary heap).

Checked

Not the same colouring as python-igraph: its tie order could not be inferred. Always a valid colouring; colour counts within 1% of python-igraph's over 220 graphs for both heuristics.

C name

og_vertex_coloring_greedy

In notebooks

Og.VertexColoringGreedy

igraph 1.0

igraph_vertex_coloring_greedy

See also

coloring_greedy_t, is_vertex_coloring

Checks that no edge joins two vertices of the same colour.

og_error_t og_is_vertex_coloring(
    const og_t *graph,
    const og_vector_int_t *types,
    og_bool_t *res
);

types gives one colour (any integer) per vertex. Self-loops are ignored and edge directions do not matter.

Parameters

• graph The input graph.
• types The colour of every vertex.
• res Output: true when the colouring is proper.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL types does not have one entry per vertex.

Complexity

O(|E|).

Checked

python-igraph has no counterpart: 860 checks against the definition.

C name

og_is_vertex_coloring

In notebooks

Og.IsVertexColoring

igraph 1.0

igraph_is_vertex_coloring

See also

vertex_coloring_greedy, is_edge_coloring, is_bipartite_coloring

Checks that a two-colouring puts the ends of every edge on different sides, and tells which way the edges run.

og_error_t og_is_bipartite_coloring(
    const og_t *graph,
    const og_vector_bool_t *types,
    og_bool_t *res,
    og_neimode_t *mode
);

types assigns false or true to every vertex. The result is true when every edge that is not a self-loop joins a false vertex and a true one; self-loops are ignored.

mode (may be NULL) reports the edge direction: OG_OUT when every edge of a directed graph goes from false to true, OG_IN when every edge goes from true to false, and OG_ALL otherwise (undirected graphs, edges in both directions, no edges, or a colouring that fails).

Parameters

• graph The input graph.
• types The side (false or true) of every vertex.
• res Output: true when every edge joins the two sides.
• mode Output (may be NULL): OG_OUT, OG_IN or OG_ALL as described.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL types does not have one entry per vertex.

Complexity

O(|E|).

Checked

python-igraph has no counterpart: 489 checks against the definition, the mode included.

C name

og_is_bipartite_coloring

In notebooks

Og.IsBipartiteColoring

igraph 1.0

igraph_is_bipartite_coloring

See also

is_bipartite, is_vertex_coloring

Checks that edges sharing a vertex have different colours.

og_error_t og_is_edge_coloring(
    const og_t *graph,
    const og_vector_int_t *types,
    og_bool_t *res
);

types gives one colour per edge. Two distinct edges with a common endpoint must differ in colour. A self-loop does not clash with itself, but does with the other edges at its vertex. Edge directions are ignored.

Parameters

• graph The input graph.
• types The colour of every edge.
• res Output: true when the edge colouring is proper.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL types does not have one entry per edge.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E| log D), D the largest degree: the colours at each vertex are sorted.

Checked

python-igraph has no counterpart: 520 checks against the definition.

C name

og_is_edge_coloring

In notebooks

Og.IsEdgeColoring

igraph 1.0

igraph_is_edge_coloring

See also

is_vertex_coloring

Tests whether a simple undirected graph is perfect.

og_error_t og_is_perfect(const og_t *graph, og_bool_t *perfect);

A graph is perfect when every induced subgraph can be coloured with as many colours as its largest clique has vertices. By the strong perfect graph theorem (Chudnovsky, Robertson, Seymour, Thomas 2006) that holds exactly when neither the graph nor its complement contains an odd hole: an induced cycle of odd length 5 or more.

Bipartite, co-bipartite and chordal graphs are accepted at once (chordality by maximum cardinality search, Tarjan and Yannakakis 1984); otherwise odd holes are searched for in the graph and in its complement. Graphs with fewer than 5 vertices are perfect.

Parameters

• graph The input graph.
• perfect Output: true when the graph is perfect.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The graph is directed, or has a self-loop or a multi-edge.
• OG_ENOMEM Memory runs out.

Complexity

Polynomial for the quick accepts. The odd-hole search enumerates induced paths and is exponential in the worst case: a perfect graph with many even holes can be slow (the line graph of a random 20x20 bipartite graph, 80 vertices, takes over 30 s).

Checked

python-igraph has no counterpart: 252 graphs against an exhaustive check of the definition (up to 9 vertices) plus named graphs.

C name

og_is_perfect

In notebooks

Og.IsPerfect

igraph 1.0

igraph_is_perfect

See also

clique_number, vertex_coloring_greedy, is_bipartite

Tests whether removing a vertex set disconnects vertices that were connected.

og_error_t og_is_separator(
    const og_t *graph,
    const og_vs_t candidate,
    og_bool_t *res
);

The set S separates the graph when two vertices outside S that are connected in the graph are no longer connected once S is removed. Edge directions are ignored and repeated ids count once. By this definition the empty set, a set leaving fewer than two vertices, and a set whose removal splits nothing that was joined are not separators.

Parameters

• graph The input graph.
• candidate Vertex selector with the set to test.
• res Output: true when the set separates the graph.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID candidate names a vertex that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

Same answer as python-igraph's Graph.is_separator on 3,022 candidates over 263 graphs (directed ones, repeated ids, empty and full candidates).

C name

og_is_separator

In notebooks

Og.IsSeparator

igraph 1.0

igraph_is_separator

See also

is_minimal_separator, minimum_size_separators

Tests whether a vertex set separates the graph while no proper subset of it does.

og_error_t og_is_minimal_separator(
    const og_t *graph,
    const og_vs_t candidate,
    og_bool_t *res
);

Uses an equivalent linear-time condition (proved in the area's provenance notes): S is a minimal separator exactly when all of S lies in one connected component C, C without S falls into at least two pieces, and every vertex of S has a neighbour in each piece. Edge directions are ignored, repeated ids count once, and the empty set is not minimal.

Parameters

• graph The input graph.
• candidate Vertex selector with the set to test.
• res Output: true when the set is a minimal separator.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID candidate names a vertex that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

Follows the definition (brute force over all subsets on 2,865 candidates). python-igraph 1.0 agrees on 2,859; on the other 6 it calls a set minimal although a proper subset separates, and its answer depends on the order of the candidate's ids.

C name

og_is_minimal_separator

In notebooks

Og.IsMinimalSeparator

igraph 1.0

igraph_is_minimal_separator

See also

is_separator, all_minimal_st_separators

Lists every vertex set that minimally separates some pair of vertices.

og_error_t og_all_minimal_st_separators(
    const og_t *graph,
    og_vector_int_list_t *separators
);

A set S is a minimal (s,t)-separator when removing it puts s and t in different components and no proper subset does so for that pair; this lists such sets for all pairs. Algorithm of Berry, Bordat and Cogis (1999): first, for every vertex v, the neighbourhoods of the components of the graph without v and its neighbours; then, for each separator S found and each x in S, the neighbourhoods of the components of the graph without S and the neighbours of x. Duplicates are dropped through a hash set.

Each separator lists its vertices in increasing order. The list order (vertex by vertex, components by their lowest vertex, then in the order found) is python-igraph's. Edge directions are ignored.

Parameters

• graph The input graph.
• separators Output: the separators; cleared first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

O(|V| (|V| + |E|)) per separator found.

Checked

python-igraph's exact order, members included, on 238 graphs (9,638 separators).

C name

og_all_minimal_st_separators

In notebooks

Og.AllMinimalStSeparators

igraph 1.0

igraph_all_minimal_st_separators

See also

minimum_size_separators, is_minimal_separator

Lists every vertex separator of the smallest possible size.

og_error_t og_minimum_size_separators(
    const og_t *graph,
    og_vector_int_list_t *separators
);

A minimum-size separator is a set of kappa(G) vertices, kappa the vertex connectivity, whose removal disconnects the graph. kappa comes from maximum flows on the split network (Even and Tarjan 1975), using only pairs that involve one of the first kappa + 1 vertices (Even 1975). Every minimum separator is then a minimum vertex cut for such a pair (Kanevsky 1993); the cuts are enumerated from the residual network (Picard and Queyranne 1980), each separator reported once.

The list is in lexicographic order, each separator's vertices increasing. Disconnected graphs, complete graphs and graphs with fewer than two vertices give an empty list.

Parameters

• graph The input graph.
• separators Output: the separators; cleared first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The graph is directed.
• OG_ENOMEM Memory runs out.

Complexity

O(kappa |V|) maximum flows on a network of 2|V| vertices, then work proportional to the separators found.

Checked

Same separators as python-igraph, compared as sets (its order is arbitrary, Open Graph's lexicographic), on 397 graphs with 10,682 separators; the 19,700 separators of C_200 take 0.06 s (python-igraph 0.77 s).

C name

og_minimum_size_separators

In notebooks

Og.MinimumSizeSeparators

igraph 1.0

igraph_minimum_size_separators

See also

all_minimal_st_separators, vertex_connectivity, cohesive_blocks, even_tarjan_reduction

Builds the split directed graph whose maximum flows count vertex-disjoint paths.

og_error_t og_even_tarjan_reduction(
    const og_t *graph,
    og_t *graphbar,
    og_vector_t *capacity
);

Each vertex i becomes two vertices, i (entry) and i + n (exit), n the vertex count, joined by the arc i -> i + n of capacity 1. Each edge {a, b} becomes the arcs a + n -> b and b + n -> a of capacity n, which no minimum cut uses; input directions are not used. The vertex arcs come first (n of them), then two arcs per edge in edge order.

A maximum flow from s + n to t in the result equals the number of s-t paths that share no inner vertex, which is the s-t vertex connectivity when s and t are not adjacent (Even and Tarjan 1975).

Parameters

• graph The input graph.
• graphbar Output: an uninitialised og_t. The function creates the result graph; free it with destroy. Directed, with 2|V| vertices and |V| + 2|E| edges.
• capacity Output (may be NULL): the capacity of every edge of graphbar.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EOVERFLOW The graph has more than half of the largest supported vertex count.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

python-igraph has no counterpart. The maximum flow from s + n to t equals python-igraph's s-t vertex connectivity on 540 pairs. The arc directions are the ones under which flows count vertex-disjoint paths; the edge order and capacity layout could not be compared with igraph.

C name

og_even_tarjan_reduction

In notebooks

Og.EvenTarjanReduction

igraph 1.0

igraph_even_tarjan_reduction

See also

st_vertex_connectivity, minimum_size_separators, maxflow