DIMACS Challenge II 
  
  DIMACS Format for Storing Undirected Graphs in Binary Files
  -----------------------------------------------------------

The binary format for storing a graph is an alternative to the ascii
(human readable) format described in the File Formats section of the
document /pub/challenge/graph/doc/ccformat.tex at dimacs.rutgers.edu
(anonymous ftp). 

If the edge density of the graph is bigger than ~1.2%, the binary
storage is more space efficient. It uses roughly (N^2)/16 bytes 
for a graph of N vertices and M edges, while the ascii format needs
about M*9 bytes for the same graph.


The file "binformat.shar" contains three codes:
-----------------------------------------------

	asc2bin infile [outfile]

		Converts an ascii format file (infile) to binary format. 
		If "outfile" is omitted, it creates a file "infile.b".

	bin2asc infile [outfile]

		Converts a binary format file (infile) to ascii format.
		"infile" must have suffix ".b". 
		If "outfile" is omitted, it creates a file with the same name
		as "infile", eexcept the ".b" suffix is removed.
	
	showpreamble binary_infile [outfile]

		Extracts the preamble information of the "binary_infile"
		to stdout or to a "outfile".


BINARY FORMAT for storing a graph of N vertices
-----------------------------------------------

The file consists of 3 blocks: 

	First Line
	Preamble
	Binary Block (The rest of the file)

	The First Line contains an integer (%d, say #) describing the
	length of the proceeding preamble.

	The a Preamble consists of # characters, and contains possibly
some comments following the ascii format plus a line
describing the number of vertices and edges in the graph. 
(In "p type Num_vertices Num_edges" format).

	The Binary Block contains the lower triangular part of the
vertex-vertex adjacency matrix of the graph. Each row of the matrix is
stored as sequence of bits, where the j'th bit is 1 if the edge (i,j) 
is in the graph otherwise the bit is 0. (Note that i >= j)

For more information, see the routine "read_graph_DIMACS_bin()"
in the file "bin2asc.c". 

IMPLEMENTATION details
----------------------

You may read the files "asc2bin.c" and "bin2asc.c" and extract any
part of the code to implement the binary storage internally.