The graph file format

To read and write graphs in files, bliss uses a variant of the DIMACS textual graph file format. The main difference is that bliss uses DIMACS “node descriptors” to describe the vertex colors. A graph file in the format consists of the following four consecutive parts:

  • Comments. In the beginning of the file, there can be comment lines that start with the character c. For instance

    c The constraint graph of a CNF formula.

    is a comment line. Comment lines have no semantic meaning, and are ignored by bliss.

  • Problem definition line. After the comment lines, there must be the “problem definition line” of the form

    p edge N E

    Here N is the number of vertices and E is the number of edges in the graph. In the file format, the vertices are numbered from 1 to N.

  • Vertex colors. After the problem definition line, the next lines of the form

    n v c

    define the colors of the vertices: v is the number of a vertex and c is the color of that vertex. The color c should be a non-negative integer fitting in the domain of the unsigned int type in the C++ programming language. It is not necessary to include a color definition line for each vertex, the default color for a vertex is 0. If the color of a vertex is defined more than once, the last definition applies.

  • Edges. Following the color definition lines, the next E lines of the form

    e v1 v2

    describe the edges in the graph, where 1 ≤ v1,v2 ≤ N are the numbers of the vertices connected by the edge. Multiple definitions of the same edge are ignored.

The graph file format itself does not make any distinction between undirected and directed graphs. This is done by a tool that uses the file format (e.g. the command bliss graphfile vs. bliss -directed graphfile). When the graph file is interpreted as an undirected graph, a line e v1 v2 represents the undirected edge between the vertices v1 and v2, and is thus equivalent to the line e v2 v1. For directed graphs, a line e v1 v2 represents the directed edge from the vertex v1 to the vertex v2.

As an example, assume that blue corresponds to the color “0” and green to “1”. The graph

A graph

can be described in the file format as:

c An example graph.
p edge 4 5
n 1 1
e 1 2
e 1 3
e 1 4
e 2 3
e 2 4

When interpreted as a directed graph, the file represents the directed graph

A directed graph