Graph.C

Go to the documentation of this file.
00001 /*!@file Beobot/Graph.C basic graph class can be both directed
00002   and undirected                                                        */
00003 // //////////////////////////////////////////////////////////////////// //
00004 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2001 by the //
00005 // University of Southern California (USC) and the iLab at USC.         //
00006 // See http://iLab.usc.edu for information about this project.          //
00007 // //////////////////////////////////////////////////////////////////// //
00008 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
00009 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
00010 // in Visual Environments, and Applications'' by Christof Koch and      //
00011 // Laurent Itti, California Institute of Technology, 2001 (patent       //
00012 // pending; application number 09/912,225 filed July 23, 2001; see      //
00013 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
00014 // //////////////////////////////////////////////////////////////////// //
00015 // This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
00016 //                                                                      //
00017 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
00018 // redistribute it and/or modify it under the terms of the GNU General  //
00019 // Public License as published by the Free Software Foundation; either  //
00020 // version 2 of the License, or (at your option) any later version.     //
00021 //                                                                      //
00022 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
00023 // that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
00024 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
00025 // PURPOSE.  See the GNU General Public License for more details.       //
00026 //                                                                      //
00027 // You should have received a copy of the GNU General Public License    //
00028 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
00029 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
00030 // Boston, MA 02111-1307 USA.                                           //
00031 // //////////////////////////////////////////////////////////////////// //
00032 //
00033 // Primary maintainer for this file: Christian Siagian <siagian@usc.edu>
00034 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/Beobot/Graph.C $
00035 // $Id $
00036 //
00037 
00038 #include "Beobot/Graph.H"
00039 #include "Image/Image.H"
00040 #include "Image/MathOps.H"
00041 #include <unistd.h>
00042 
00043 #include "Raster/Raster.H"
00044 
00045 // ######################################################################
00046 Graph::Graph():
00047   itsNodes(),
00048   itsEdges(),
00049   itsDirectedAdjecencyList(),
00050   itsDirectedAdjecencyCostList(),
00051   itsDirectedAdjecencyInEdgeList(),
00052   itsDirectedAdjecencyOutEdgeList(),
00053   itsUndirectedAdjecencyList(),
00054   itsUndirectedAdjecencyCostList(),
00055   itsUndirectedAdjecencyEdgeList(),
00056   itsDirectedPathList(),
00057   itsUndirectedPathList()
00058 {
00059   itsDistanceMatrixComputed = false;
00060 }
00061 
00062 // ######################################################################
00063 Graph::Graph(std::vector<rutz::shared_ptr<Node> > nodes,
00064              std::vector<rutz::shared_ptr<Edge> > edges):
00065   itsNodes(),
00066   itsEdges(),
00067   itsDirectedAdjecencyList(),
00068   itsDirectedAdjecencyCostList(),
00069   itsDirectedAdjecencyInEdgeList(),
00070   itsDirectedAdjecencyOutEdgeList(),
00071   itsUndirectedAdjecencyList(),
00072   itsUndirectedAdjecencyCostList(),
00073   itsUndirectedAdjecencyEdgeList(),
00074   itsDirectedPathList(),
00075   itsUndirectedPathList()
00076 {
00077   for(uint i = 0; i < nodes.size(); i++)
00078     itsNodes.push_back(nodes[i]);
00079 
00080   for(uint i = 0; i < edges.size(); i++)
00081     itsEdges.push_back(edges[i]);
00082 
00083   itsDistanceMatrixComputed = false;
00084 }
00085 
00086 // ######################################################################
00087 Graph::~Graph()
00088 { }
00089 
00090 // ######################################################################
00091 void Graph::addNode(rutz::shared_ptr<Node> node)
00092 {
00093   itsNodes.push_back(node);
00094 }
00095 
00096 // ######################################################################
00097 void Graph::addEdge(rutz::shared_ptr<Edge> edge)
00098 {
00099   itsEdges.push_back(edge);
00100 }
00101 
00102 // ######################################################################
00103 void Graph::computeAdjecencyList()
00104 {
00105   itsDirectedAdjecencyList.resize(itsNodes.size());
00106   itsDirectedAdjecencyCostList.resize(itsNodes.size());
00107   itsDirectedAdjecencyInEdgeList.resize(itsNodes.size());
00108   itsDirectedAdjecencyOutEdgeList.resize(itsNodes.size());
00109 
00110   itsUndirectedAdjecencyList.resize(itsNodes.size());
00111   itsUndirectedAdjecencyCostList.resize(itsNodes.size());
00112   itsUndirectedAdjecencyEdgeList.resize(itsNodes.size());
00113 
00114   // for each edge get the nodes
00115   for(uint i = 0; i < itsEdges.size(); i++)
00116     {
00117       uint sind = itsEdges[i]->getSourceNode()->getIndex();
00118       uint dind = itsEdges[i]->getDestNode()->getIndex();
00119       float cost = itsEdges[i]->getCost();
00120       LINFO("[%d -> %d]: %f", sind, dind, cost);
00121 
00122       // adjecency list:
00123 
00124       //for directed case
00125       itsDirectedAdjecencyList[sind].push_back(dind);
00126       itsDirectedAdjecencyCostList[sind].push_back(cost);
00127 
00128       itsDirectedAdjecencyInEdgeList[dind].push_back(i);
00129       itsDirectedAdjecencyOutEdgeList[sind].push_back(i);
00130 
00131       //for undirected case
00132       itsUndirectedAdjecencyList[sind].push_back(dind);
00133       itsUndirectedAdjecencyList[dind].push_back(sind);
00134       itsUndirectedAdjecencyCostList[sind].push_back(cost);
00135       itsUndirectedAdjecencyCostList[dind].push_back(cost);
00136 
00137       itsUndirectedAdjecencyEdgeList[dind].push_back(i);
00138       itsUndirectedAdjecencyEdgeList[sind].push_back(i);
00139     }
00140 }
00141 
00142 // ######################################################################
00143 void Graph::computeDistances()
00144 {
00145   // to avoid flag in getDistance()
00146   itsDistanceMatrixComputed = false;
00147   uint nnode = itsNodes.size();
00148 
00149   // create distance matrix
00150   itsDirectedDistanceMatrix.resize(nnode, nnode);
00151   itsDirectedPathList.resize(nnode);
00152   itsUndirectedDistanceMatrix.resize(nnode, nnode);
00153   itsUndirectedPathList.resize(nnode);
00154   for(uint i = 0; i < nnode; i++)
00155     {
00156       itsDirectedPathList[i].resize(nnode);
00157       itsUndirectedPathList[i].resize(nnode);
00158     }
00159 
00160   for(uint i = 0; i < nnode; i++)
00161     {
00162       for(uint j = 0; j < nnode; j++)
00163         {
00164           // directed case
00165           std::vector<uint> dedges;
00166           float ddist = getDirectedDistance(i,j, dedges);
00167           itsDirectedDistanceMatrix.setVal(i,j, ddist);
00168           itsDirectedPathList[i][j] = dedges;
00169 
00170           // undirected case
00171           std::vector<uint> uedges;
00172           float udist = getUndirectedDistance(i,j, uedges);
00173           itsUndirectedDistanceMatrix.setVal(i,j, udist);
00174           itsUndirectedPathList[i][j] = uedges;
00175         }
00176     }
00177   itsDistanceMatrixComputed = true;
00178 }
00179 
00180 // ######################################################################
00181 float Graph::getDirectedDistance(uint a, uint b)
00182 {
00183   std::vector<uint> edges;
00184   return getDirectedDistance(a, b, edges);
00185 }
00186 
00187 // ######################################################################
00188 float Graph::getDirectedDistance
00189 (uint a, uint b, std::vector<uint> &edges)
00190 {
00191   ASSERT(a < itsNodes.size() && b < itsNodes.size());
00192   if(a == b) return 0.0F;
00193 
00194   if(itsDistanceMatrixComputed)
00195     {
00196       edges.clear();
00197       for(uint i = 0; i < itsDirectedPathList[a][b].size(); i++)
00198         edges.push_back(itsDirectedPathList[a][b][i]);
00199       return itsDirectedDistanceMatrix[Point2D<int>(a,b)];
00200     }
00201 
00202   uint nnode = itsNodes.size();
00203   std::vector<float> edist(nnode);
00204   std::vector<uint>  epath(nnode);
00205 
00206   // NOTE: this is Dijkstra algorithm
00207   //       we can't have negative edges
00208   for(uint i = 0; i < nnode; i++) edist[i] = -1.0F;
00209   std::vector<bool> selected(nnode);
00210   for(uint i = 0; i < nnode; i++) selected[i] = false;
00211 
00212   // Directed edges
00213   uint nsadj = itsDirectedAdjecencyList[a].size();
00214   for(uint i = 0; i < nsadj; i++)
00215     {
00216       uint adjnode   = itsDirectedAdjecencyList[a][i];
00217       edist[adjnode] = itsDirectedAdjecencyCostList[a][i];
00218       epath[adjnode] = itsDirectedAdjecencyOutEdgeList[a][i];
00219     }
00220   edist[a] = 0.0F; selected[a] = true;
00221 
00222   //for(uint ii = 0; ii < edist.size(); ii++)
00223   //  LINFO("[%d]: %d %f",ii, int(selected[ii]), edist[ii]);
00224 
00225   // while the minimum vertex is not our destination
00226   // or all the queue minimums are negative (can't reach anything else)
00227   // for un-connected graph
00228   uint mindex = a; bool end = false;
00229   while(mindex != b && !end)
00230     {
00231       // find the minimum distance in the queue
00232       float mindist = -1.0F;
00233       for(uint i = 0; i < nnode; i++)
00234         if(!selected[i] && edist[i] != -1.0F &&
00235            (mindist == -1.0F || mindist > edist[i]))
00236           {
00237             mindist = edist[i]; mindex = i;
00238             //LINFO("in: %d: mindex: %d mindist: %f", i, mindex, mindist);
00239           }
00240 
00241       //LINFO("min index[%d] %f", mindex, edist[mindex]);
00242 
00243       // if we still have a reacheable node
00244       if(mindist != -1.0F)
00245         {
00246           selected[mindex] = true;
00247 
00248           uint nadj = itsDirectedAdjecencyList[mindex].size();
00249           for(uint i = 0; i < nadj; i++)
00250             {
00251               uint eindex   = itsDirectedAdjecencyOutEdgeList[mindex][i];
00252               uint adjindex = itsDirectedAdjecencyList[mindex][i];
00253               float cost    = itsDirectedAdjecencyCostList[mindex][i];
00254 
00255               //LINFO("eindex: %d adjindex: %d cost: %f", eindex, adjindex, cost);
00256 
00257               if(edist[adjindex] == -1.0F ||
00258                  edist[adjindex] > edist[mindex] + cost)
00259                 {
00260                   //LINFO("relaxing: %d: %f -> %f", adjindex,
00261                   //      edist[adjindex], edist[mindex] + cost);
00262                   edist[adjindex] = edist[mindex] + cost;
00263                   epath[adjindex] = eindex;
00264 
00265                   //LINFO("edist[%d]: %f epath[%d]: %d",
00266                   //      adjindex, edist[adjindex],
00267                   //      adjindex, epath[adjindex]);
00268                 }
00269             }
00270         }
00271       else { end = true; }
00272 
00273       //for(uint ii = 0; ii < edist.size(); ii++)
00274       //  LINFO("[%d]: %d %f",ii, int(selected[ii]), edist[ii]);
00275     }
00276 
00277   // use the distances to calculate the list of edges
00278   edges.clear();
00279 
00280   // if node b is not unreachable
00281   if(edist[b] != -1.0F)
00282     {
00283       std::vector<uint> tEdges;
00284       // backtrack from the destination
00285       uint index = b;
00286       while(index != a)
00287         {
00288           tEdges.push_back(epath[index]);
00289           //LINFO("index: %d: epath: %d",index, epath[index]);
00290           index = getEdge(epath[index])->getSourceNode()->getIndex();
00291         }
00292       for(int i = tEdges.size()-1; i >= 0; i--)
00293         edges.push_back(tEdges[i]);
00294     }
00295 
00296   return edist[b];
00297 }
00298 
00299 // ######################################################################
00300 float Graph::getUndirectedDistance(uint a, uint b)
00301 {
00302   std::vector<uint> edges;
00303   return getUndirectedDistance(a, b, edges);
00304 }
00305 
00306 // ######################################################################
00307 float Graph::getUndirectedDistance
00308 (uint a, uint b, std::vector<uint> &edges)
00309 {
00310   ASSERT(a < itsNodes.size() && b < itsNodes.size());
00311   if(a == b) return 0.0F;
00312   //LINFO("a: %d, b: %d", a, b);
00313 
00314   if(itsDistanceMatrixComputed)
00315     {
00316       edges.clear();
00317       for(uint i = 0; i < itsUndirectedPathList[a][b].size(); i++)
00318         {
00319           edges.push_back(itsUndirectedPathList[a][b][i]);
00320           //LINFO("edge[%d]: %d", i, edges[i]);
00321         }
00322       return itsUndirectedDistanceMatrix[Point2D<int>(a,b)];
00323     }
00324 
00325   uint nnode = itsNodes.size();
00326   std::vector<float> edist(nnode);
00327   std::vector<uint>  epath(nnode);
00328 
00329   // NOTE: this is Dijkstra algorithm
00330   //       we can't have negative edges
00331   for(uint i = 0; i < nnode; i++) edist[i] = -1.0F;
00332   std::vector<bool> selected(nnode);
00333   for(uint i = 0; i < nnode; i++) selected[i] = false;
00334 
00335   // undirected edges
00336   uint nsadj = itsUndirectedAdjecencyList[a].size();
00337   //LINFO("nsadj: %d", nsadj);
00338   for(uint i = 0; i < nsadj; i++)
00339     {
00340       uint adjnode = itsUndirectedAdjecencyList[a][i];
00341       edist[adjnode] = itsUndirectedAdjecencyCostList[a][i];
00342       epath[adjnode] = itsUndirectedAdjecencyEdgeList[a][i];
00343     }
00344   edist[a] = 0.0F; selected[a] = true;
00345 
00346   // for(uint ii = 0; ii < edist.size(); ii++)
00347   //   LINFO("[%d]:sel:%d %f ep:%d",
00348   //         ii, int(selected[ii]), edist[ii], epath[ii]);
00349 
00350   // while the minimum vertex is not our destination
00351   // or all the queue minimums are negative (can't reach anything else)
00352   // for un-connected graph
00353   uint mindex = a; bool end = false;
00354   while(mindex != b && !end)
00355     {
00356       // find the minimum distance in the queue
00357       float mindist = -1.0F;
00358       for(uint i = 0; i < nnode; i++)
00359         if(!selected[i] && edist[i] != -1.0F &&
00360            (mindist == -1.0F || mindist > edist[i]))
00361           {
00362             mindist = edist[i]; mindex = i;
00363             //LINFO("in: %d: mindex: %d mindist: %f", i, mindex, mindist);
00364           }
00365 
00366       //LINFO("min index[%d] %f", mindex, edist[mindex]);
00367 
00368       // if we still have a reacheable node
00369       if(mindist != -1.0F)
00370         {
00371           selected[mindex] = true;
00372 
00373           uint nadj = itsUndirectedAdjecencyList[mindex].size();
00374           for(uint i = 0; i < nadj; i++)
00375             {
00376               uint eindex   = itsUndirectedAdjecencyEdgeList[mindex][i];
00377               uint adjindex = itsUndirectedAdjecencyList[mindex][i];
00378               float cost    = itsUndirectedAdjecencyCostList[mindex][i];
00379 
00380               if(edist[adjindex] == -1.0F ||
00381                  edist[adjindex] > edist[mindex] + cost)
00382                 {
00383                   //LINFO("relaxing: %d: %f -> %f", adjindex,
00384                   //      edist[adjindex], edist[mindex] + cost);
00385                   edist[adjindex] = edist[mindex] + cost;
00386                   epath[adjindex] = eindex;
00387                 }
00388             }
00389         }
00390       else { end = true; }
00391 
00392       //for(uint ii = 0; ii < edist.size(); ii++)
00393       //  LINFO("[%d]: %d %f",ii, int(selected[ii]), edist[ii]);
00394     }
00395 
00396   // use the distances to calculate the list of edges
00397   edges.clear();
00398 
00399   // if node b is not unreachable
00400   if(edist[b] != -1.0F)
00401     {
00402       std::vector<uint> tEdges;
00403       // backtrack from the destination
00404       uint index = b;
00405       while(index != a)
00406         {
00407           tEdges.push_back(epath[index]);
00408           uint is = getEdge(epath[index])->getSourceNode()->getIndex();
00409           uint id = getEdge(epath[index])->getDestNode()->getIndex();
00410           if(index == is) index = id;
00411           else index = is;
00412           //LINFO("edge index: %d",index);
00413         }
00414 
00415       for(int i = tEdges.size()-1; i >= 0; i--)
00416         edges.push_back(tEdges[i]);
00417     }
00418   return edist[b];
00419 }
00420 
00421 // ######################################################################
00422 float Graph::getMaxDirectedDistance()
00423 {
00424   float min, max;
00425   getMinMax(itsDirectedDistanceMatrix, min, max);
00426   if(min == -1.0F) return -1.0F;
00427   else return max;
00428 }
00429 
00430 // ######################################################################
00431 float Graph::getMaxUndirectedDistance()
00432 {
00433   float min, max;
00434   getMinMax(itsUndirectedDistanceMatrix, min, max);
00435   if(min == -1.0F) return -1.0F;
00436   else return max;
00437 }
00438 
00439 // ######################################################################
00440 std::vector<uint> Graph::getDirectedPath(uint a, uint b)
00441 {
00442   std::vector<uint> edges;
00443 
00444   // if distance matrix is already computed
00445   if(itsDistanceMatrixComputed) return itsDirectedPathList[a][b];
00446   else
00447     {
00448       getDirectedDistance(a, b, edges);
00449       return edges;
00450     }
00451 }
00452 
00453 // ######################################################################
00454 std::vector<uint> Graph::getUndirectedPath(uint a, uint b)
00455 {
00456   std::vector<uint> edges;
00457 
00458   // if distance matrix is already computed
00459   if(itsDistanceMatrixComputed) return itsUndirectedPathList[a][b];
00460   else
00461     {
00462       getUndirectedDistance(a, b, edges);
00463       return edges;
00464     }
00465 }
00466 
00467 // ######################################################################
00468 std::vector<uint> Graph::getEdges(rutz::shared_ptr<Node> n)
00469 {
00470   std::vector<uint> res;
00471 
00472   // for each edge get the nodes
00473   for(uint i = 0; i < itsEdges.size(); i++)
00474     {
00475 
00476       //res.push_back();
00477     }
00478   LFATAL("not yet implemented");
00479 
00480   return res;
00481 }
00482 
00483 // ######################################################################
00484 float Graph::getAngle
00485 (rutz::shared_ptr<Edge> e1, rutz::shared_ptr<Edge> e2)
00486 {
00487   // get the end coordinates of each edge
00488   Point2D<int> s1 = e1->getSourceNode()->getCoordinate();
00489   Point2D<int> d1 = e1->getDestNode()->getCoordinate();
00490   Point2D<int> s2 = e2->getSourceNode()->getCoordinate();
00491   Point2D<int> d2 = e2->getDestNode()->getCoordinate();
00492   LDEBUG("(s1(%d,%d)-d1(%d,%d))-----(s2(%d,%d)-d2(%d,%d))",
00493          s1.i, s1.j,d1.i, d1.j, s2.i, s2.j,d2.i, d2.j);
00494 
00495   // calculate differences
00496   float xD1 = d1.i - s1.i;
00497   float xD2 = d2.i - s2.i;
00498   float yD1 = d1.j - s1.j;
00499   float yD2 = d2.j - s2.j;
00500 
00501   // calculate the lengths of the two lines
00502   float len1 = sqrt(xD1*xD1+yD1*yD1);
00503   float len2 = sqrt(xD2*xD2+yD2*yD2);
00504 
00505   float dot   = (xD1*xD2+yD1*yD2); // dot   product
00506   float cross = (xD1*yD2-xD2*yD1); // cross product
00507 
00508   // calculate angle between the two lines
00509   float ang = atan2(cross/(len1*len2), dot/(len1*len2));
00510   return ang;
00511 }
00512 
00513 // ######################################################################
00514 /* So things look consistent in everyone's emacs... */
00515 /* Local Variables: */
00516 /* indent-tabs-mode: nil */
00517 /* End: */
Generated on Sun May 8 08:40:12 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3