Simple sparse matrix data structure. More...

Inheritance diagram for aud.graph.matrix.SparseMatrixCS< T >:

Collaboration diagram for aud.graph.matrix.SparseMatrixCS< T >:

Public Member Functions
	SparseMatrixCS ()
	create empty matrix with "arbitrarily growing" dimensions More...

	SparseMatrixCS (SparseMatrixCS< T > other)
	copy constructor More...

int	nnz ()
	get number of nonzero entries More...

int	getNumRows ()
	computes from maximium row index [O(`nnz`)] More...

int	getMinRowIndex ()
	get minimum row index [O(`nnz`)] More...

int	getNumColumns ()
	computed from maximum column index [O(1)] More...

int	getMinColumnIndex ()
	get minimum row index [O(1)] More...

T	get (int i, int j)
	get entry (i,j) [O(log(`nnz`))] More...

T	set (int i, int j, T data)
	Set entry (i,j) to data [O(log(`nnz`))]. More...

Vector< T >	getColumnEntries (int j)
	get entries in column j as array More...

int[]	getColumnRowIndices (int j)
	get row indices in column j as array More...

int	columnDegree (int j)
	get number of nonzero entries in column j More...

SparseMatrixCS< T >	getTransposed ()
	get transposed matrix More...

SparseMatrixCS< Integer >	spones ()
	Get nonzero pattern. More...

int[]	getRowIndices ()
	Get array of row indices. More...

int[]	getColumnIndices ()
	Get array of column indices in same order as for `getRowIndices`. More...

T[]	getValues ()
	Get array of values in same order as for `getRowIndices`. More...

String	toString ()

String	toLaTeX (String name)
	get LaTeX code for displaying (TikZ) matrix More...

File	renderSpySVG (File svgfile, Colormap< T > colormap)

String	spyTikZ (boolean rulers, Colormap< T > colormap)

SVGViewer	spy (String caption, Colormap< T > colormap)
	render spy plot in new window More...

Protected Attributes
TreeMap< Coordinate, T >	mat_

Detailed Description

Simple sparse matrix data structure.

This data structure is intended for sparse storage: it stores only non-null entries, i.e., the required amount of storage is O(nnz) (not O(m*n))).

SparseMatrixCS stores and retrieves columns efficiently. The retrieval of rows is not supported.
The matrix has potentially infinite dimensions. (Dimension is determined by the maximium row and column indices for all entries. We don't require this property for adjacency matrices.
The implementation is based on a simplified compressed column storage (CCS) scheme based on sorted tuples in a TreeMap.

Definition at line 36 of file SparseMatrixCS.java.

Constructor & Destructor Documentation

◆ SparseMatrixCS() [1/2]

aud.graph.matrix.SparseMatrixCS< T >.SparseMatrixCS ( )

create empty matrix with "arbitrarily growing" dimensions

Definition at line 42 of file SparseMatrixCS.java.

                          {
    mat_=new TreeMap<Coordinate,T>();
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

◆ SparseMatrixCS() [2/2]

aud.graph.matrix.SparseMatrixCS< T >.SparseMatrixCS ( SparseMatrixCS< T > other )

copy constructor

Definition at line 46 of file SparseMatrixCS.java.

                                                 {
    mat_=new TreeMap<Coordinate,T>(other.mat_);
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Member Function Documentation

◆ columnDegree()

int aud.graph.matrix.SparseMatrixCS< T >.columnDegree ( int j )

get number of nonzero entries in column j

Exceptions

IndexOutOfBoundsException on error (non-positive index)

Returns: length of getColumnEntries

Definition at line 155 of file SparseMatrixCS.java.

155{ return getColumnEntries(j).size(); }

aud.graph.matrix.SparseMatrixCS.getColumnEntries

Vector< T > getColumnEntries(int j)

get entries in column j as array

Definition: SparseMatrixCS.java:123

References aud.graph.matrix.SparseMatrixCS< T >.getColumnEntries().

Referenced by aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), and aud.test.SparseMatrixTest.testSymmatrixMatrix().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get()

T aud.graph.matrix.SparseMatrixCS< T >.get	(	int	i,
		int	j
	)

get entry (i,j) [O(log(nnz))]

Exceptions

IndexOutOfBoundsException (non-positive indices)

Returns: entry or null

Definition at line 90 of file SparseMatrixCS.java.

                            {
    return check(i,j).get(new Coordinate(i,j));
  }

Referenced by aud.test.AdjacencyMatrixTest.testMatrix(), aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), aud.test.AdjacencyMatrixTest.testSymmatrixMatrix(), and aud.test.SparseMatrixTest.testSymmatrixMatrix().

Here is the caller graph for this function:

◆ getColumnEntries()

Vector< T > aud.graph.matrix.SparseMatrixCS< T >.getColumnEntries ( int j )

get entries in column j as array

Exceptions

IndexOutOfBoundsException on error (non-positive index)

Definition at line 123 of file SparseMatrixCS.java.

                                           {
    SortedMap<Coordinate,T> sub=
      check(1,j).subMap(new Coordinate(-1,j),
                        new Coordinate(Integer.MAX_VALUE,j));
    Object[] a=sub.values().toArray();
    Vector<T> v=new Vector<T>();
    v.reserve(a.length);
    for (int i=0;i<a.length;++i)
      v.push_back((T) a[i]);
    return v;
  }

Referenced by aud.graph.matrix.SparseMatrixCS< T >.columnDegree(), aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), and aud.test.SparseMatrixTest.testSymmatrixMatrix().

Here is the caller graph for this function:

◆ getColumnIndices()

int[] aud.graph.matrix.SparseMatrixCS< T >.getColumnIndices ( )

Get array of column indices in same order as for getRowIndices.

Definition at line 198 of file SparseMatrixCS.java.

                                  {
    int[] ci=new int[nnz()];
    int i=0;
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet())
      ci[i++]=entry.getKey().j;
    return ci;
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_, and aud.graph.matrix.SparseMatrixCS< T >.nnz().

Here is the call graph for this function:

◆ getColumnRowIndices()

int[] aud.graph.matrix.SparseMatrixCS< T >.getColumnRowIndices ( int j )

get row indices in column j as array

Exceptions

IndexOutOfBoundsException on error (non-positive index)

Definition at line 138 of file SparseMatrixCS.java.

                                          {
    SortedMap<Coordinate,T> sub=
      check(1,j).subMap(new Coordinate(-1,j),
                        new Coordinate(Integer.MAX_VALUE,j));
    int[] idx=new int[sub.size()];
    int i=0;
    for (Coordinate c : sub.keySet()) {
      idx[i++]=c.i;
    }
    assert(i==idx.length);
    return idx;
  }

Referenced by aud.graph.AdjacencyMatrix< Edge >.clearColumnAndRow(), aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), and aud.test.SparseMatrixTest.testSymmatrixMatrix().

Here is the caller graph for this function:

◆ getMinColumnIndex()

int aud.graph.matrix.SparseMatrixCS< T >.getMinColumnIndex ( )

get minimum row index [O(1)]

Definition at line 74 of file SparseMatrixCS.java.

74{ return mat_.size()==0 ? 0 : mat_.firstKey().j; }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), aud.test.SparseMatrixTest.testSymmatrixMatrix(), and aud.graph.matrix.SparseMatrixCS< T >.toLaTeX().

Here is the caller graph for this function:

◆ getMinRowIndex()

int aud.graph.matrix.SparseMatrixCS< T >.getMinRowIndex ( )

get minimum row index [O(nnz)]

Reimplemented in aud.graph.matrix.SparseMatrix< T >.

Definition at line 63 of file SparseMatrixCS.java.

                              {
    int imin=Integer.MAX_VALUE;
    for (Coordinate c : mat_.keySet()) {
      if (c.i<imin)
        imin=c.i;
    }
    return (imin==Integer.MAX_VALUE) ? 0 : imin;
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.test.SparseMatrixCSTest.testMatrix(), and aud.graph.matrix.SparseMatrixCS< T >.toLaTeX().

Here is the caller graph for this function:

◆ getNumColumns()

int aud.graph.matrix.SparseMatrixCS< T >.getNumColumns ( )

computed from maximum column index [O(1)]

Definition at line 72 of file SparseMatrixCS.java.

72{ return mat_.size()==0 ? 0 : mat_.lastKey().j; }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.graph.matrix.SparseMatrixCS< T >.renderSpySVG(), aud.graph.matrix.SparseMatrixCS< T >.spyTikZ(), aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), aud.test.SparseMatrixTest.testSymmatrixMatrix(), and aud.graph.matrix.SparseMatrixCS< T >.toLaTeX().

Here is the caller graph for this function:

◆ getNumRows()

int aud.graph.matrix.SparseMatrixCS< T >.getNumRows ( )

computes from maximium row index [O(nnz)]

Reimplemented in aud.graph.matrix.SparseMatrix< T >.

Definition at line 54 of file SparseMatrixCS.java.

                          {
    int imax=0;
    for (Coordinate c : mat_.keySet()) {
      if (c.i>imax)
        imax=c.i;
    }
    return imax;
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.graph.matrix.SparseMatrixCS< T >.renderSpySVG(), aud.graph.matrix.SparseMatrixCS< T >.spyTikZ(), aud.test.SparseMatrixCSTest.testMatrix(), and aud.graph.matrix.SparseMatrixCS< T >.toLaTeX().

Here is the caller graph for this function:

◆ getRowIndices()

int[] aud.graph.matrix.SparseMatrixCS< T >.getRowIndices ( )

Get array of row indices.

See also: getColumnIndices; getValues

Definition at line 188 of file SparseMatrixCS.java.

                               {
    int[] ri=new int[nnz()];
    int i=0;
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet())
      ri[i++]=entry.getKey().i;
    return ri;
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_, and aud.graph.matrix.SparseMatrixCS< T >.nnz().

Here is the call graph for this function:

◆ getTransposed()

SparseMatrixCS< T > aud.graph.matrix.SparseMatrixCS< T >.getTransposed ( )

get transposed matrix

Reimplemented in aud.graph.matrix.SparseMatrix< T >.

Definition at line 159 of file SparseMatrixCS.java.

                                           {
    SparseMatrixCS<T> m=new SparseMatrixCS<T>();
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet()) {
      Coordinate c=entry.getKey();
      m.mat_.put(new Coordinate(c.j,c.i),entry.getValue());
    }
    return m;
  }

References aud.graph.matrix.Coordinate.i, aud.graph.matrix.Coordinate.j, and aud.graph.matrix.SparseMatrixCS< T >.mat_.

◆ getValues()

T[] aud.graph.matrix.SparseMatrixCS< T >.getValues ( )

Get array of values in same order as for getRowIndices.

Definition at line 208 of file SparseMatrixCS.java.

                         {
    T[] values=(T[]) new Object[nnz()];
    int i=0;
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet())
      values[i++]=entry.getValue();
    return values;
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_, and aud.graph.matrix.SparseMatrixCS< T >.nnz().

Here is the call graph for this function:

◆ nnz()

int aud.graph.matrix.SparseMatrixCS< T >.nnz ( )

get number of nonzero entries

Definition at line 51 of file SparseMatrixCS.java.

51{ return mat_.size(); }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.graph.matrix.SparseMatrixCS< T >.getColumnIndices(), aud.graph.matrix.SparseMatrixCS< T >.getRowIndices(), aud.graph.matrix.SparseMatrixCS< T >.getValues(), aud.test.AdjacencyMatrixTest.testMatrix(), aud.test.SparseMatrixCSTest.testMatrix(), aud.test.SparseMatrixTest.testMatrix(), aud.test.AdjacencyMatrixTest.testSymmatrixMatrix(), and aud.test.SparseMatrixTest.testSymmatrixMatrix().

Here is the caller graph for this function:

◆ renderSpySVG()

File aud.graph.matrix.SparseMatrixCS< T >.renderSpySVG	(	File	svgfile,
		Colormap< T >	colormap
	)

Definition at line 249 of file SparseMatrixCS.java.

                                                              {
    if (colormap==null)
      colormap=new Colormap<T>();
 
    try {
      FileOutputStream f=new FileOutputStream(svgfile);
 
      // write header
      float sz=5.0f; // cell size
      float r=2.0f;  // radius
      float w=(getNumColumns()+1)*sz, h=(getNumRows()+1)*sz;
 
      String buf=
        "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"+
        "<svg xmlns=\"http://www.w3.org/2000/svg\"\n"+
        " width=\""+w+"mm\"\n"+
        " height=\""+h+"mm\"\n"+
        " version=\"1.1\"\n>\n\n";
      f.write(buf.getBytes());
 
      // rulers
      f.write(("<line x1=\""+0+"mm\" y1=\""+(sz-r)+
               "mm\" x2=\""+w+"mm\" y2=\""+(sz-r)+"mm\" "+
               "style=\"stroke:#000000;stroke-width:1pt\"/>\n").getBytes());
      for (int i=1;i<=getNumColumns();++i) {
        float x=sz*(0.5f+i);
        f.write(("<line x1=\""+x+"mm\" y1=\""+(r)+
                 "mm\" x2=\""+x+"mm\" y2=\""+(r+r)+"mm\" "+
                 "style=\"stroke:#000000;stroke-width:1pt\"/>\n").getBytes());
      }
      f.write(("<line x1=\""+(sz-r)+"mm\" y1=\""+0+
               "mm\" x2=\""+(sz-r)+"mm\" y2=\""+h+"mm\" "+
               "style=\"stroke:#000000;stroke-width:1pt\"/>\n").getBytes());
      for (int i=1;i<=getNumRows();++i) {
        float y=sz*(0.5f+i);
        f.write(("<line x1=\""+(r)+"mm\" y1=\""+y+
                 "mm\" x2=\""+(r+r)+"mm\" y2=\""+(y)+"mm\" "+
                 "style=\"stroke:#000000;stroke-width:1pt\"/>\n").getBytes());
      }
      f.write("\n\n".getBytes());
 
      // data
      for (Map.Entry<Coordinate,T> entry : mat_.entrySet()) {
        float x=sz*(0.5f+entry.getKey().j), y=sz*(0.5f+entry.getKey().i);
        String fill=String.format("%06x",colormap.getRGB(entry.getValue()));
 
        buf="<circle style=\"fill:#"+fill+";stroke:#000000;stroke-width:0px\" "+
            "r=\""+r+"mm\" cx=\""+x+"mm\" cy=\""+y+"mm\"/>\n";
        f.write(buf.getBytes());
      }
 
      f.write("</svg>\n".getBytes());
      f.close();
    } catch (IOException e) {
      System.err.println("ERROR: "+e.getMessage());
      return null; // note: probably triggers NullPointerException
    }
    return svgfile;
  }

References aud.graph.matrix.SparseMatrixCS< T >.getNumColumns(), aud.graph.matrix.SparseMatrixCS< T >.getNumRows(), aud.util.Colormap< T >.getRGB(), and aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.graph.matrix.SparseMatrixCS< T >.spy().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set()

T aud.graph.matrix.SparseMatrixCS< T >.set	(	int	i,
		int	j,
		T	data
	)

Set entry (i,j) to data [O(log(nnz))].

Parameters

i	row index (>=0)
j	column index (>=0)
data	new value; if `data==null`, then the entry will be erased from the matrix.

Exceptions

IndexOutOfBoundsException on error (non-positive indices)a

Returns: old value (or null

Reimplemented in aud.graph.matrix.SparseMatrix< T >.

Definition at line 102 of file SparseMatrixCS.java.

102{ return _set(i,j,data); }

Referenced by aud.test.SparseMatrixCSTest.testMatrix().

Here is the caller graph for this function:

◆ spones()

SparseMatrixCS< Integer > aud.graph.matrix.SparseMatrixCS< T >.spones ( )

Get nonzero pattern.

Returns a matrix with integer entries that equal 1 for every nonzero entry. (Same as Matlab's spones).

Definition at line 173 of file SparseMatrixCS.java.

                                          {
    SparseMatrixCS<Integer> m=new SparseMatrixCS<Integer>();
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet())
      m.mat_.put(entry.getKey(),1);
    return m;
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.test.SparseMatrixCSTest.testMatrix().

Here is the caller graph for this function:

◆ spy()

SVGViewer aud.graph.matrix.SparseMatrixCS< T >.spy	(	String	caption,
		Colormap< T >	colormap
	)

render spy plot in new window

Definition at line 348 of file SparseMatrixCS.java.

                                                            {
    File tmp=null;
    try {
      tmp=File.createTempFile("aud-","svg");
    }
    catch (IOException e) {
      System.err.println("ERROR: "+e.getMessage());
      System.exit(-1);
    }
    tmp.deleteOnExit();
    renderSpySVG(tmp,colormap!=null ? colormap: new Colormap<T>());
 
    SVGViewer v=SVGViewer.displayWindow(tmp,caption!=null ? caption : "spy");
 
    return v;
  }

References aud.util.SVGViewer.displayWindow(), and aud.graph.matrix.SparseMatrixCS< T >.renderSpySVG().

Referenced by aud.graph.matrix.SparseMatrix< T >.main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ spyTikZ()

String aud.graph.matrix.SparseMatrixCS< T >.spyTikZ	(	boolean	rulers,
		Colormap< T >	colormap
	)

Definition at line 309 of file SparseMatrixCS.java.

                                                             {
    if (colormap==null)
      colormap=new Colormap<T>();
 
    String s="\\begin{tikzpicture}[dot/.style={draw=none,fill=c},scale=1]\n";
 
    if (rulers) {
      s+="  \\foreach \\y in {0,...,"+(getNumRows()-1)+"} {\n"+
         "     \\draw (-2.5pt,-\\y) -- (2.5pt,-\\y);\n"+
         "     \\node[left] at (-1ex,-\\y-0.5) {{\\scriptsize \\y}};\n"+
         "  }\n"+
         "  \\draw (0,0) -- (0,-"+getNumRows()+");\n\n"
         ;
      s+="  \\foreach \\x in {1,...,"+(getNumColumns())+"} {\n"+
      "     \\draw (\\x,-2.5pt) -- (\\x,2.5pt);\n"+
      "     \\node[above] at (\\x-0.5,0) {{\\scriptsize \\x}};\n"+
      "  }\n"+
      "  \\draw (0,0) -- ("+(getNumColumns())+",0);\n\n"
      ;
    }
 
    float sz=1;
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet()) {
      int rgb=colormap.getRGB(entry.getValue());
      float r=(float) (rgb>>16)/255.0f;
      float g=(float) ((rgb>> 8)&0xff)/255.0f;
      float b=(float) (rgb&0xff)/255.0f;
      s+="  \\definecolor{c}{rgb}{"+r+","+g+","+b+"}\n";
      float x=sz*(-0.5f+entry.getKey().j), y=-sz*(-0.5f+entry.getKey().i);
      s+="  \\draw[dot] ("+x+","+y+") circle (0.4" +
                ");\n";
    }
 
    s+="\\end{tikzpicture}\n";
    return s;
  }

References aud.graph.matrix.SparseMatrixCS< T >.getNumColumns(), aud.graph.matrix.SparseMatrixCS< T >.getNumRows(), aud.util.Colormap< T >.getRGB(), and aud.graph.matrix.SparseMatrixCS< T >.mat_.

Referenced by aud.graph.matrix.SparseMatrix< T >.main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toLaTeX()

String aud.graph.matrix.SparseMatrixCS< T >.toLaTeX ( String name )

get LaTeX code for displaying (TikZ) matrix

Definition at line 229 of file SparseMatrixCS.java.

                                     {
    String rv="\\matrix ("+name+") [matrix of math nodes]\n{\n";
    int m=getNumRows(),n=getNumColumns();
    Class<?> intclass=Integer.valueOf(1).getClass();
    for (int i=getMinRowIndex();i<=m;++i) {
      for (int j=getMinColumnIndex();j<=n;++j) {
        T v=get(i,j);
        if (v!=null) {
          rv+=" ";
          rv+=(v.getClass()==intclass) ? v.toString() : "1";
        }
        if (j!=n)
          rv+=" &";
      }
      rv+=" \\\\\n";
    }
    rv+="};\n";
    return rv;
  }

References aud.graph.matrix.SparseMatrixCS< T >.getMinColumnIndex(), aud.graph.matrix.SparseMatrixCS< T >.getMinRowIndex(), aud.graph.matrix.SparseMatrixCS< T >.getNumColumns(), and aud.graph.matrix.SparseMatrixCS< T >.getNumRows().

Here is the call graph for this function:

◆ toString()

String aud.graph.matrix.SparseMatrixCS< T >.toString ( )

Definition at line 216 of file SparseMatrixCS.java.

                                     {
    String rv="[";
    for (Map.Entry<Coordinate,T> entry : mat_.entrySet()) {
      rv+=entry+" ";
    }
    return rv.trim()+"]";
  }

References aud.graph.matrix.SparseMatrixCS< T >.mat_.

Member Data Documentation

◆ mat_

TreeMap<Coordinate,T> aud.graph.matrix.SparseMatrixCS< T >.mat_

protected

Definition at line 38 of file SparseMatrixCS.java.

The documentation for this class was generated from the following file:

SparseMatrixCS.java

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SparseMatrixCS() [1/2]

◆ SparseMatrixCS() [2/2]

Member Function Documentation

◆ columnDegree()

◆ get()

◆ getColumnEntries()

◆ getColumnIndices()

◆ getColumnRowIndices()

◆ getMinColumnIndex()

◆ getMinRowIndex()

◆ getNumColumns()

◆ getNumRows()

◆ getRowIndices()

◆ getTransposed()

◆ getValues()

◆ nnz()

◆ renderSpySVG()

◆ set()

◆ spones()

◆ spy()

◆ spyTikZ()

◆ toLaTeX()

◆ toString()

Member Data Documentation

◆ mat_