Branch data     Line data    Source code

       1                 :            : /***************************************************************************
       2                 :            :   qgsgraphanalyzer.cpp
       3                 :            :   --------------------------------------
       4                 :            :   Date                 : 2011-04-14
       5                 :            :   Copyright            : (C) 2010 by Yakushev Sergey
       6                 :            :   Email                : YakushevS <at> list.ru
       7                 :            : ****************************************************************************
       8                 :            : *                                                                          *
       9                 :            : *   This program is free software; you can redistribute it and/or modify   *
      10                 :            : *   it under the terms of the GNU General Public License as published by   *
      11                 :            : *   the Free Software Foundation; either version 2 of the License, or      *
      12                 :            : *   (at your option) any later version.                                    *
      13                 :            : *                                                                          *
      14                 :            : ***************************************************************************/
      15                 :            : 
      16                 :            : #include <limits>
      17                 :            : 
      18                 :            : #include <QMap>
      19                 :            : #include <QVector>
      20                 :            : #include <QPair>
      21                 :            : 
      22                 :            : #include "qgsgraph.h"
      23                 :            : #include "qgsgraphanalyzer.h"
      24                 :            : 
      25                 :          0 : void QgsGraphAnalyzer::dijkstra( const QgsGraph *source, int startPointIdx, int criterionNum, QVector<int> *resultTree, QVector<double> *resultCost )
      26                 :            : {
      27                 :          0 :   if ( startPointIdx < 0 || startPointIdx >= source->vertexCount() )
      28                 :            :   {
      29                 :            :     // invalid start point
      30                 :          0 :     return;
      31                 :            :   }
      32                 :            : 
      33                 :          0 :   QVector< double > *result = nullptr;
      34                 :          0 :   if ( resultCost )
      35                 :            :   {
      36                 :          0 :     result = resultCost;
      37                 :          0 :   }
      38                 :            :   else
      39                 :            :   {
      40                 :          0 :     result = new QVector<double>();
      41                 :            :   }
      42                 :            : 
      43                 :          0 :   result->clear();
      44                 :          0 :   result->insert( result->begin(), source->vertexCount(), std::numeric_limits<double>::infinity() );
      45                 :          0 :   ( *result )[ startPointIdx ] = 0.0;
      46                 :            : 
      47                 :          0 :   if ( resultTree )
      48                 :            :   {
      49                 :          0 :     resultTree->clear();
      50                 :          0 :     resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );
      51                 :          0 :   }
      52                 :            : 
      53                 :            :   // QMultiMap< cost, vertexIdx > not_begin
      54                 :            :   // I use it and don't create any struct or class
      55                 :          0 :   QMultiMap< double, int > not_begin;
      56                 :          0 :   QMultiMap< double, int >::iterator it;
      57                 :            : 
      58                 :          0 :   not_begin.insert( 0.0, startPointIdx );
      59                 :            : 
      60                 :          0 :   while ( !not_begin.empty() )
      61                 :            :   {
      62                 :          0 :     it = not_begin.begin();
      63                 :          0 :     double curCost = it.key();
      64                 :          0 :     int curVertex = it.value();
      65                 :          0 :     not_begin.erase( it );
      66                 :            : 
      67                 :            :     // edge index list
      68                 :          0 :     const QgsGraphEdgeIds &outgoingEdges = source->vertex( curVertex ).outgoingEdges();
      69                 :          0 :     for ( int edgeId : outgoingEdges )
      70                 :            :     {
      71                 :          0 :       const QgsGraphEdge &arc = source->edge( edgeId );
      72                 :          0 :       double cost = arc.cost( criterionNum ).toDouble() + curCost;
      73                 :            : 
      74                 :          0 :       if ( cost < ( *result )[ arc.toVertex()] )
      75                 :            :       {
      76                 :          0 :         ( *result )[ arc.toVertex()] = cost;
      77                 :          0 :         if ( resultTree )
      78                 :            :         {
      79                 :          0 :           ( *resultTree )[ arc.toVertex()] = edgeId;
      80                 :          0 :         }
      81                 :          0 :         not_begin.insert( cost, arc.toVertex() );
      82                 :          0 :       }
      83                 :            :     }
      84                 :          0 :   }
      85                 :          0 :   if ( !resultCost )
      86                 :            :   {
      87                 :          0 :     delete result;
      88                 :          0 :   }
      89                 :          0 : }
      90                 :            : 
      91                 :          0 : QgsGraph *QgsGraphAnalyzer::shortestTree( const QgsGraph *source, int startVertexIdx, int criterionNum )
      92                 :            : {
      93                 :          0 :   QgsGraph *treeResult = new QgsGraph();
      94                 :          0 :   QVector<int> tree;
      95                 :            : 
      96                 :          0 :   QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
      97                 :            : 
      98                 :            :   // sourceVertexIdx2resultVertexIdx
      99                 :          0 :   QVector<int> source2result( tree.size(), -1 );
     100                 :            : 
     101                 :            :   // Add reachable vertices to the result
     102                 :          0 :   source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
     103                 :          0 :   int i = 0;
     104                 :          0 :   for ( i = 0; i < source->vertexCount(); ++i )
     105                 :            :   {
     106                 :          0 :     if ( tree[ i ] != -1 )
     107                 :            :     {
     108                 :          0 :       source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
     109                 :          0 :     }
     110                 :          0 :   }
     111                 :            : 
     112                 :            :   // Add arcs to the result
     113                 :          0 :   for ( i = 0; i < source->vertexCount(); ++i )
     114                 :            :   {
     115                 :          0 :     if ( tree[ i ] != -1 )
     116                 :            :     {
     117                 :          0 :       const QgsGraphEdge &arc = source->edge( tree[i] );
     118                 :            : 
     119                 :          0 :       treeResult->addEdge( source2result[ arc.fromVertex()], source2result[ arc.toVertex()],
     120                 :          0 :                            arc.strategies() );
     121                 :          0 :     }
     122                 :          0 :   }
     123                 :            : 
     124                 :          0 :   return treeResult;
     125                 :          0 : }