how to reindex a sparse associative array

Question

first off, this question is not related to a specific language - I use Haxe to target multiple platforms - so a pseudo code will be more than enough.

here's my problem : I have a sparse Matrix description in this form:

edges = 
[
1,1,2,1,3,1,4,1,
2,2,3,2,
3,3,4,3,5,3,
4,4,5,4,6,4,
5,5,6,5,7,5,25,5,27,5,28,5,29,5,30,5
];

this describes edges associations:

• point 1 is linked to points 1, 2, 3 & 4
• point 2 is linked to points 2 & 3
• point 3 is linked to points 3, 4 & 5
• point 4 is linked to points 4, 5 & 6
• point 5 is linked to points 5, 6, 7, 25, 27, 28, 29 & 30

now I need to render this in 3D and to do so, I need to "compress" the data into an index buffer without "gaps". say with the above example, I'd need to get :

newEdges = 
[ 
1,2, 1, 3, 1, 4,
2,3,
3,4, 3,5,
4,5, 4,6,
5,6, 5,7, 5,8, 5,9, 5,10, 5,11, 5,12
]

so, the edge linking themselves (edge 1-1, 2-2, 3-3 etc. ) must be removed (easy).

as the point order is not important ( the edge 1-2 = edges 2-1 ) we shall also remove the duplicate edges (sort of easy).

now the tricky part is to remove the "gaps": as 7 was the highest consecutive value and 25 is the one right after, 25 must become 8, 27 must become 9, 28 must become 10 and so on.

for now I'm using a BitmapData in which I plot all the values as XY coordinates. then I recursively copy the non empty vertical stripes (1 pixel wide rect) of this bitmap next to each other into a temporary bitmap. then I do the same for the horizontal stripes and finally scan my bitmap and store X & Y values of the pixels as edges' IDs.

and it works!( at least it seems to :) ) but the overhead is terrible and depending on the input Matrix, I might just not be able to generate the Bitmaps (for instance flash is limited to 4092 pixels max, JS doesn't support copyPixels very well).

so the question is how would you do this "gap removal" without bitmaps and without a language-specific method?

hoping this was explicit enough, thanks for your attention.

Nicolas

Answer 1

Let E[m+1][m+1] be the 2-dimensional adjacency matrix corresponding to edges, where the range of point indices is [0..m].

Let f[n] be a sorted array of the n points visited in edges. By creating the f[n] array we're creating a mapping between the non-contiguous point indices in the range [0..m] and the contiguous point indices from [0..n-1].

Create a new adjacency matrix G as follows:

for i = 0..(n-1)
    for j = 0..(n-1)    // or, j = (i+1)..(n-1) for upper triangular portion
        G[i][j] = E[f[i]][f[j]]
    end
end

This will only take O(n^2) rather than O(m^2) time.

Edit: Removed the if statement. If both E and G are initialized to all 0's it's unnecessary.