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

[Gábor Csárdi]

Hello Christian,

you can use

int igraph_get_eids(const igraph_t *graph, igraph_vector_t *eids,
                    const igraph_vector_t *pairs, igraph_bool_t directed);

This is not documented, but will be, it is public. You fill 'pairs'
with the vertex ids and the result is returned in 'eids'.
Unfortunately it is not possible to just pass the result of the
shortest path calculation, because 'pairs' really required to be pairs
of vertices.

But actually our shortest path implementation should really return the
edge ids (as well). I will add this to the TODO list, it is easy to
implement, we use the edges for the calculation, anyway.
https://bugs.launchpad.net/igraph/+bug/406194

Thanks, best,
G.

On Wed, Jul 29, 2009 at 2:01 AM, Christian
Gonzalez<address@hidden> wrote:
> 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
> }
>
>
>
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM