cliquer1

Usage

Overview

cliquer searched for cliques in a graph. The graph is read from the file given as command line argument, or stdin if that filename is "-".

The file must be ASCII as described below or a binary DIMACS-format.

By default it prints the first maximal clique it finds, but this can be changed with the options described below.

Options

-h --help

Displays a short list of options and what they do.

-a --all

Find all cliques.

-s --single

Find only one clique (default).

-w --weight

Tell only maximum weight (no faster than -s).

-m N --min N

Search for cliques with weight at least N.

If N=0, searches for maximum weight clique (default).

-M N --max N

Search for cliques with weight at most N.

If N=0, no limit is imposed (default).

N being positive is incompatible with "--min 0" ("--min 1" is assumed).

-x --maximal

Require cliques to be maximal.

-u --unweighted

Assume weight 1 for all vertices.

-0 --from-0

Number vertices 0 to n-1 instead of 1 to n when writing.

-q --quiet

Suppresses progress output.

Specifying -q twice suppresses all output except the actual result.

-r F --reorder F

Reorder with function F. Available reordering functions are:

none

No ordering (same order as in the file).

reverse

Reverse order as in the file.

default

One of the two below, depending on weightedness.

unweighted-coloring

Coloring method efficient for unweighted graphs.

weighted-coloring

Coloring method efficient for weighted graphs.

degree

Order by ascending degree.

random

Random order.

File format

The format of the ASCII representation of a graph is the following: Each line has a single letter (enclosed in spaces) as first part.

A line with 'p' starts the graph. The second token is a name of at most 15 characters and ignored. Then there is the number of nodes in this graph. Then the number of edges (currently ignored).

A line with 'e' adds an edge. The two next tokens are the numbers of two nodes to connect.

A line with 'n' weights an node. The first argument is the number of the node to assign a weight to, the second it's weight.

Examples

p clausehouse 5 8
e 4 3
e 3 1
e 1 2
e 2 3
e 3 5
e 5 2
e 2 4
e 4 5
n 1 2