О ненаправленных графах с представлением матрицы смежности

Question

Я хочу создать матричное представление для алгоритма графа, используя как можно меньше памяти.

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

Затем я прочитал пост, предлагающий использовать структуру, которая может помочь мне сделать это, используя, например, int (4 байта, так что 32-bit) и, с некоторой магией и битовыми сдвигами, используйте его как «массив» битов.

Понял, но я не могу понять, как именно я мог это сделать.Я запутался ...

Я думаю об использовании структуры для хранения указателя типа int / void на n байтов, соответствующих наименьшему количеству байтов, на количество n выделенных битов и число k«Количество битов в этом представлении, что-то в этом роде.

Поэтому я подумал, что вы могли бы помочь мне понять, каков наилучший подход для такого рода решений.

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

Спасибо всем.

PS: почти забыл, я программирую это на C, но я очень хорошо понимаю языки C ++, .Net и Java.Еще раз спасибо.

Answer 1

Здесь есть несколько хитрых битов: работа с отдельными битами в большом массиве;и моделирование 2-мерного массива с 1-дневным.Сначала лучше решить их отдельно.

Начните с некоторых вспомогательных функций, которые позволяют вам работать с отдельными битами.Что-то вроде:

typedef unsigned int BYTE;  /* Int type to use for data. */
#define BYTE_SIZE (sizeof(BYTE)*8)   /* How many bits in each one. */

void set_bit(BYTE *data, int pos, int value)
{
    int index = pos / BYTE_SIZE;   /* Which byte to adjust. */
    int offset = pos % BYTE_SIZE;  /* Which bit within it. */
    /* 1 << offset turns into the place value for the bit at offset. */
    /* x | 1 << offset sets the bit there (an OR operation);
       ~(1 << offset) gets something with all bits except that bit set, and
       x & ~(1 << offset) clears the bit with an AND operation on x. */
    if (value)
        data[index] = data[index] | (1 << offset);
    else
        data[index] = data[index] & ~(1 << offset);
}

int test_bit(int *data
{
    int index = pos / BYTE_SIZE;
    int offset = pos % BYTE_SIZE;
    /* An AND operation to see if the bit is set, then compare against 0
       so that 1 or 0 is returned instead of the place value. */
    return (data[index] & (1 << offset)) != 0;
}

Затем вы перемещаетесь на уровень со структурой для хранения массива байтов и некоторых данных об измерениях.2-мерный массив может быть смоделирован с 1-й единицей путем преобразования операции с битом (x,y) в операцию с битом 1007 *.

struct BITMATRIX
{
    BYTE *data;
    int width;
    int height;
}

void set_bit_matrix(struct BITMATRIX *bm, int x, int y, int value)
{
    int pos = y * bm->width + x;
    set_bit(bm->data, pos, value);
}

/* Etc. */

Answer 2

Просто комментарий к битовым структурам в C - посмотрите здесь:

• http://www.cs.cf.ac.uk/Dave/C/node13.html
• http://msdn.microsoft.com/en-us/library/yszfawxh(VS.80).aspx

Это должны быть хорошие указатели на то, как вы должны использовать битовые структуры.