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

[Christian Gonzalez]

Hello Gábor,
    I followed your suggestions and my problem is solved.

Thanks a lot!

these is my new source code:

/*gcc command:
* gcc shortest_path.c -std=gnu99 -I/usr/include -I/usr/include/igraph -L/usr/lib -ligraph -o shortest_path
*
*
*    HOW TO USE:
* ./shortest_path
* ./shortest_path 100 800 1
* valgrind --memcheck:leak-check=yes --tool=memcheck ./src/igraph_test 100 800 1
*
* AUTHOR: Christian Gonzalez <address@hidden>
* FILE: shortest_path.c
*/
/*
 * igraph_test.h
 *
 *  Created on: 08-jul-2009
 *      Author: cgonzalez
 */
#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;

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 int
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_element(igraph_real_t id, igraph_vector_t *v);

static igraph_real_t
search_eid(igraph_t *g, igraph_real_t id1, igraph_real_t id2, igraph_bool_t directed);


int
main(int argc, char *argv[])
{
  igraph_t graph;
  igraph_vector_t weights;
  igraph_vector_t eids;
  igraph_vector_t edges;
  igraph_vector_t vertex;

  igraph_integer_t from = 100;
  igraph_integer_t to = 700;

  int directed = 1;
  int ret = -1;


  igraph_real_t NUM_EDGES = 9;

  /*getting the arguments*/
  if (argc == 4)
  {
    from = atof(argv[1]);
    to = atof(argv[2]);
    directed = atoi(argv[3]);
  }

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

  /*my own path structure*/
  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
   *  200 <--> 400 = 110
   *  100 <--> 300 = 100
   *  400 <--> 300 = 20
   *  300 <--> 600 = 50
   *  300 ---> 500 = 60
   *  500 <--> 700 = 35
   *  700 ---> 600 = 25
   *  800 ---> 600 = 15
   */

  /*reserve memory for my own edge structure and fill those*/
  edge_t *e = NULL;

  if ((e = (edge_t *) malloc(sizeof(edge_t) * NUM_EDGES)) == NULL)
  {
    printf("No memory for e structure");
    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 own edge structure"
  for (register int i = 0; i < NUM_EDGES; i++)
  {
    fecth_edges(i, &e[i], &edges, &weights, &eids, &vertex, directed);
  }

  //free my own edge structure
  free(e);

  printf("from -> to : %3.0f ----> %3.0f ===>  ", from, to);
  /*
   *checking: from and to in the graph
   */
  if ((from = search_element(from, &vertex)) == -1)
  {
    printf("the source is not in the graph \n");

    igraph_vector_destroy(&weights);
    igraph_vector_destroy(&edges);
    igraph_vector_destroy(&eids);
    igraph_vector_destroy(&vertex);

    return EXIT_FAILURE;
  }

  if ((to = search_element(to, &vertex)) == -1)
  {
    printf("the target is not in the graph \n");

    igraph_vector_destroy(&weights);
    igraph_vector_destroy(&edges);
    igraph_vector_destroy(&eids);
    igraph_vector_destroy(&vertex);

    return EXIT_FAILURE;
  }

  printf("%3.0f ----> %3.0f \n", from, to);

  /*Create the graph*/

  if (directed == 1)
  {
    ret = igraph_create(&graph, &edges, 0, IGRAPH_DIRECTED);
    if ((ret == IGRAPH_EINVEVECTOR) || (ret == IGRAPH_EINVVID))
    {
      printf("Problems creating the graph, check your edges vector!");

      igraph_vector_destroy(&weights);
      igraph_vector_destroy(&edges);
      igraph_vector_destroy(&eids);
      igraph_vector_destroy(&vertex);

      return EXIT_FAILURE;
    }
  }
  else
  {
    ret = igraph_create(&graph, &edges, 0, IGRAPH_UNDIRECTED);
    if ((ret == IGRAPH_EINVEVECTOR) || (ret == IGRAPH_EINVVID))
    {
      printf("Problems creating the graph, check your edges vector!");

      igraph_vector_destroy(&weights);
      igraph_vector_destroy(&edges);
      igraph_vector_destroy(&eids);
      igraph_vector_destroy(&vertex);
      return EXIT_FAILURE;
    }
  }

  // filling the graph attr
  for (register int i = 0; i < (int) igraph_ecount(&graph); i++)
  {
    //filling the my own edges ids
    SETEAN(&graph,"id",i,VECTOR(eids)[i]);
  }

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

  /* vectors for results*/
  igraph_vector_t result;
  igraph_vector_ptr_t result_vector;
  igraph_vector_init(&result, 0);
  igraph_vector_ptr_init(&result_vector, 1);
  VECTOR(result_vector)[0] = &result;

  /* Calculating shortest paths*/
  ret = igraph_get_shortest_paths_dijkstra(&graph, &result_vector, from, igraph_vss_1(to),
                                           &weights, IGRAPH_OUT);

  if ((ret == IGRAPH_ENOMEM) || (ret == IGRAPH_EINVVID) || (ret == IGRAPH_EINVMODE))
  {
    printf("Problems calculating igraph_get_shortest_paths_dijkstra, check yours vectors data!");
    igraph_vector_destroy(&weights);
    igraph_vector_destroy(&edges);
    igraph_vector_destroy(&eids);
    igraph_vector_destroy(&vertex);
    igraph_destroy(&graph);
    igraph_vector_destroy(&result);
    igraph_vector_ptr_destroy(&result_vector);
    return EXIT_FAILURE;
  }

  //dot not exist shortest path from --> to
  if(igraph_vector_size(&result) == 0)
  {
    printf("dot not exist shortest path from --> to \n\n");
    igraph_vector_destroy(&weights);
    igraph_vector_destroy(&edges);
    igraph_vector_destroy(&eids);
    igraph_vector_destroy(&vertex);
    igraph_destroy(&graph);
    igraph_vector_destroy(&result);
    igraph_vector_ptr_destroy(&result_vector);
    return EXIT_FAILURE;
  }
  if ((path = (path_element_t *) malloc(sizeof(path_element_t) * igraph_vector_size(&result)))
      == NULL)
  {
    printf("problems allocating memory for path pointer");
    igraph_vector_destroy(&weights);
    igraph_vector_destroy(&edges);
    igraph_vector_destroy(&eids);
    igraph_vector_destroy(&vertex);
    igraph_destroy(&graph);
    igraph_vector_destroy(&result);
    igraph_vector_ptr_destroy(&result_vector);
    return EXIT_FAILURE;
  }

  /*Putting the result in my own structure*/
  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].cost = -1;

    if (i < (igraph_vector_size(&result) - 1))
    {
      path[i].edge_id = (int) search_eid(&graph, (long int) VECTOR(result)[i],
                                         (long int) VECTOR(result)[i + 1],
                                         igraph_is_directed(&graph));
      path[i].edge_id = EAN(&graph,"id",path[i].edge_id);
    }
    else
    {
      path[i].edge_id = -1;
    }
  }

  /* Print the result*/
  printf("\n");
  printf("PATH : ");
  printf("( vertex id )=== edge id === -1 ( END) \n");
  printf("\n");

  for (register int i = 0; i < igraph_vector_size(&result); i++)
  {
    if (i == 0)
    {
      printf("( ");
    }

    if (i < (igraph_vector_size(&result)-1) )
    {
      //printf("%3.0i )===%3.0i[%2.0f]===( ", path[i].vertex_id, path[i].edge_id, path[i].cost);
      printf("%3.0i )===%3.0i===( ", path[i].vertex_id, path[i].edge_id);
    }

    if (i == (igraph_vector_size(&result)-1))
    {
      printf("%3.0i )===%3.0i (END)", path[i].vertex_id, path[i].edge_id);
    }

  }
  printf("\n");
  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 = %3.0f  == new ids ==>  ", e->source, e->target, e->cost);
    printf("%3.0f <--> %3.0f = %3.0f \n", *nsp, *ntp, e->cost);
  }
  else
  {
    printf("%i ---> %i = %3.0f  == new ids ==>  ", e->source, e->target, e->cost);
    printf("%3.0f ---> %3.0f = %3.0f \n", *nsp, *ntp, e->cost);
  }

  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
      if ((igraph_vector_resize(edges, dta_edges + 2)) == IGRAPH_ENOMEM)
      {
        printf("problems allocating memory for edges vector");
        igraph_vector_destroy(weights);
        igraph_vector_destroy(edges);
        igraph_vector_destroy(eids);
        igraph_vector_destroy(vertex);
        return EXIT_FAILURE;
      }

      //reservamos mas memoria para el vector, ya que vemos a añadir otro lado
      if ((igraph_vector_resize(weights, dta_weights + 1)) == IGRAPH_ENOMEM)
      {
        printf("problems allocating memory for weights vector");
        igraph_vector_destroy(weights);
        igraph_vector_destroy(edges);
        igraph_vector_destroy(eids);
        igraph_vector_destroy(vertex);
        return EXIT_FAILURE;
      }

      //reservamos mas memoria para el vector, ya que vemos a añadir otro lado
      if ((igraph_vector_resize(eids, dta_eids + 1)) == IGRAPH_ENOMEM)
      {
        printf("problems allocating memory for eids vector");
        igraph_vector_destroy(weights);
        igraph_vector_destroy(edges);
        igraph_vector_destroy(eids);
        igraph_vector_destroy(vertex);
        return EXIT_FAILURE;
      }

      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 int
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
  {
    if ((igraph_vector_push_back(v, source)) == IGRAPH_ENOMEM)
    {
      printf("problems allocating memory for v vector");
      return EXIT_FAILURE;
    }
    *newsource = (float) (igraph_vector_size(v) - 1);
  }

  if (igraph_vector_search(v, 0, target, ind))
  {
    *newtarget = (float) (*ind);
  }
  else
  {
    if ((igraph_vector_push_back(v, target)) == IGRAPH_ENOMEM)
    {
      printf("problems allocating memory for v vector");
      return EXIT_FAILURE;
    }
    *newtarget = (float) (igraph_vector_size(v) - 1);
  }
}

/*
 *
 */
static igraph_real_t
search_element(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 igraph_real_t
search_eid(igraph_t *g, igraph_real_t id1, igraph_real_t id2, igraph_bool_t directed)
{
  igraph_vector_t pair;
  igraph_vector_init(&pair, 2);
  igraph_vector_t out;
  igraph_vector_init(&out, 0);
  igraph_real_t e = -1;

  VECTOR(pair)[0] = id1;
  VECTOR(pair)[1] = id2;

  igraph_get_eids(g, &out, &pair, directed);
  e = VECTOR(out)[0];
  igraph_vector_destroy(&out);
  igraph_vector_destroy(&pair);

  return e;
}


El 29/07/09 01:59, Gábor Csárdi escribió:

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