DESCRIPTION OF "kthlist" ADJACENCY LIST GRAPH FORMAT
====================================================
by Jakob Nordström (jakobn@kth.se)

Last update: November 16th, 2016


FORMAL DESCRIPTION

The "kthlist" adjacency list graph format can be used to represent
directed, undirected, and bipartite graphs.  The format for all of
these graph types is the same, and "kthlist" does not contain any way
of specifying which type of graph is intended (except that this will
of course be expected to be made clear by other means, e.g., in a
comment at the top of the graph file). Thus, it is the responsibility
of the user to interpret data correctly, but this should not be a
problem since the intended meaning should always be clear from
context.
     
The expected format of the input file is as follows:

- Every empty line, i.e. consisting only of a newline, is ignored.

- Every line starting with 'c' or 'C' is a comment and is ignored except
  if it occurs in the first block of comments at the top of the file and 
  contains coordinates for a vertex as specified next.

- A line on the form
    
    c coord <integer>: (real, real)
  
  occurring in the first block of comments at the beginning of the
  file is interpreted to specify the x and y coordinates for the
  vertex with index given by the integer. Such coordinates can be
  inserted in the generated GML file if the graph is converted to GML
  format using the kthlist2gml utility.  Coordinates are assumed to be
  positive numbers --- specifying negative coordinates is an
  error. Specifying coordinates multiple times for the same vertex is
  an error (regardless of whether the values are consistent or not).
    
- The first non-comment non-empty line should be an integer <nvert>,
  which is the number of vertices of the graph.

- For all other non-comment non-empty lines the following
  holds. The default expected format for such lines is 

      <int1> : <int2> ... <intN> 0

  which means that for a directed graph the vertex <int1> has
  <int2>, ..., <intN> as immediate predecessors, i.e., there are
  directed edges (<int2>,<int1>), ..., (<intN>,<int1>), whereas
  for an undirected graph <int2>, ..., <intN> are simply
  neighbouring vertices. For a bipartite graph, <int1> should be a 
  left vertex and <int2> ...<intN> should be right vertices.

  It is also allowed to break a long list of predecessors or
  neighbours over several lines, in which case the first line
  will look like 

      <int1> : <int2> ... <intM>

  and following lines will be on the format

      <intI> ... <intJ> 

  until a final line

      <intK> ... <intN> 0

  is reached. Each neighbour list has to start on a new line, however.

  Having lines "<int1> : 0" without any neighbours is allowed --- for
  source vertices of DAGs, for instance --- but is superfluous unless
  one wants to encode a bipartite graph with an isolated vertex on the
  left.  All vertex indices should be between 1 and <nvert>.  For an
  undirected non-bipartite graph, it is assumed that <int1> appears in
  the adjacency list of <int2> if <int2> appears in the adjacency list
  of <int1>, and the result is implementation-dependent otherwise.

  For a directed *acyclic* graph (DAG) it is assumed that listing
  vertices in the order 1, 2, 3, ..., <nvert> is a correct topological
  ordering of the DAG.


SOME SMALL EXAMPLES

(1) Directed graph

By default kthlist graphs are directed, so that

3
3: 1 2 0

is the graph with sources 1 and 2 and sink 3.

(2) Undirected graph

An undirected graphs is simply a directed graph with all edges going
in both directions, so that the graph above would become

3
1: 3 0
2: 3 0
3: 1 2 0

(3) Bipartite graph

A bipartite graph is a graph where we only list vertices on the left
and where the neighbours are incoming edges from the right. Thus,
K_{3,2} can be represented as

5
1: 4 5 0
2: 4 5 0
3: 4 5 0

Note that any piece of code generating formulas from bipartite graphs
(in CNFgen, for instance) knows that it should expect a bipartite
graph, so there can never be any ambiguity when reading a graph in
predecessor list format. The meaning is always completely clear from
context.


IMPLEMENTATION COMMENTS

In the kthlist2gml graph format converter all lines in the input file
are assumed to be at most MAXLINELENGTH = 100,000 characters long ---
longer lines will result in an error. Also, the number of vertices in
the graph is assumed to be at most MAXNVERTICES = 10,000 (since larger
graphs won't really be feasible to visualize anyway).

In the graph generation code that we have it will generally be the
case that a predecessor/neighbour list is given on one, single line,
but the kthlist2gml converter does not assume that this is the case.