As I See Tech

Data collection is highly valued. There are businesses focused on profiting from them. Data analysts and data scientists are the new careers to aim for. It's not just about big data anymore. It's now about really putting them to work, with the ultimate manifestation building what is known as artificial intelligence.

This article serves as the Mendz.Graphs series ToC (Table of Contents). Consider bookmarking for a quick and easy reference.

If you can compress them, you can decompress them, right? Decompression helps to validate the compression. In this article, I'll explore how CVS, CRS and CCS can be decompressed to a two-dimensional array T[,] dense matrix.

The CVSExtensions, CRSExtensions and CCSExtensions serve as my placeholders for compressed matrix operations. This article focuses on matrix-vector multiplication.

In .Net, extension methods are fantastic ways of adding new features to types that can share the same behavior (static methods) without necessarily changing the types' source codes. Extension methods can be maintained in separate code files. IDOKSparseMatrixExtensions provides extension methods to sparse matrices that implement IDOKSparseMatrix.

When I discussed about compressed matrices , I mentioned two common compressed matrix formats, CRS and CCS, and described a third one I called CVS. These compressed matrices are supported in Mendz.Library.Matrices.

Mendz.Library.Matrices abstracted the sparse matrix via IDOKSparseMatrix and DOKSparseMatrixBase . Now it's time to create the classes DOKSparseMatrix and DOKConcurrentSparseMatrix. From these, the coordinates keyed and linear index keyed concrete classes will be created. If you've been waiting for it, note that Mendz.Graphs..Sparse matrices use CoordinatesKeyedConcurrentSparseMatrix , which is described in this article.

After much self-deliberation, I decided that the sparse matrix must be abstracted. The primary inspiration of the sparse matrix's design in Mendz.Graphs came from Wolfram where the SparseArray is shown as a collection of coordinates and their values ((0, 0) -> 1, (3, 1) -> 3, (7, 5) -> 5, ...).

Once upon a time, there was a problem that inspired a quest. That quest created Mendz.Graphs, which is now a .Net Core class library that grew from a simple implementation of G = (V, E) in to one that also provides features to represent a graph as a list, a dense matrix, a sparse matrix and, quite recently, a compressed matrix.

The connection matrix is a (true, false, false)-adjacency matrix, implemented in Mendz.Graphs.Representation.Matrices namespace as the ConnectionMatrix.

In Mendz.Graphs, you should find that the AdjacencyMatrix, WeightedAdjacencyMatrix and GenericAdjacencyMatrix classes are coded pretty much the same way. In fact, they are essentially coded exactly alike, with only the namespaces different. Why is this so, Mendz?

Looking at Mendz.Graphs, you can clearly see how repeatable coding patterns are celebrated. Take note, I didn't say repeating codes. I said, repeatable coding patterns. Maintenance-wise, it makes a lot of difference.

Mendz.Graphs provides a set of concrete sparse matrix implementations. Compared to dense matrices, sparse matrices save on memory by using only what's needed to represent the graph.

The incidence matrix is a rectangular matrix which entries can vary depending on whether the graph is directed or undirected, and whether the incidence matrix is oriented or not. The sparse version applies the same logic used by the dense version.

Come to think of it, the degree matrix and its variations are really sparse. Implementing the degree matrix as a sparse matrix just makes absolute sense!

If there is a Mendz.Graphs..Dense.GenericAdjacencyMatrix, there should definitely be a Mendz.Graphs..Sparse.GenericAdjacencyMatrix!

With the AdjacencyMatrixBase in place, variations of the adjacency matrix can be easily implemented.

In Mendz.Graphs, representing graphs as matrices follow similar coding patterns. This is basically because they all derive from the GraphMatrixBase class. Thus, it shouldn't be surprising to see that the codes for sparse matrices look a lot like their dense matrix counterparts.

In the previous series, I covered the dense matrices in Mendz.Graphs, which implement them as two-dimensional arrays T[,]. They work good, really... that is, until you start loading graphs with a very large collection of vertices and edges.

Mendz.Graphs provides a set of concrete dense matrix implementations that can be used in operations that support two-dimensional arrays (T[,]).