ext/OGDF/src/graphalg/PageRank.cpp

   1 /*
   2  * $Revision: 2597 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-15 19:26:11 +0200 (So, 15. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of basic page rank.
  11  *
  12  * \author Martin Gronemann
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include <ogdf/graphalg/PageRank.h>
  45
  46 namespace ogdf {
  47
  48
  49 void BasicPageRank::call(
  50         const Graph& graph,
  51         const EdgeArray<double>& edgeWeight,
  52         NodeArray<double>& pageRankResult)
  53 {
  54         const double initialPageRank = 1.0 / (double)graph.numberOfNodes();
  55         const double maxPageRankDeltaBound = initialPageRank * m_threshold;
  56
  57         // the two ping pong buffer
  58         NodeArray<double> pageRankPing(graph, 0.0);
  59         NodeArray<double> pageRankPong(graph, 0.0);
  60
  61         NodeArray<double>* pCurrPageRank = &pageRankPing;
  62         NodeArray<double>* pNextPageRank = &pageRankPong;
  63
  64         NodeArray<double> nodeNorm(graph);
  65
  66         for (node v = graph.firstNode(); v; v = v->succ())
  67         {
  68                 double sum = 0.0;
  69                 for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ())
  70                 {
  71                         edge e = adj->theEdge();
  72                         sum += edgeWeight[e];
  73                 }
  74                 nodeNorm[v] = 1.0 / sum;
  75         }
  76
  77         pCurrPageRank->init(graph, initialPageRank);
  78
  79         // main iteration loop
  80         int numIterations = 0;
  81         bool converged = false;
  82         // check conditions
  83         while ( !converged && (numIterations < m_maxNumIterations) )
  84         {
  85                 // init the result of this iteration
  86                 pNextPageRank->init(graph, (1.0 - m_dampingFactor) / (double)graph.numberOfNodes());
  87                 // calculate the transfer between each node
  88                 for (edge e = graph.firstEdge(); e; e = e->succ())
  89                 {
  90                         node v = e->source();
  91                         node w = e->target();
  92
  93                         double vwTransfer = (edgeWeight[e] * nodeNorm[v] * (*pCurrPageRank)[v]);
  94                         double wvTransfer = (edgeWeight[e] * nodeNorm[w] * (*pCurrPageRank)[w]);
  95                         (*pNextPageRank)[w] += vwTransfer;
  96                         (*pNextPageRank)[v] += wvTransfer;
  97                 }
  98
  99                 // damping and calculating change
 100                 double maxPageRankDelta = 0.0;
 101                 for (node v = graph.firstNode(); v; v = v->succ())
 102                 {
 103                         (*pNextPageRank)[v] *= m_dampingFactor;
 104                         double pageRankDelta = fabs((*pNextPageRank)[v] - (*pCurrPageRank)[v]);
 105                         maxPageRankDelta = std::max(maxPageRankDelta, pageRankDelta);
 106                 }
 107
 108                 // swap ping and pong, pong ping, ping pong, lalalala
 109                 std::swap(pNextPageRank, pCurrPageRank);
 110                 numIterations++;
 111
 112                 // check if the change is small enough
 113                 converged = (maxPageRankDelta < maxPageRankDeltaBound);
 114         }
 115
 116         // normalization
 117         double maxPageRank = (*pCurrPageRank)[graph.firstNode()];
 118         double minPageRank = (*pCurrPageRank)[graph.firstNode()];
 119         for (node v = graph.firstNode(); v; v = v->succ())
 120         {
 121                 maxPageRank = std::max(maxPageRank, (*pCurrPageRank)[v]);
 122                 minPageRank = std::min(minPageRank, (*pCurrPageRank)[v]);
 123         }
 124
 125         // init result
 126         pageRankResult.init(graph);
 127         for (node v = graph.firstNode(); v; v = v->succ())
 128         {
 129                 double r = ((*pCurrPageRank)[v] - minPageRank) / (maxPageRank - minPageRank);
 130                 pageRankResult[v] = r;
 131         }
 132         // result is now between 0 and 1
 133 }
 134
 135 } // end of namespace ogdf