Sorting rows of a sparse CSC matrix Golang

Question

I'm trying to analyze sparse matrices. Faced with the task of sorting rows in ascending order of the elements in them in the original matrix.

But I don't understand how to do this without damaging the empty elements.

I tried to bind the elements of the sum array to the rows and somehow move them. But some elements have been removed from the CSC structure.

It may be necessary to change the li/lj arrays themselves, but I don't have enough mathematical knowledge for this. More precisely, I don't understand how to track when elements should be rearranged unless additional elements (zeros) are explicitly specified in the structure.

package main

import (
    "fmt"
)

type CSC struct {
    a, lj, li []int
}

func getEl(i, j int, el *CSC) int {
    for k := el.lj[j]; k < el.lj[j+1]; k++ {
        if el.li[k] == i {
            return el.a[k]
        }
    }
    return 0
}

func maxSliceEl(lj []int) int {
    max := 0

    for _, v := range lj {
        if v > max {
            max = v
        }
    }
    return max
}

func main() {
    ma := CSC{
        a:  []int{8, 2, 5, 7, 1, 9, 2},
        li: []int{0, 0, 1, 4, 4, 6, 4},
        lj: []int{0, 1, 1, 4, 6, 7},
    }

    n := len(ma.lj) + 1
    m := maxSliceEl(ma.li) - 1
    fmt.Printf("Col: %v, Row: %v\n", n, m)

    maxStr := []int{}

    fmt.Println("Initial matrix:")
    for i := 0; i < n; i++ {

        sumStrEl := 0
        for j := 0; j < m; j++ {
            fmt.Print(getEl(i, j, &ma), " ")
            sumStrEl += getEl(i, j, &ma)
        }

        maxStr = append(maxStr, sumStrEl)
        fmt.Println("|sumStrEl: ", sumStrEl)
    }

}

Answer 1

I found a solution to the problem by taking the structure as a solution: the sum of the elements + their index. The solution turned out to be simpler than expected, only the practice of solving sparse matrices was lacking. The position [i] of the sum must be passed to the getEl function as the first parameter.

package main

import (
    "fmt"
    "sort"
)

// Creating a CSC (CCS) matrix structure
type CSC struct {
    // Array of values, column indexes, row indexing
    a, lj, li []int
}

// Getting access to the element
func getEl(i, j int, el *CSC) int {
    for k := el.lj[j]; k < el.lj[j+1]; k++ {
        // If the element string is equal to the string of the searched element, then the element is found
        if el.li[k] == i {
            return el.a[k]
        }
    }
    // Otherwise, we will return 0. It will be entered into the matrix
    return 0
}

func maxSliceEl(lj []int) int {
    max := 0

    for _, v := range lj {
        if v > max {
            max = v
        }
    }
    return max
}

type strInfo struct {
    summa int
    pos   int
}

func main() {
    // Set the CSC matrix
    ma := CSC{
        a:  []int{8, 2, 5, 7, 1, 9, 2},
        li: []int{0, 0, 1, 4, 4, 6, 4},
        lj: []int{0, 1, 1, 4, 6, 7},
    }

    // Define the number of columns
    n := len(ma.lj) + 1
    // Define the number of rows
    m := maxSliceEl(ma.li) - 1
    fmt.Printf("Cols: %v, Rows: %v\n", m, n)

    // Set a variable with a structure type for calculating 
    // the amount in a row and indexing each element in it
    var stringsInfo []strInfo

    fmt.Println("Initial matrix:")
    for i := 0; i < n; i++ {
        sumStrEl := 0

        for j := 0; j < m; j++ {
            sumStrEl += getEl(i, j, &ma)
            fmt.Print(getEl(i, j, &ma), " ")
        }
        fmt.Println("|", sumStrEl)

        // Adding a cell with the sum and index to the slice
        var strI strInfo
        strI.summa = sumStrEl
        strI.pos = i
        stringsInfo = append(stringsInfo, strI)
    }

    fmt.Println("stringsInfo: ", stringsInfo)

    // Sorting the stringsInfo slice in ascending order of the sum elements
    sort.Slice(stringsInfo, func(i, j int) (less bool) {
        return stringsInfo[i].summa < stringsInfo[j].summa
    })

    fmt.Println("stringsInfo: ", stringsInfo)

    fmt.Println("Sorted matrix:")
    for i := range stringsInfo {
        for j := 0; j < m; j++ {
            // Output the matrix by idnex stringsInfo[i].pos
            fmt.Print(getEl(stringsInfo[i].pos, j, &ma), " ")
        }
        fmt.Println("|", stringsInfo[i].summa)
    }
}