Replace 2D-matrix by "double-index List<>"?-CodePudding

I'm implementing the Floyd-Warshal algorithm from

There are about 600 vertices in my graph, and having a 600x600 matrix might blow up my memory, so I'm looking for a datatype, like a double_index_List<int> where I could do something like:

double_index_List<int> graph_connections = new double_index_List<int>();
for (int index=0, index <= 600; index  )
    graph_connections.insertAt(index,index) = 0;

// make the connections between all subsequent points
graph_connections.insertAt(1, 2)   = 5000;
graph_connections.insertAt(2, 3)   = 5100;
graph_connections.insertAt(3, 4)   =  600;
...
graph_connections.insertAt(600, 1) = 4800;

// foresee the possibility that some non-subsequent vertices in the graph are reachable.
graph_connections.insertAt(100,  20) = 4200;
graph_connections.insertAt(200, 124) =  500;
graph_connections.insertAt(320, 240) =  600;
...
graph_connections.insertAt(600, 540) =  480;

The idea is that I have a function, like:

// Explanation: If graph_connections(x, y) has been created, then return that entry. 
//              If not, return the default value (being `INF`).
graph_connections.get(x, y, INF)

Does such "doubly indexed List" or "double-index List" exist in C#?

CodePudding user response：

having a 600x600 matrix might blow up my memory

Why? such a matrix should only require 1.44Mb of memory, that should really not be a problem, even on 32 bit systems.

Does such "doubly indexed List" or "double-index List" exist in C#?

What you are describing is essentially a sparse matrix, there is no such builtin. But you might want to take a look at Math.Net SparseMatrix.

However, it would not be very difficult to write your own based on a dictionary

var mySparseMatrix = new Dictionary<(int x, int y), int>();
mySparseMatrix[(1, 2)]   = 5000;
var value = mySparseMatrix.TryGet((1, 2), out var r) ? r : 0

Note that ValueTuple that this uses does not have a good GetHashCode implementation, so the performance of this will be poor. You should probably implement your own Point/Vector2i type with GetHashCode & Equals implemented. Or maybe use System.Drawing.Point. You should probably also wrap the dictionary in a custom class to provide the interface you want.