Создать матрицу инцидентности с помощью igraph в C - PullRequest
Новая
       7

Создать матрицу инцидентности с помощью igraph в C

0 голосов
/ 23 ноября 2018

Я пытаюсь создать матрицу инцидентности из сгенерированного мной графика: 

igraph_t generateGeometricGraph(igraph_integer_t n, igraph_real_t radius){
    igraph_t G_graph;
    igraph_bool_t connected;

    // generate a connected random graph using the geometric model
    igraph_grg_game(&G_graph, n, radius, 0, 0, 0);

    igraph_is_connected(&G_graph, &connected, IGRAPH_WEAK);
    while(!connected){
        igraph_destroy(&G_graph);
        igraph_grg_game(&G_graph, n, radius, 0, 0, 0);

        igraph_is_connected(&G_graph, &connected, IGRAPH_WEAK);
    }
    return G_graph;
}

Это мой график, но я не могу сделать матрицу: есть библиотечная функция для получения инцидентности.матрица, но это также для двудольного графа.Я вижу, что есть функция igraph_inclist_init, которая может быть полезна, но мне не удалось получить матрицу.Спасибо за вашу помощь!

1 Ответ

0 голосов
/ 23 ноября 2018

Матрица инцидентности по краю вершины достаточно проста для построения.Просто зациклите все ребра и добавьте необходимые элементы матрицы для каждого.

В зависимости от того, зачем вам нужна эта матрица, вы можете использовать для этого разреженную структуру данных матрицы.У igraph есть два разреженных типа матрицы.

Для простоты здесь я покажу пример с типом данных плотной матрицы igraph_matrix_t. 

#include <igraph.h>
#include <stdio.h>

void print_matrix(igraph_matrix_t *m, FILE *f) {
  long int i, j;
  for (i=0; i<igraph_matrix_nrow(m); i++) {
    for (j=0; j<igraph_matrix_ncol(m); j++) {
      fprintf(f, " %li", (long int)MATRIX(*m, i, j));
    }
    fprintf(f, "\n");
  }
}

int main() {
    igraph_t graph;
    igraph_integer_t vcount, ecount, i;
    igraph_matrix_t incmat;

    igraph_ring(&graph, 10, 0, 0, 0);

    vcount = igraph_vcount(&graph);
    ecount = igraph_ecount(&graph);

    /* this also sets matrix elements to zeros */
    igraph_matrix_init(&incmat, vcount, ecount);

    for (i=0; i < ecount; ++i) {
        /* we increment by one instead of set to 1 to handle self-loops */
        MATRIX(incmat, IGRAPH_FROM(&graph, i), i) += 1;
        MATRIX(incmat, IGRAPH_TO(&graph, i), i) += 1;
    }

    print_matrix(&incmat, stdout);

    igraph_matrix_destroy(&incmat);
    igraph_destroy(&graph);

    return 0;
}
...