Linux and UNIX Man Pages

Linux & Unix Commands - Search Man Pages

mcxio(5) [debian man page]

mcxio(5)							   FILE FORMATS 							  mcxio(5)

      mcxio - the format specifications for input and output in the mcl family.

      The primary objects in the MCL network analysis suite are graphs and clusterings. Graphs can be directed and may have loops. Both graphs and
      clusterings are represented in a general unified format. This format specifies two domains (a source domain and a destination domain), along
      with  lists  of  arcs  linking  pairs  of elements from the two domains.	For graphs the two domains are simply both equal to the graph node
      domain, whereas for clusterings one domain is the graph node domain and the other corresponds to the  enumeration  of  clusters.	Undirected
      graphs  are  a special instance of a directed graph, where an edge from the undirected graph is represented by two arcs of identical weight,
      one for each possible direction.

      The general unified format alluded to above is in fact a simple rectangular sparse matrix representation.  Sparse means that zero entries in
      the matrix are not stored.  A zero entry corresponds to an ordered node pair in the graph for which no arc exists from the first to the sec-
      ond node.  An undirected graph corresponds with a symmetric matrix.

      The MCL suite uses a slight generalisation of the matrix concept, in that the row and column indices (that is,  domains)	can  be  arbitrary
      lists  of  nonnegative integers. Usually, but not necessarily, a domain of size N will use the common representation of the list of integers
      starting at 0 and ending at  N-1.  The source domain is always associated with the columns of a matrix, and the destination domain is always
      associated  with	the rows of a matrix. The matrix format, introduced below, first specifies the two domains. It then represents the nonzero
      matrix entries (corresponding with graph arc weights) in a column-wise fashion, as a list of lists. For each node from the source domain, it
      presents the list of all its neighbours in the destination domain along with the corresponding weights.  This document describes

      native matrix format
	The  format  that  can	be  read  in by any mcl application expecting a matrix argument. The native format closely resembles the layout of
	matrices as residing in computer memory. There are two distinct encodings, respectively interchange and binary.  Their relative merits are
	described further below.

      concatenated native matrix format
	This  always  pertains	to  matrices  in  native format concatenated in a single file, refered to as a cat file. It is used for example to
	encode hierarchical clusterings as generated by mclcm. A cat file either consists of matrices in interchange  format  or  of  matrices	in
	binary format.

      raw intermediate format
	This is read by mcxassemble(1).

      tab format
	Used  by applications such as mcl(1) and mcxdump(1) to convert between meaningful labels describing the input data and the numerical iden-
	tifiers used internally.

      label format
	The format used when streaming labels directly into mcl(1) or mcxload(1).

      transformation syntax
	The syntax accepted by mcl(1), mcxalter(1) and many other programs to transform graphs and matrices.

      The interchange format is a portable format that can be transmitted across computers and over networks and will work with any version of mcl
      or  its sibling programs. It is documented (here) and very stable.  Applications can easily create matrices in this format.  The drawback of
      interchange format is that for very large graphs matrix encodings grow very big and are slow to read.

      The binary format is not garantueed to be portable across machines or different versions of mcl or differently compiled versions of mcl. Its
      distinct advantage is that for very large graphs the speed advantage over interchange format is dramatic.

      Conversion  between  the two formats is easily achieved with mcxconvert. Both mcl(1) and mcxload(1) can save a matrix in either format after
      constructing it from label input.

      The concatenated format is generated e.g. by mclcm(1) and can be transformed by mcxdump(1) using the -imx-cat option. In cat format matrices
      are simply concatenated, so it is easily generated from the command line if needed.  For native binary format it is imperative that no addi-
      tional bytes are inserted inbetween the matrix encodings. For native interchange format the only requirement is that the last matrix is fol-
      lowed by nothing but white space.

      A  remark  on  the sloppy naming conventions used for mcl and its sibling utilities may be in order here. The prefix mcx is used for generic
      matrix functionality, the prefix clm is used for generic cluster functionaliy. The utility mcx is a general purpose interpreter for  manipu-
      lating matrices (and grahps, sets, and clusterings). The set of all mcl siblings (cf. mclfamily(7)) is loosely refered to as the mcl family,
      which makes use of the mcl libraries (rather than the mcx libraries). The full truth is even more horrible, as the  mcl/mcx  prefix  conven-
      tions used in the C source code follow still other rules.

      In  this document, 'MCL' means 'the mcl setting' or 'the mcl family'. An MCL program is one of the programs in the mcl family. The remainder
      of this document contains the following sections.

  Internal representation of matrices in MCL
      There are several aspects to the way in which MCL represents matrices.  Internally, indices never act as an ofset in an array,  and  neither
      do  they	participate  in  ofset computations. This means that they purely act as identifiers. The upshot is that matrices can be handled in
      which the index domains are non-sequential (more below). Thus one can work with different graphs and matrices all using subsets of the  same
      set  of indices/identifiers. This aids in combining data sets in different ways and easily comparing the respective results when experiment-
      ing. Secondly, only nonzero values (and their corresponding indices) are stored. Thirdly, MCL stores a matrix as a listing of columns. Iter-
      ating  over a column is trivial; iterating over a row requires a costly transposition computation.  The last two points should matter little
      to the user of MCL programs.

      In textbook expositions and in many matrix manipulation implementations, matrices are represented with sequentially indexed  rows  and  col-
      umns,  with the indices usually starting at either zero or one. In the MCL setting, the requirement of sequentiality is dropped, and it fol-
      lows naturally that no requirement is posed on the first index. The only requirement MCL poses on the indices is that they  be  nonnegative,
      and can be represented by the integer type used by MCL. On many machines, the largest allowable integer will be 2147483647.

      MCL  associates  two  domains with a matrix M, the row domain and column domain. The matrix M can only have entries M[i,j] where i is in the
      row domain and j is in the column domain. This is vital when specifying a matrix: it is illegal to specify an  entry M[i,j]  violating  this
      condition. However, it is not necessary to specify all entries M[i,j] for all possible combinations of i and j. One needs only specify those
      entries for which the value is nonzero, and only nonzero values will be stored internally. In the MCL matrix format, the matrix domains must
      be specified explicitly if they are not canonical (more below).

      Strictly	as  an	aside, the domains primarily exist to ensure data integrity. When combining matrices with addition or multiplication (e.g.
      using the mcx utility), MCL will happily combine matrices for which the domains do not match, although it  will  usually	issue  a  warning.
      Conceptually,  matrices auto-expand to the dimensions required for the operation. Alternatively, a matrix can be viewed as an infinite quad-
      rant, with the domains delimiting the parts in which nonzero entries may exist.  In the future, facilities could be added to MCL (c.q.  mcx)
      to allow for placing strict domain requirements on matrices when submitted to binary operations such as addition and multiplication.

  Specifying matrices
      From here on, all statements about matrices and graphs are really statements about matrices and graphs in the MCL setting. The specification
      of a matrix quite closely matches the internal representation.

      A matrix M has two domains: the column domain and the row domain. Both simply take the form of a set (represented as  an	ordered  list)	of
      indices.	A canonical domain is a domain of some size K where the indices are simply the first K nonnegative integers 0,1..,K-1. The domains
      dictate which nonzero entries are allowed to occur in a matrix; only entries M[i,j] are allowed where i is in the row domain and j is in the
      column domain.

      The matrix M is specified in three parts, for which the second is optional.  The parts are:

      Header specification
	This  specifies  the  dimensions K and L of the matrix, where K is the size of the row domain, and L is the size of the column domain.	It
	looks as follows:

	mcltype matrix
	dimensions 9x14

	This dictates that a matrix will be specified for which the row domain has dimension 9 and the column domain has dimension 14.

      Domain specification
	The domain specification can have various forms: if nothing is specified, the matrix will have canonical domains and a canonical represen-
	tation,  similar  to  the  representation  encountered in textbooks. Alternatively, the row and column domains can each be specified sepa-
	rately, and it is also possible to specify only one of them; the other will simply be a canonical domain again. Finally, it is possible to
	declare  the  two  domains identical and specify them simultaneously. It is perfectly legal in each case to explicitly specify a canonical
	domain. It is required in each case that the number of indices listed in a domain corresponds with the dimension given in the header.

	An example where both a row domain and a column domain are specified:

	 100 200 300 400 500 600 700 800 900 $
	 30 32 34 36 38 40 42 44 46 48 50 52 56 58 $

	This example combines with the header given above, as the dimensions fit.  Had the row domain specification been omitted, the  row  domain
	would automatically be set to the integers 0,1,..8. Had the column specification been omitted, it would be set to 0,1,..13.

	Suppose  now that the header did specify the dimensions 10x10.	Because the dimensions are identical, this raises the possibility that the
	domains be identical.  A valid way to specify the row domain and column domain in one go is this.

	 11 22 33 44 55 66 77 88 99 100 $

      Matrix specification
	The matrix specification starts with the sequence


	The 'begin' keyword in the '(mclmatrix' part is followed by a list of listings, where the primary list ranges over all column indices in M
	(i.e.  indices in the column domain), and where each secondary lists encodes all positive entries in the corresponding column. A secondary
	list (or matrix column) starts with the index c of the column, and then contains a listing of all row  entries	in  c  (these  are  matrix
	entries  M[r,c]  for varying r). The entry M[r,c] is specified either as 'r' or as 'r:f', where f is a float. In the first case, the entry
	M[r,c] defaults to 1.0, in the second case, it is set to f. The secondary list is closed with the `$' character. A full  fledged  examples
	thus looks as follows:

	mcltype matrix
	dimensions 12x3
	 11 22 33 44 55 66 77 88 99 123 456 2147483647 $
	  0  1	2 $
	0    44 88 99 456 2147483647 $
	1    11 66 77 123 $
	2    22 33 55 $

	Note  that  the column domain is canonical; its specifiation could have been omitted. In this example, no values were specified. See below
	for more.

  Specifying graphs
      A graph is simply a matrix where the row domain is the same as the column domain. Graphs should have positive entries only. Example:

      mcltype matrix
      dimensions 12x12
      11 22 33 44 55 66 77 88 99 123 456 2147483647 $
      11    22:2  66:3.4  77:3	123:8 $
      22    11:2  33:3.8  55:8.1 $
      33    22:3.8  44:7  55:6.2 $
      44    33:7  88:5.7  99:7.0 456:3 $
      55    22:8.1  33:6.2  77:2.9  88:3.0 $
      66    11:3.4  123:5.1 $
      77    11:3  55:2.9  123:1.5 $
      88    44:5.7  55:3.0  99:3.0 456:4.2 $
      99    44:7.0  88:3.0 456:1.8 2147483647:3.9 $
      123   11:8  66:5.1  77:1.5 $
      456   44:3  88:4.2  99:1.8 2147483647:6.3 $
      2147483647   99:3.9 456:6.3 $

      Incidentally, clustering this graph with mcl, using default parameters, yields a cluster that is represented by the 12x3 matrix  shown  ear-

      The following example shows the same graph, now represented on a canonical domain, and with all values implicitly set to 1.0:

      mcltype matrix
      dimensions 12x12
      0    1  5  6  9 $
      1    0  2  4 $
      2    1  3  4 $
      3    2  7  8 10 $
      4    1  2  6  7 $
      5    0  9 $
      6    0  4  9 $
      7    3  4  8 10 $
      8    3  7 10 11 $
      9    0  5  6 $
      10   3  7  8 11 $
      11   8 10 $

      Additional notes
      There are few restrictions on the format that one might actually expect.	Vectors and entries may occur in any order and need not be sorted.
      Repeated entries and repeated vectors are allowed but are always discarded while an error message is emitted.

      If you want functionally interesting behaviour in combining repeated vectors and repeated entries, have a look at the next  section  and	at

      Within the vector listing, the '#' is a token that introduces a comment until the end of line.

  Raw format
      A  file in raw format is simply a listing of vectors without any sectioning structure. No header specification, no domain specification, and
      no matrix introduction syntax is used - these are supplied to the processing application by other means. The end-of-vector  token  '$'  must
      still  be used, and the comment token '#' is still valid. mcxassemble(1) imports a file in raw format, creates a native matrix from the data
      therein, and writes the matrix to (a different) file. It allows customizable behaviour in how to combine repeated entries and repeated  vec-
      tors. This is typically used in the following procedure. A) Do a one-pass-parse on some external cooccurrence file/format, generate raw data
      during the parse and write it to file (without needing to build a huge data structure in memory). B) mcxassemble	takes  the  raw  data  and
      assembles it according to instruction into a native mcl matrix.

  Tab format / label information
      Several  mcl  programs  accept options such as -tab, -tabc, -tabr, -use-tab, -strict-tab, and -extend-tab.  The argument to these options is
      invariably the name of a so-called tab file.  Tab files are used to convert between labels (describing entities in the data) and indices	as
      used  in	the  mcl  matrix  format.   In a tab file each line starts with a unique number which presumably corresponds to an index used in a
      matrix file.  The rest of the line contains a descriptive string associated with the number. It is required  that  each  string  is  unique,
      although	not  all  mcl  programs enforce this at the time of writing.  The string may contain spaces.  Lines starting with # are considered
      comment and are disregarded.

      Tab domain
      The ordered set of indices found in the tab file is called the tab domain.

      Tab files are almost always employed in conjunction with an mcl matrix file.  mcxdump(1) and clmformat(1) require by default  that  the  tab
      domain coincides with the matrix domain (either row or column or both) to which they will be applied. This can be relaxed for either by sup-
      plying the --lazy-tab option.

      mcl provides explicit modes for dealing with tab structures by means of the -extend-tab, -restrict-tab and -strict-tab options. Refer to the
      mcl(1) documentation.

  Label input
      Label input is a line based input where two nodes and an optional value are specified on each line. The nodes should be specified by labels.
      If the labels contain spaces they should be separated by tabs (and the value if present should be separated from the second label by  a  tab
      as  well). The parse code will assume tab-separated labels if it sees a tab character in the input, otherwise it will split the input on any
      kind of whitespace.  Any line where the first non-whitespace character is the octothorp (#) is ignored. The following is an example of label

      # the cat and the hat example
      cat hat  0.2
      hat bat  0.16
      bat cat  1.0
      bat bit  0.125
      bit fit  0.25
      fit hit  0.5
      hit bit  0.16

      mcl(1) can read in label input and cluster it when it is given the --abc option. It can optionally save the input graph in native format and
      save the label information in a tab file with the -save-graph and -save-tab options.

      Refer to the MCL getting started and MCL manual examples sections for more information on how MCL deals with label input.

      mcxload(1) is a general purpose program for reading in label data and other stream formats. It encodes them in native  mcl  format  and  tab
      files.  It allows intermediate transformations on the values.

  Transformation syntax
      mcl(1),  mcxload(1),  mcxsubs(1),  mcxassemble(1)  and  mcxalter(1)  all accept the same transformation language in their respective tf-type
      options and mcxsub's val specification.

      A statement in this language is simply a comma-separated list of functions accepting a single numerical value.  The  syntax  of  a  function
      invocation in general is func(arg).  The functions exp, log, neglog can also be given an empty parameter list, indicating that e is taken as
      the exponent base. In this case, the invocation looks like func().  Functions with names that start  with  #  operate  on  graphs  in  their
      entirety.  For  example,	#knn(50) indicates the k-Nearest Neighbour transformation for k=50.  All other names encode functions that operate
      directly on edges.  Functions with names that start with #arc operate on directed graphs and yield directed graphs.  Most  of  the  other  #
      functions  either  expect  an  undirected graph (such as #knn()) or yield an undirected graph (such as #add() and #max().  The following are

      lt       Filter out values greater than or equal to arg.
      lq       Filter out values greater than arg.
      gq       Filter out values less than arg.
      gt       Filter out values less than or equal to arg.
      ceil     Set everything higher than arg to arg.
      floor    Set everything lower than arg to arg.
      mul      Multiply by arg.
      add      Add arg to it.
      power    Raise to power arg.
      exp      Raise arg (e if omitted) to value.
      log      Take log in base arg (e if omitted).
      neglog   Take minus log in base arg (e if omitted).
      #knn     k-Nearest Neighbour reduction with k=arg.
      #ceilnb  Cap neighbours at arg at most.
      #mcl     Cluster with inflation=arg, use induced graph.
      #add     Convert two arcs to one edge using addition.
      #min     Convert two arcs to one edge using minimum.
      #max     Convert two arcs to one edge using maximum.
      #mul     Convert two arcs to one edge using multiplication.
      #rev     Encode graph in reverse direction.
      #tp      Same as above in matrix speak (transpose).
      #tug     Perturb edge weights with factor arg.
      #shrug   Randomly perturb edge weights with factor arg.
      #step    Use the k-step relation, where k=arg.
      #thread  Set thread pool size to arg.
      #arcmax  Only keep largest arc between two nodes.
      #arcsub  Replace G by G - G^T.
      #arcmcl  As #mcl, use symmetrised graph for clustering.

      mcl(1) accepts --abc-neg-log and --abc-neg-log10 to specify log transformations. Similarly, mcxload(1) accepts  --stream-log,  --stream-neg-
      log,  and --stream-neg-log10. The reason is that probabilities are sometimes encoded below the precision dictated by the IEEE (32 bit) float
      specification. This poses a problem as the mcl applications encode values by default as floats, and the  transformation  specifications  are
      always applied to the mcl encoding. The options just mentioned are applied after a value has been read from an input stream and before it is
      converted to the native encoding.

      mcxassemble(1), and mclfamily(7) for an overview of all the documentation and the utilities in the mcl family.

      Stijn van Dongen.

  mcxio 12-068							      8 Mar 2012							    mcxio(5)
Man Page

Featured Tech Videos