Hello Gábor,
Thanks a lot, I'm trying to solve my problem with you
recomendation, and then I will move to version 0.6.
Thanks again,
Christian
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
|