/** * test_graph.c * * ORATIO Library * Copyright (C) 2009-2010 * * Licensed under BSD License. */ #include #include #define N 10 int main() { double dist[N]; int previous[N], next[N]; GR_Edge *previous_edges[N]; int perm[N]; int i; GR_Graph *graph = gr_graph_new(N); GR_Node *nodes = graph->nodes; GR_Node *temp_node; GR_Edge *e; DS_List *edges = ds_list_new(), *temp_edge, *start; for (i = 0; i < N; i++) graph->nodes[i].value = _mallocs(2, double); /* Connect the nodes */ edges = ds_list_prepend(edges, gr_graph_connect(graph, 0, 4, 1550.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 0, 3, 1100.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 0, 2, 650.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 0, 1, 300.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 1, 7, 2800.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 1, 6, 2150.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 1, 5, 1500.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 2, 8, 2850.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 2, 7, 2200.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 2, 6, 1550.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 2, 5, 1000.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 3, 8, 2250.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 3, 7, 1600.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 3, 6, 1050.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 3, 5, 500.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 4, 8, 1650.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 4, 7, 1100.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 4, 6, 550.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 4, 5, 0.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 5, 9, 1400.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 6, 9, 900.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 7, 9, 400.0)); edges = ds_list_prepend(edges, gr_graph_connect(graph, 8, 9, 0.0)); start = edges; while (edges) { ((GR_Edge *)(edges->data))->value = _mallocs(3, double); edges = edges->next; } /* gr_graph_dijkstra(N, graph->nodes, 0, 8, dist, previous); */ gr_graph_dijkstra(N, graph->nodes, 0, 9, dist, previous); printf("Optimal value: %g\n", dist[9]); i = 9; do { printf("Parent of %d: %d\n", i, previous[i]); i = previous[i]; } while (i); gr_graph_backward_linking(N, nodes, 0, 9, dist, next); printf("Optimal value: %g\n", dist[0]); i = 0; do { printf("Successor of %d: %d\n", i, next[i]); i = next[i]; } while (next[i] != -1); gr_graph_forward_linking(N, nodes, 0, 9, dist, previous); printf("Optimal value: %g\n", dist[9]); i = 9; do { printf("Parent of %d: %d\n", i, previous[i]); i = previous[i]; } while (i); gr_graph_accession(N, nodes, 0, 9, dist, previous); printf("Optimal value: %g\n", dist[9]); i = 9; do { printf("Parent of %d: %d\n", i, previous[i]); i = previous[i]; } while (i); gr_graph_free(graph); return 0; }