[igraph] [c]: Help - where to get the edges from traverse's paths disjktra?

[Christian Gonzalez]

Hello everyone,
  I'm trying to adapt some PostgreSQL functions "shortest path"  to 
igraph library.

my problem is:
I need to return the following data structure from my shortest path 
function:

typedef struct
{
  int vertex_id;
  int edge_id;
  float cost;
} path_element_t;

and "igraph_get_shortest_paths_dijkstra" only returns vertex ids.

What is the best way to get the edges from traverse's paths disjktra?



This is my igraph test for then adapt:

#gcc command:
#gcc shortest_path.c -std=gnu99 -I/usr/include -I/usr/include/igraph 
-L/usr/lib -ligraph -o shortest_path
#
#source: shortest_path.c
#Christian Gonzalez <address@hidden>

#include <stdlib.h>
#include <igraph/igraph.h>

/*
 *
 */
typedef struct
{
  int id;
  int source;
  int target;
  float cost;
  int bidirectional;
  float reverse_cost;
} edge_t;

/*
 *
 */
typedef struct
{
  int vertex_id;
  int edge_id;
  float cost;
} path_element_t;

/*
 * FUNCTIONS PROTOTYPES
 */
static int
fecth_edges(const int i, edge_t *e, igraph_vector_t *edges, 
igraph_vector_t *weights,
            igraph_vector_t *eids, igraph_vector_t *vertex, int directed);

static void
fill_edges_attributes(const int i, igraph_t *g, igraph_vector_t *eids);

static void
reenumerate(igraph_real_t source, igraph_real_t target, igraph_real_t 
*newsource,
             igraph_real_t *newtarget, igraph_vector_t *v);

static igraph_real_t
search_vertex(igraph_real_t id, igraph_vector_t *v);

static void
free_object();
/************************************************************************************/

int
main(int argc, char *argv[])
{
  igraph_t graph;
  igraph_vector_t result;
  igraph_vector_t weights;
  igraph_vector_t eids;
  igraph_vector_t edges;
  igraph_vector_t vertex;
  igraph_real_t NUM_EDGES = 9; //Constante para los pesos
  igraph_vector_ptr_t result_vector; //

  igraph_integer_t from = 100;
  igraph_integer_t to = 700;
  int directed = 1;//the graph is directed (default)


  if (argc > 1 && argc < 5)
  {
    from = atof(argv[1]);
    to = atof(argv[2]);
    directed = atoi(argv[3]);
  }

  /* turn on attribute handling */
  igraph_i_set_attribute_table(&igraph_cattribute_table);
  path_element_t *path;

  /*      The graph
   *                         10
   *                       A--->B
   *                       |        |
   *                100 |        |110
   *                       |        |
   *          E<------C------D
   *           |   60   |  20
   *       35|          |50
   *           |          |
   *          G------>F<-----H
   *             25           15
   *
   * A --> 100
   * B --> 200
   * C --> 300
   * D --> 400
   * E --> 500
   * F --> 600
   * G --> 700
   * H --> 800
   *
   *   s        t      w
   *  100 ---> 200 = 10.000000
   *  200 <--> 400 = 110.000000
   *  100 <--> 300 = 100.000000
   *  400 <--> 300 = 20.000000
   *  300 <--> 600 = 50.000000
   *  300 ---> 500 = 60.000000
   *  500 <--> 700 = 35.000000
   *  700 ---> 600 = 25.000000
   *  800 ---> 600 = 15.000000
   */

  edge_t *e = NULL;

  if ((e = (edge_t *) malloc(sizeof(edge_t) * NUM_EDGES)) == NULL)
  {
    printf("No memory for e structure");
    //TODO: free igraph memory objects
    exit(EXIT_FAILURE);
  }

  e[0].id = 158;
  e[0].source = 100;
  e[0].target = 200;
  e[0].cost = 10;
  e[0].bidirectional = 0;
  e[0].reverse_cost = 0;

  e[1].id = 1245;
  e[1].source = 200;
  e[1].target = 400;
  e[1].cost = 110;
  e[1].bidirectional = 1;
  e[1].reverse_cost = 0;

  e[2].id = 3657;
  e[2].source = 100;
  e[2].target = 300;
  e[2].cost = 100;
  e[2].bidirectional = 1;
  e[2].reverse_cost = 0;

  e[3].id = 8745;
  e[3].source = 400;
  e[3].target = 300;
  e[3].cost = 20;
  e[3].bidirectional = 1;
  e[3].reverse_cost = 0;

  e[4].id = 2458;
  e[4].source = 300;
  e[4].target = 600;
  e[4].cost = 50;
  e[4].bidirectional = 1;
  e[4].reverse_cost = 0;

  e[5].id = 9758;
  e[5].source = 300;
  e[5].target = 500;
  e[5].cost = 60;
  e[5].bidirectional = 0;
  e[5].reverse_cost = 0;

  e[6].id = 1458;
  e[6].source = 500;
  e[6].target = 700;
  e[6].cost = 35;
  e[6].bidirectional = 1;
  e[6].reverse_cost = 0;

  e[7].id = 6547;
  e[7].source = 700;
  e[7].target = 600;
  e[7].cost = 25;
  e[7].bidirectional = 0;
  e[7].reverse_cost = 0;

  e[8].id = 6547;
  e[8].source = 800;
  e[8].target = 600;
  e[8].cost = 15;
  e[8].bidirectional = 0;
  e[8].reverse_cost = 0;

  /* initializing  igraph vectors*/
  igraph_vector_init(&edges, NUM_EDGES * 2);
  igraph_vector_init(&weights, NUM_EDGES);
  igraph_vector_init(&eids, NUM_EDGES);
  igraph_vector_init(&vertex, 0);

  //filling the "igraph edges" from "my edges structure"
  for (register int i = 0; i < NUM_EDGES; i++)
  {
    fecth_edges(i, &e[i], &edges, &weights, &eids, &vertex, directed);
  }

  //free my edges structure
  free(e);

  /*
   *checking: from and to in the graph
   */
  if ((from = search_vertex(from, &vertex)) == -1)
  {
    printf("the source is not in the graph \n");
    //TODO: free memory
    return EXIT_FAILURE;
  }

  if ((to = search_vertex(to, &vertex)) == -1)
  {
    printf("the target is not in the graph \n");
    //TODO: free memory
    return EXIT_FAILURE;
  }

  printf("new ids: from = %f --> to = %f \n", from, to);

  /*Create the graph*/
  if (directed == 1)
  {
    igraph_create(&graph, &edges, 0, IGRAPH_DIRECTED);
  }
  else
  {
    igraph_create(&graph, &edges, 0, IGRAPH_UNDIRECTED);
  }

  // filling the graph attr
  for (register int i = 0; i < (int) igraph_ecount(&graph); i++)
  {
    fill_edges_attributes(i, &graph, &eids);
  }

  /* vector result*/
  igraph_vector_init(&result, 0);
  igraph_vector_ptr_init(&result_vector, 1);
  VECTOR(result_vector)[0] = &result;

  /* graph information*/
  printf("Vertex: %i, edges: %i \n", (int) igraph_vcount(&graph), (int) 
igraph_ecount(&graph));

  /* shortest paths*/
  //TODO: validate the igraph_get_shortest_paths_dijkstra function result
  igraph_get_shortest_paths_dijkstra(&graph, &result_vector, from, 
igraph_vss_1(to), &weights,
                                     IGRAPH_OUT);

  /* Imprimimos los resultados*/
  printf("RUTA: ");

  path = (path_element_t *) malloc(sizeof(path_element_t) * 
igraph_vector_size(&result));

  for (register int i = 0; i < igraph_vector_size(&result); i++)
  {
    //path[i].vertex_id = (long) VECTOR(result)[i];
    path[i].vertex_id = (long) VECTOR(vertex)[(long int) 
VECTOR(result)[i]];
    path[i].edge_id = -1;
    path[i].cost = -1;
  }

  for (register int i = 0; i < igraph_vector_size(&result); i++)
  {
    printf("%ld ", path[i].vertex_id);
  }

  printf("\n");

  /*free memory*/
  igraph_destroy(&graph);
  igraph_vector_destroy(&result);
  igraph_vector_destroy(&weights);
  igraph_vector_destroy(&eids);
  igraph_vector_destroy(&vertex);
  igraph_vector_ptr_destroy(&result_vector);
  igraph_vector_destroy(&edges);

  free(path);

  return EXIT_SUCCESS;
}

/*
 *
 */
static int
fecth_edges(const int i, edge_t *e, igraph_vector_t *edges, 
igraph_vector_t *weights,
            igraph_vector_t *eids, igraph_vector_t *vertex, int directed)
{
  igraph_real_t ns = 0, *nsp = NULL;
  igraph_real_t nt = 0, *ntp = NULL;

  nsp = &ns;
  ntp = &nt;

  reenumerate(e->source, e->target, nsp, ntp, vertex);

  if (e->bidirectional == 1)
  {
    printf("%i <--> %i = %f <|******|>  ", e->source, e->target, e->cost);
    printf("%f <--> %f = %f \n", *nsp, *ntp, e->cost);
  }
  else
  {
    printf("%i ---> %i = %f <|******|>  ", e->source, e->target, e->cost);
    printf("%f ---> %f = %f \n", *nsp, *ntp, e->cost);
  }

  //reenumerated(e->source, e->target, nsp, ntp, vertex, 0);

  VECTOR(*edges)[(2* i )] = *nsp;
  VECTOR(*edges)[(2* i ) + 1] = *ntp;
  VECTOR(*weights)[i] = e->cost;
  VECTOR(*eids)[i] = e->id;
  /*
   VECTOR(*edges)[(2* i )] = e->source;
   VECTOR(*edges)[(2* i ) + 1] = e->target;
   VECTOR(*weights)[i] = e->cost;
   VECTOR(*eids)[i] = e->id;
   */
  if (directed == 1)
  {
    //Verificamos si es bidirecional para agregarlo en sentido contrario
    if (e->bidirectional == 1)
    {
      int dta_edges = igraph_vector_size(edges);
      int dta_weights = igraph_vector_size(weights);
      int dta_eids = igraph_vector_size(eids);

      //reservamos mas memoria para el vector, ya que vemos a añadir 
otro lado
      //se agregan 2 mas, ya que es un vector from,to
      //TODO: verificar que la funcion igraph_vector_resize reserve la 
memoria
      igraph_vector_resize(edges, dta_edges + 2);
      //reservamos mas memoria para el vector, ya que vemos a añadir 
otro lado
      igraph_vector_resize(weights, dta_weights + 1);
      //reservamos mas memoria para el vector, ya que vemos a añadir 
otro lado
      igraph_vector_resize(eids, dta_eids + 1);

      VECTOR(*edges)[dta_edges] = *ntp;
      VECTOR(*edges)[dta_edges + 1] = *nsp;
      VECTOR(*weights)[dta_weights] = e->cost;
      VECTOR(*eids)[dta_eids] = e->id;

      /*
       VECTOR(*edges)[dta_edges] = e->target;
       VECTOR(*edges)[dta_edges + 1] = e->source;
       VECTOR(*weights)[dta_weights] = e->cost;
       VECTOR(*eids)[dta_eids] = e->id;
       */
    }
  }
}

/*
 *
 */
static void
fill_edges_attributes(const int i, igraph_t *g, igraph_vector_t *eids)
{
  SETEAN(g,"id",i,VECTOR(*eids)[i]);
}

/*
 *
 */
static void
reenumerate(igraph_real_t source, igraph_real_t target, igraph_real_t 
*newsource,
            igraph_real_t *newtarget, igraph_vector_t *v)
{
  long int i = 0, *ind = NULL;
  ind = &i;

  if (igraph_vector_search(v, 0, source, ind))
  {
    *newsource = (float) (*ind);
  }
  else
  {
    //TODO: verificar que la funcion igraph_vector_push_back no de 
error de memoria
    igraph_vector_push_back(v, source);
    *newsource = (float) (igraph_vector_size(v) - 1);
  }

  if (igraph_vector_search(v, 0, target, ind))
  {
    *newtarget = (float) (*ind);
  }
  else
  {
    igraph_vector_push_back(v, target);
    *newtarget = (float) (igraph_vector_size(v) - 1);
  }
}

/*
 *
 */
static igraph_real_t
search_vertex(igraph_real_t id, igraph_vector_t *v)
{
  long int i = 0, *ind = NULL;
  ind = &i;

  if (igraph_vector_search(v, 0, id, ind))
  {
    return (float) (*ind);
  }
  else
  {
    return (float) (-1);
  }
}

/*
 *
 */
static void
free_object()
{
  //TODO:liberar los objetos desde este procedimiento y este debe ser 
llamado siempre en las execiones
}