Транспонирование разреженной матрицы с использованием связанных списков (задачи обхода) - PullRequest
Новая
       27

Транспонирование разреженной матрицы с использованием связанных списков (задачи обхода)

0 голосов
/ 29 марта 2012

Я пытаюсь транспонировать разреженную матрицу в c ++.Я борюсь с обходом новой транспонированной матрицы.Я хочу ввести все от первой строки матрицы до первого столбца новой матрицы.

Каждая строка имеет индекс столбца, в котором должно быть число, и сам номер.

Ввод:

Ввод номера столбца Ввод номера столбца

Ввод:

1 1 2 2 3 3

1 4 2 53 6

1 7 2 8 3 9

Вывод:

1 1 2 4 3 7

1 2 2 5 3 8

1 3 2 6 3 9

Как сделать так, чтобы список проходил вниз по первому столбцу, вставляя первый элемент по ходу, а затем возвращался к вершине, вставляя вниз по второму столбцу.Извинения, если это два трудно следовать.Но все, с чем я хочу помочь - это пройти через транспонированную матрицу, чтобы она была в нужном месте в нужное время, вставив nz (ненулевой) объект в нужное место.

Вот мой код 

list<singleRow> tran;
//Finshed reading so transpose

for (int i = 0; i < rows.size(); i++){ // Initialize transposed matrix
    singleRow trow;
    tran.push_back(trow);
}

list<singleRow>::const_iterator rit;
list<singleRow>::const_iterator trowit; 
int rowind;
for (rit = rows.begin(), rowind = 1; rit != rows.end(); rit++, rowind++){//rit = row iterator
    singleRow row = *rit;
    singleRow::const_iterator nzit;
    trowit = tran.begin(); //Start at the beginning of the list of rows
    trow = *trowit;
    for (nzit = row.begin(); nzit != row.end(); nzit++){//nzit = non zero iterator
            int col = nzit->getCol();
            double val = nzit->getVal();
            trow.push_back(nz(rowind,val)); //How do I attach this to tran so that it goes in the right place?
            trowit++;
    }
}

Ответы [ 2 ]

1 голос
/ 29 марта 2012

Ваш выбор list-of-list представление для разреженной матрицы плохое для транспонирования.Иногда, рассматривая алгоритмы и структуры данных, лучше всего предпринять попытку превратить вашу структуру данных в более подходящую для вашего алгоритма, чем искажать алгоритм для работы с неправильной структурой данных.

В этом случае вы могли бы, например, прочитать вашу матрицу в представление списка координат , которое было бы очень легко транспонировать, а затем записать в любое представление, которое вам нравится.Если пространство является проблемой, то вам может потребоваться выполнить этот фрагмент по частям, выделяя новые столбцы в целевом представлении 1 на 1 и освобождая столбцы в вашем старом представлении по ходу работы.

1 голос
/ 29 марта 2012

Ваше представление матрицы неэффективно: оно не использует тот факт, что матрица разрежена. Я говорю так, потому что он включает в себя все строки матрицы, даже если большинство из них равны нулю (пусто), как это обычно происходит с разреженными матрицами.

С вашим представлением также сложно работать. Поэтому я предлагаю сначала преобразовать представление (в обычный двумерный массив), транспонировать матрицу и выполнить обратное преобразование.

(ред :) В качестве альтернативы вы можете изменить представление, например, так:

Ввод: rowInd colInd num 

1 1 1
1 2 2
1 2 3
2 1 4
2 2 5
2 3 6
3 1 7
3 2 8
3 3 9

Выход: 

1 1 1
2 1 2
3 1 3
1 2 4
2 2 5
3 2 6
1 3 7
2 3 8
3 3 9

Код будет выглядеть примерно так: 

struct singleElement {int row, col; double val;};
list<singleElement> matrix_input, matrix_output;

...
// Read input matrix from file or some such

list<singleElement>::const_iterator i;
for (i = matrix_input.begin(); i != matrix_input.end(); ++i)
{
    singleElement e = *i;
    std::swap(e.row, e.col);
    matrix_output.push_back(e);
}
...