Vlib/graph.c

Go to the documentation of this file.
00001 /****************************************************************************
00002 *
00003 * MODULE:       Vector library 
00004 *               
00005 * AUTHOR(S):    Radim Blazek
00006 *
00007 * PURPOSE:      Higher level functions for reading/writing/manipulating vectors.
00008 *
00009 *               This program is free software under the GNU General Public
00010 *               License (>=v2). Read the file COPYING that comes with GRASS
00011 *               for details.
00012 *
00013 *****************************************************************************/
00014 #include <stdlib.h>
00015 #include <string.h>
00016 #include <grass/gis.h>
00017 #include <grass/dbmi.h>
00018 #include <grass/Vect.h>
00019 
00020 /* TODO: Vect_graph_free ( GRAPH *graph ) */
00021 
00022 static int From_node;   /* from node set in SP and used by clipper for first arc */  
00023 
00024 static int clipper ( dglGraph_s    *pgraph ,
00025                      dglSPClipInput_s  * pargIn ,
00026                      dglSPClipOutput_s * pargOut ,
00027                      void *          pvarg )         /* caller's pointer */
00028 {
00029     dglInt32_t cost;
00030     dglInt32_t from;
00031     
00032     G_debug ( 3, "Net: clipper()" );
00033     
00034     from = dglNodeGet_Id(pgraph, pargIn->pnNodeFrom);
00035     
00036     G_debug ( 3, "  Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d", 
00037                      dglEdgeGet_Id (pgraph, pargIn->pnEdge), 
00038                      from, dglNodeGet_Id(pgraph, pargIn->pnNodeTo),
00039                      pargOut->nEdgeCost);
00040 
00041     if ( from != From_node ) { /* do not clip first */
00042         if ( dglGet_NodeAttrSize(pgraph) > 0 ) {
00043             memcpy( &cost, dglNodeGet_Attr(pgraph, pargIn->pnNodeFrom), sizeof(cost) );
00044             if ( cost == -1 ) { /* closed, cannot go from this node except it is 'from' node */
00045                 G_debug ( 3, "  closed node" );
00046                 return 1;
00047             } else {
00048                 G_debug ( 3, "  EdgeCost += %d (node)", cost );
00049                 pargOut->nEdgeCost += cost;
00050             }
00051         }
00052     } else {
00053         G_debug ( 3, "  don't clip first node" );
00054     }
00055 
00056     return 0;   
00057 }
00058 
00067 void
00068 Vect_graph_init ( GRAPH *graph, int nodes_costs )
00069 {
00070     dglInt32_t opaqueset[ 16 ] = { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
00071 
00072     G_debug (3, "Vect_graph_init()" ); 
00073 
00074     if ( nodes_costs )
00075         dglInitialize(graph, (dglByte_t)1, sizeof(dglInt32_t), (dglInt32_t)0, opaqueset);
00076     else
00077         dglInitialize(graph, (dglByte_t)1, (dglInt32_t)0, (dglInt32_t)0, opaqueset);
00078 }
00079 
00088 void
00089 Vect_graph_build ( GRAPH *graph )
00090 {
00091     int ret;
00092 
00093     G_debug (3, "Vect_graph_build()" ); 
00094 
00095     ret = dglFlatten ( graph );
00096     if ( ret < 0 ) G_fatal_error ("GngFlatten error");
00097 }
00098 
00110 void
00111 Vect_graph_add_edge ( GRAPH *graph, int from, int to, double costs, int id  )
00112 {
00113     int ret;
00114     dglInt32_t dglcosts;
00115     
00116     G_debug (3, "Vect_add_edge() from = %d to = %d, costs = %f, id = %d", from, to, costs, id ); 
00117 
00118     dglcosts = (dglInt32_t) costs * 1000;
00119             
00120     ret = dglAddEdge ( graph, (dglInt32_t)from, (dglInt32_t)to, dglcosts, (dglInt32_t)id );
00121     if ( ret < 0 ) G_fatal_error ("Cannot add network arc");
00122 }
00123 
00133 void
00134 Vect_graph_set_node_costs ( GRAPH *graph, int node, double costs )
00135 {
00136     dglInt32_t dglcosts;
00137     
00138     /* TODO: Not tested! */
00139     G_debug (3, "Vect_graph_set_node_costs()" ); 
00140 
00141     dglcosts = (dglInt32_t) costs * 1000;
00142             
00143     dglNodeSet_Attr(graph, dglGetNode(graph, (dglInt32_t)node), &dglcosts); 
00144 }
00145 
00159 int
00160 Vect_graph_shortest_path ( GRAPH *graph, int from, int to, struct ilist *List, double *cost ) 
00161 {
00162     int i, line, *pclip, cArc, nRet;
00163     dglSPReport_s * pSPReport;
00164     dglInt32_t nDistance;
00165 
00166     G_debug (3, "Vect_graph_shortest_path(): from = %d, to = %d", from, to ); 
00167     
00168     /* Note : if from == to dgl goes to nearest node and returns back (dgl feature) => 
00169     *         check here for from == to */
00170     
00171     if ( List != NULL ) Vect_reset_list ( List);
00172 
00173     /* Check if from and to are identical, otherwise dglib returns path to neares node and back! */
00174     if ( from == to ) {
00175         if ( cost != NULL ) *cost = 0;
00176         return 0;
00177     }
00178 
00179     From_node = from;
00180 
00181     pclip = NULL;
00182     if ( List != NULL ) {
00183         nRet = dglShortestPath ( graph, &pSPReport, (dglInt32_t)from, (dglInt32_t)to, clipper, pclip, NULL);
00184     } else {
00185         nRet = dglShortestDistance ( graph, &nDistance, (dglInt32_t)from, (dglInt32_t)to, clipper, pclip, NULL);
00186     }
00187 
00188     if ( nRet == 0 ) {
00189         if ( cost != NULL )
00190            *cost = PORT_DOUBLE_MAX;
00191         return -1;
00192     }
00193     else if ( nRet < 0 ) {
00194         fprintf( stderr , "dglShortestPath error: %s\n", dglStrerror( graph ) );
00195         return -1;
00196     }
00197     
00198     if ( List != NULL ) {
00199         for( i = 0 ; i < pSPReport->cArc ; i ++ ) {
00200             line = dglEdgeGet_Id(graph, pSPReport->pArc[i].pnEdge);
00201             G_debug( 2, "From %ld to %ld - cost %ld user %d distance %ld" ,
00202                           pSPReport->pArc[i].nFrom,
00203                           pSPReport->pArc[i].nTo,
00204                           /* this is the cost from clip() */
00205                           dglEdgeGet_Cost(graph, pSPReport->pArc[i].pnEdge) / 1000, 
00206                           line,
00207                           pSPReport->pArc[i].nDistance );
00208             Vect_list_append ( List, line );
00209         }
00210     }
00211 
00212     if ( cost != NULL ) {
00213         if ( List != NULL ) 
00214             *cost = (double) pSPReport->nDistance /  1000;
00215         else    
00216             *cost = (double) nDistance / 1000;
00217     }
00218         
00219     if ( List != NULL ) {
00220         cArc = pSPReport->cArc;
00221         dglFreeSPReport( graph, pSPReport );
00222     } else
00223         cArc = 0;
00224 
00225     return (cArc);
00226 }
00227 

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5