← Back to branch summary

~ubuntu-branches/ubuntu/precise/grass/precise

« back to all changes in this revision

Viewing changes to lib/vector/dglib/sp-template.c

  • Committer: Bazaar Package Importer
  • Author(s): Francesco Paolo Lovergine
  • Date: 2011-04-13 17:08:41 UTC
  • mfrom: (8.1.7 sid)
  • Revision ID: james.westby@ubuntu.com-20110413170841-ss1t9bic0d0uq0gz
Tags: 6.4.1-1
* New upstream version.
* Now build-dep on libjpeg-dev and current libreadline6-dev.
* Removed patch swig: obsolete.
* Policy bumped to 3.9.2, without changes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/vector/dglib/sp-template.c
23
23
 
24
24
/*
25
25
 * SHORTEST PATH CACHE
 
26
 * 
 
27
 * components:
 
28
 *   - start node id
 
29
 *   - visited network: a node is marked as visited when its departing
 
30
 *     edges have been added to the cache
 
31
 *   - predist network: node distances from start node
 
32
 *   - NodeHeap: holds unvisited nodes, the next node extracted is the
 
33
 *     unvisited node closest to SP start
 
34
 *
 
35
 * not all nodes in the predist network have been visited, SP from start
 
36
 * is known only for visited nodes
 
37
 * unvisited nodes can be reached, but not necessarily on the shortest
 
38
 * possible path
 
39
 * important for DGL_SP_CACHE_DISTANCE_FUNC and DGL_SP_CACHE_REPORT_FUNC
26
40
 */
 
41
 
27
42
#if !defined(DGL_DEFINE_TREE_PROCS) && !defined(DGL_DEFINE_FLAT_PROCS)
28
43
 
29
44
int DGL_SP_CACHE_INITIALIZE_FUNC(dglGraph_s * pgraph, dglSPCache_s * pCache,
60
75
                                      dglInt32_t nStart,
61
76
                                      dglInt32_t nDestination)
62
77
{
63
 
    dglTreeTouchI32_s *pVisitedItem, VisitedItem;
 
78
    dglTreeTouchI32_s VisitedItem;
64
79
    dglTreePredist_s *pPredistItem, PredistItem;
65
80
 
66
81
    if (pCache->nStartNode != nStart) {
69
84
    }
70
85
 
71
86
    VisitedItem.nKey = nDestination;
72
 
    if ((pVisitedItem = avl_find(pCache->pvPredist, &VisitedItem)) == NULL) {
 
87
    if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
73
88
        pgraph->iErrno = DGL_ERR_TailNodeNotFound;
74
89
        return -pgraph->iErrno;
75
90
    }
106
121
    }
107
122
 
108
123
    VisitedItem.nKey = nDestination;
109
 
 
110
124
    if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
111
125
        pgraph->iErrno = DGL_ERR_TailNodeNotFound;
112
126
        return NULL;
113
127
    }
114
128
 
 
129
    PredistItem.nKey = nDestination;
 
130
    if (avl_find(pCache->pvPredist, &PredistItem) == NULL) {
 
131
        pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
 
132
        return NULL;
 
133
    }
 
134
 
115
135
    for (PredistItem.nKey = nDestination,
116
136
         pPredistItem = avl_find(pCache->pvPredist, &PredistItem);
117
137
         pPredistItem;
312
332
    dglEdgesetTraverser_s laT;
313
333
 
314
334
    dglSPCache_s spCache;
 
335
    int new_cache = 0;
315
336
 
316
337
    /*
317
338
     * shortest path distance temporary min heap
346
367
    if (pCache == NULL) {
347
368
        pCache = &spCache;
348
369
        DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart);
 
370
        new_cache = 1;
349
371
    }
350
372
    else {
351
373
        if (ppReport) {
364
386
        if (pgraph->iErrno == DGL_ERR_HeadNodeNotFound) {
365
387
            DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
366
388
            DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart);
 
389
            new_cache = 1;
367
390
        }
368
391
        else if (pgraph->iErrno != DGL_ERR_TailNodeNotFound) {
369
392
            goto sp_error;
370
393
        }
371
 
        /*
372
 
         * reset visited status for existing cache: fix for BUG1
373
 
         */
374
 
        if (pCache->pvVisited) {
375
 
            avl_destroy(pCache->pvVisited, dglTreeTouchI32Cancel);
376
 
 
377
 
            if ((pCache->pvVisited =
378
 
                avl_create(dglTreeTouchI32Compare, NULL,
379
 
                        dglTreeGetAllocator())) == NULL)
380
 
                return -1;
381
 
        }
382
394
    }
383
395
 
384
396
    /*
409
421
        goto sp_error;
410
422
    }
411
423
 
412
 
    /*
413
 
     * now we inspect all edges departing from the start node
414
 
     * - at each loop 'pedge' points to the edge in the edge buffer
415
 
     * - we invoke the caller's clip() and eventually skip the edge (clip() != 0)
416
 
     * - we insert a item in the predist network to set actual predecessor and distance
417
 
     *   (there is no precedecessor at this stage) and actual distance from the starting node
418
 
     *   (at this stage it equals the edge's cost)
419
 
     * - we insert a item in the node min-heap (sorted on node distance), storing the offset of the
420
 
     *   edge in the edge buffer.
421
 
     * In the case of undirected graph (version 3) we inspect input edges as well.
422
 
     */
423
 
    pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
424
 
    if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
425
 
        goto sp_error;
426
 
    }
427
 
    for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
428
 
         pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
429
 
        ) {
430
 
        __EDGELOOP_BODY_1(0);
431
 
    }
432
 
    DGL_EDGESET_T_RELEASE_FUNC(&laT);
433
 
 
434
 
    if (pgraph->Version == 3) {
435
 
        pEdgeset = _DGL_INEDGESET(pgraph, pStart);
 
424
    /* if we do not need a new cache, we just continue with the unvisited
 
425
     * nodes in the cache */
 
426
    if (new_cache) {
 
427
        /*
 
428
         * now we inspect all edges departing from the start node
 
429
         * - at each loop 'pedge' points to the edge in the edge buffer
 
430
         * - we invoke the caller's clip() and eventually skip the edge (clip() != 0)
 
431
         * - we insert a item in the predist network to set actual predecessor and distance
 
432
         *   (there is no precedecessor at this stage) and actual distance from the starting node
 
433
         *   (at this stage it equals the edge's cost)
 
434
         * - we insert a item in the node min-heap (sorted on node distance), storing the offset of the
 
435
         *   edge in the edge buffer.
 
436
         * In the case of undirected graph (version 3) we inspect input edges as well.
 
437
         */
 
438
        pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
436
439
        if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
437
440
            goto sp_error;
438
441
        }
439
442
        for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
440
443
             pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
441
444
            ) {
442
 
            if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
443
 
                continue;
444
 
            __EDGELOOP_BODY_1(1);
 
445
            __EDGELOOP_BODY_1(0);
445
446
        }
446
447
        DGL_EDGESET_T_RELEASE_FUNC(&laT);
 
448
 
 
449
        if (pgraph->Version == 3) {
 
450
            pEdgeset = _DGL_INEDGESET(pgraph, pStart);
 
451
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
 
452
                goto sp_error;
 
453
            }
 
454
            for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
 
455
                 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
 
456
                ) {
 
457
                if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
 
458
                    continue;
 
459
                __EDGELOOP_BODY_1(1);
 
460
            }
 
461
            DGL_EDGESET_T_RELEASE_FUNC(&laT);
 
462
        }
447
463
    }
448
464
 
449
 
 
450
465
    /*
451
466
     * Now we begin extracting nodes from the min-heap. Each node extracted is
452
467
     * the one that is actually closest to the SP start.
470
485
            pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge); /* reversed head/tail */
471
486
        }
472
487
 
473
 
 
474
488
        /*
475
489
         * We do not want to explore twice the same node as a relative starting point,
476
490
         * that's the meaning of 'visited'. We mark actual start node as 'visited' by
488
502
        }
489
503
 
490
504
        /*
491
 
         * Dijkstra algorithm ends when the destination node is extracted from
492
 
         * the min distance heap, that means: no other path exist in the network giving
493
 
         * a shortest output.
494
 
         * If this happens we jump to the epilogue in order to build a path report and return.
495
 
         */
496
 
        if (DGL_NODE_ID(pStart) == nDestination) {
497
 
            goto destination_found;
498
 
        }
499
 
 
500
 
        /*
501
505
         * Give up with visited nodes now
502
506
         */
503
507
        if (pVisitedItem) {
504
 
            continue;
 
508
            if (DGL_NODE_ID(pStart) == nDestination) {
 
509
                /* should not happen but does not harm
 
510
                 * this case should have been handled above */
 
511
                goto destination_found;
 
512
            }
 
513
            else
 
514
                continue;
505
515
        }
506
516
 
507
517
        /*
509
519
         * blind alley. Just give up this direction and continue looping.
510
520
         * This only applies to v1 and v2 (digraphs)
511
521
         */
512
 
        if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3)
513
 
            continue;
 
522
        if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
 
523
            if (DGL_NODE_ID(pStart) == nDestination) {
 
524
                goto destination_found;
 
525
            }
 
526
            else
 
527
                continue;
 
528
        }
514
529
 
515
530
        /*
516
531
         * save actual edge for later clip()
534
549
         * Scan the edgeset and loads pedge at each iteration with next-edge.
535
550
         * iWay == DGL_EDGESET_T_WAY_OUT then pedge is a out arc (departing from node) else ot is a in arc.
536
551
         * V1 has no in-degree support so iWay is always OUT, V2/3 have in-degree support.
 
552
         *
 
553
         * This loop needs to be done also when destination is found, otherwise
 
554
         * the node is marked as visited but its departing edges are not added to the cache
 
555
         * --> loose end, we might need these edges later on
537
556
         */
538
557
        pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
539
558
        if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
560
579
            }
561
580
            DGL_EDGESET_T_RELEASE_FUNC(&laT);
562
581
        }
 
582
 
 
583
        /*
 
584
         * Dijkstra algorithm ends when the destination node is extracted from
 
585
         * the min distance heap, that means: no other path exist in the network giving
 
586
         * a shortest output.
 
587
         * If this happens we jump to the epilogue in order to build a path report and return.
 
588
         */
 
589
        if (DGL_NODE_ID(pStart) == nDestination) {
 
590
            goto destination_found;
 
591
        }
563
592
    }
564
593
 
565
594
  sp_error:
566
595
    if (pCache == &spCache) {
567
596
        DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
568
597
    }
569
 
    return -pgraph->iErrno;     /* ==0 path not found */
 
598
    return -pgraph->iErrno;     /* == 0 path not found */
570
599
 
571
600
  destination_found:            /* path found - build a shortest path report or report the distance only */
572
601