ImageGraph.cpp

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00002 
00027 #include "ImageGraph.h"
00028 #include <queue>
00029 
00030 namespace HuginGraph
00031 {
00032 /* build adjacency list for all images in pano */
00033 ImageGraph::ImageGraph(const HuginBase::PanoramaData& pano, bool ignoreLinkedPosition)
00034 {
00035     if (pano.getNrOfImages() > 0)
00036     {
00037         m_graph.resize(pano.getNrOfImages());
00038         if (!ignoreLinkedPosition)
00039         {
00040             // handle all linked positions
00041             for (size_t i = 0; i < pano.getNrOfImages(); ++i)
00042             {
00043                 const HuginBase::SrcPanoImage& image = pano.getImage(i);
00044                 if (image.YawisLinked())
00045                 {
00046                     for (size_t j = i + 1; j < pano.getNrOfImages(); ++j)
00047                     {
00048                         if (image.YawisLinkedWith(pano.getImage(j)))
00049                         {
00050                             m_graph[i].insert(j);
00051                             m_graph[j].insert(i);
00052                         };
00053                     };
00054                 };
00055             };
00056         };
00057         // and now all control points
00058         const HuginBase::CPVector& cps = pano.getCtrlPoints();
00059         for (size_t i = 0; i < cps.size(); ++i)
00060         {
00061             if (cps[i].mode == HuginBase::ControlPoint::X_Y && cps[i].image1Nr != cps[i].image2Nr)
00062             {
00063                 m_graph[cps[i].image1Nr].insert(cps[i].image2Nr);
00064                 m_graph[cps[i].image2Nr].insert(cps[i].image1Nr);
00065             }
00066         }
00067     };
00068 };
00069 
00070 template<typename VALUETYPE>
00071 void DepthFirstSearch(const ImageGraph::GraphList& graph, std::vector<VALUETYPE>& marks, const size_t vertex, const VALUETYPE setType, const VALUETYPE unvisitedType)
00072 {
00073     marks[vertex] = setType;
00074     for (HuginBase::UIntSet::const_iterator it = graph[vertex].begin(); it != graph[vertex].end(); ++it)
00075     {
00076         if (marks[*it] == unvisitedType)
00077         {
00078             DepthFirstSearch(graph, marks, *it, setType, unvisitedType);
00079         };
00080     };
00081 };
00082 
00083 ImageGraph::Components ImageGraph::GetComponents()
00084 {
00085     ImageGraph::Components comp;
00086     if (m_graph.empty())
00087     {
00088         return comp;
00089     };
00090     // and now the depth first search algorithm
00091     std::vector<size_t> marks(m_graph.size(), 0);
00092     size_t counter = 0;
00093     for (size_t i = 0; i < m_graph.size(); ++i)
00094     {
00095         if (marks[i] == 0)
00096         {
00097             counter++;
00098             DepthFirstSearch<size_t>(m_graph, marks, i, counter, 0);
00099         };
00100     };
00101     // now create the connected components as vector<UIntSet>
00102     comp.resize(counter);
00103     for (size_t imgNr = 0; imgNr < marks.size(); ++imgNr)
00104     {
00105         comp[marks[imgNr] - 1].insert(imgNr);
00106     }
00107     return comp;
00108 };
00109 
00110 bool ImageGraph::IsConnected()
00111 {
00112     if (m_graph.empty())
00113     {
00114         return false;
00115     };
00116     // and now the depth first search algorithm
00117     std::vector<bool> visited(m_graph.size(), false);
00118     DepthFirstSearch(m_graph, visited, 0, true, false);
00119     for (std::vector<bool>::const_iterator it = visited.begin(); it != visited.end(); ++it)
00120     {
00121         if (!(*it))
00122         {
00123             return false;
00124         }
00125     }
00126     return true;
00127 };
00128 
00129 void BreadthFirstSearchVisit(const ImageGraph::GraphList& graph,
00130     std::queue<size_t>& queue, std::vector<bool>& visited, BreadthFirstSearchVisitor* visitor)
00131 {
00132     while (!queue.empty())
00133     {
00134         const size_t vertex = queue.front();
00135         queue.pop();
00136         if (!visited[vertex])
00137         {
00138             visited[vertex] = true;
00139             HuginBase::UIntSet visitedNeighbors;
00140             HuginBase::UIntSet unvisitedNeighbors;
00141             for (HuginBase::UIntSet::const_iterator it = graph[vertex].begin(); it != graph[vertex].end(); ++it)
00142             {
00143                 if (visited[*it])
00144                 {
00145                     visitedNeighbors.insert(*it);
00146                 }
00147                 else
00148                 {
00149                     unvisitedNeighbors.insert(*it);
00150                     queue.push(*it);
00151                 };
00152             };
00153             visitor->Visit(vertex, visitedNeighbors, unvisitedNeighbors);
00154         };
00155     };
00156 }
00157 
00158 void ImageGraph::VisitAllImages(const size_t startImg, bool forceAllComponents, BreadthFirstSearchVisitor* visitor)
00159 {
00160     if (m_graph.empty())
00161     {
00162         return;
00163     }
00164     // range checking, just in case
00165     const size_t realStartImg = (startImg >= m_graph.size()) ? 0 : startImg;
00166     std::vector<bool> visited(m_graph.size(), false);
00167     std::queue<size_t> queue;
00168     // go down the graph starting from the startImg
00169     queue.push(realStartImg);
00170     BreadthFirstSearchVisit(m_graph, queue, visited, visitor);
00171     if (forceAllComponents)
00172     {
00173         // if the graph contains several components
00174         // we have not yet visited all images, so
00175         // restart the breadth first algorithm from the new component start
00176         for (size_t i = 0; i < m_graph.size(); ++i)
00177         {
00178             if (!visited[i])
00179             {
00180                 queue.push(i);
00181                 BreadthFirstSearchVisit(m_graph, queue, visited, visitor);
00182             };
00183         };
00184     };
00185 };
00186 
00187 }  // namespace HuginGraph

Generated on 10 Feb 2016 for Hugintrunk by  doxygen 1.4.7