| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/graph.h
Go to the documentation of this file.

    00001 /************************************************************************************
    00002 TerraLib - a library for developing GIS applications.
    00003 Copyright � 2001-2007 INPE and Tecgraf/PUC-Rio.
    00004
    00005 This code is part of the TerraLib library.
    00006 This library is free software; you can redistribute it and/or
    00007 modify it under the terms of the GNU Lesser General Public
    00008 License as published by the Free Software Foundation; either
    00009 version 2.1 of the License, or (at your option) any later version.
    00010
    00011 You should have received a copy of the GNU Lesser General Public
    00012 License along with this library.
    00013
    00014 The authors reassure the license terms regarding the warranties.
    00015 They specifically disclaim any warranties, including, but not limited to,
    00016 the implied warranties of merchantability and fitness for a particular purpose.
    00017 The library provided hereunder is on an "as is" basis, and the authors have no
    00018 obligation to provide maintenance, support, updates, enhancements, or modifications.
    00019 In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
    00020 indirect, special, incidental, or consequential damages arising out of the use
    00021 of this library and its documentation.
    00022 *************************************************************************************/
    00028 #ifndef GRAPH_H
    00029 #define GRAPH_H
    00030 #include<cassert>
    00031 #include<vector>
    00032 #include<map>
    00033 #include<stack>
    00034 #include<iostream>
    00035 #include "TeDefines.h"
    00036
    00037 namespace br_stl
    00038 {
    00039            // empty parameter class with a minimal set of operations
    00040            // if there are no weights for edges necessary
    00041            struct TL_DLL Empty
    00042            {
    00043            public:
    00044                       Empty(int=0) {}
    00045                       bool operator<(const Empty&) const { return true;}
    00046            };
    00047
    00048            inline std::ostream& operator<<(std::ostream& os, const Empty&) { return os;}
    00049            inline std::istream& operator>>(std::istream& is, Empty& ) { return is;}
    00050
    00051            template<class VertexType, class EdgeType>
    00052            class Graph
    00053            {
    00054            public:
    00055                       // public type interface
    00056                       typedef std::map<int, EdgeType > Successor;
    00057                       typedef std::pair<VertexType, Successor> vertex;
    00058                       typedef std::vector<vertex> GraphType;
    00059                       typedef typename GraphType::iterator iterator;
    00060                       typedef typename GraphType::const_iterator const_iterator;
    00061
    00062                       /* The following constructor initializes the output channel with
    00063                       cerr. A parameter must be specified as to whether the graph is
    00064                       directed or undirected, because this is an essential property
    00065                       of a graph. */
    00066
    00067                       Graph(bool g, std::ostream& os = cerr)
    00068                       : directed(g), pOut(&os)
    00069                       { }
    00070
    00071                       bool isDirected() const { return directed;}
    00072
    00073                       /* A graph is a special kind of container to which something can
    00074                       be added and whose elements can be accessed. Therefore, typical
    00075                       container methods follow, which in their extent are limited to
    00076                       those needed in the book's examples. Thus, there is no method
    00077                       for explicit removal of a vertex or an edge from the graph. */
    00078
    00079                       size_t size() const  { return C.size();}
    00080
    00081                       iterator begin()     { return C.begin();}
    00082                       iterator end()       { return C.end();}
    00083
    00084                       // access to vertex i}
    00085                       vertex& operator[](int i)
    00086                       {
    00087                                  // the access is safe, because C is a checkedVector
    00088                                  return C[i];
    00089                       }
    00090
    00091                       // return the position of the vertex, if it does not exist return -1
    00092                       int getPosition(const VertexType& e);
    00093
    00094                       // addition of a vertex
    00095                       int  insert(const VertexType& e);
    00096
    00097                       // addition of an edge between e1 and e2
    00098                       void insert(const VertexType& e1, const VertexType& e2,
    00099                                                        const EdgeType& Value);
    00100
    00101                       // addition of an edge between vertices no. i and j
    00102                       void connectVertices(int i, int j, const EdgeType& Value);
    00103
    00104                       // set the edge value between vertices no. i and j
    00105                       bool setEdgeValue(const VertexType& e1, const VertexType& e2, const EdgeType& Value);
    00106
    00107                       /* The following methods are useful tools for displaying
    00108                       information on a graph and check its structure.*/
    00109
    00110                       // checking of a read data model
    00111                       // output on the channel passed to check()
    00112                       void check(std::ostream& = std::cout);
    00113
    00114                       // determine the number of edges
    00115                       size_t CountEdges();
    00116
    00117                       /* determine whether the graph contains cycles and in which way it
    00118                       is connected. The method combines two tasks, because they can
    00119                       be carried out in a single run.*/
    00120                       void CycleAndConnect(std::ostream& = cout);
    00121                       int sucessors(int index);
    00122
    00123            private:
    00124                       bool directed;
    00125                       GraphType C;          // container
    00126                       std::ostream* pOut;
    00127            };      // class Graph
    00128
    00129
    00130            template<class VertexType, class EdgeType>
    00131            int Graph<VertexType,EdgeType>::getPosition(const VertexType& e)
    00132            {
    00133                       for(size_t i = 0; i < size(); ++i)
    00134                       if(e == C[i].first)
    00135                                  return i;
    00136
    00137                       return -1;
    00138            }
    00139
    00140            /* In order to avoid ambiguities, a vertex is only entered if it does
    00141            not yet exist. The sequential search is not particularly fast; on the
    00142            other hand, this process is only needed once during the construction
    00143            of the graph. The position of the vertex is returned. */
    00144
    00145            template<class VertexType, class EdgeType>
    00146            int Graph<VertexType,EdgeType>::insert(const VertexType& e)
    00147            {
    00148                       int pos = getPosition(e);
    00149                       if(pos<0)
    00150                       {
    00151                                  // if not found, insert:
    00152                                  C.push_back(vertex(e, Successor()));
    00153                                  return size()-1;
    00154                       }
    00155
    00156                       return pos;
    00157            }
    00158
    00159            /* An edge is inserted by first inserting the vertices, if needed, and
    00160            by determining their positions. The edge construction itself is
    00161            carried out by the function connectVertices(). It is passed the
    00162            vertex numbers and, because of the absence of a search procedure,
    00163            it is very fast. */
    00164
    00165            template<class VertexType, class EdgeType>
    00166            void Graph<VertexType,EdgeType>::insert(const VertexType& e1,
    00167                                                                                                               const VertexType& e2,
    00168                                                                                                               const EdgeType& Value)
    00169            {
    00170                       int pos1 = insert(e1);
    00171                       int pos2 = insert(e2);
    00172                       connectVertices(pos1, pos2, Value);
    00173            }
    00174
    00175            template<class VertexType, class EdgeType>
    00176            void Graph<VertexType,EdgeType>::connectVertices(
    00177                                             int pos1, int pos2, const EdgeType& Value)
    00178            {
    00179                       (C[pos1].second)[pos2] = Value;
    00180
    00181                       if(!directed)  // automatically insert opposite direction too
    00182                       (C[pos2].second)[pos1] = Value;
    00183            }
    00184
    00185            template<class VertexType, class EdgeType>
    00186            bool Graph<VertexType,EdgeType>::setEdgeValue(const VertexType& e1,
    00187                                                                                                               const VertexType& e2,
    00188                                                                                                               const EdgeType& Value)
    00189            {
    00190                       int pos1 = getPosition(e1);
    00191                       int pos2 = getPosition(e2);
    00192
    00193                       if((pos1<0) || (pos2<0))
    00194                                  return false;
    00195
    00196                       (C[pos1].second)[pos2] = Value;
    00197
    00198                       if(!directed)  // automatically insert opposite direction too
    00199                       (C[pos1].second)[pos2] = Value;
    00200
    00201                       return true;
    00202            }
    00203
    00204
    00205            template<class VertexType, class EdgeType>
    00206            void Graph<VertexType,EdgeType>::check(std::ostream& os)
    00207            {
    00208                       os << "The graph is ";
    00209                       if(!isDirected())
    00210                                  os << "un";
    00211
    00212                       os << "directed and has "
    00213                       << size() << " vertices and "
    00214                       << CountEdges()
    00215                       << " edges\n";
    00216                       CycleAndConnect(os);
    00217            }
    00218
    00219            template<class VertexType, class EdgeType>
    00220            size_t Graph<VertexType,EdgeType>::CountEdges()
    00221            {
    00222                       size_t edges = 0;
    00223                       iterator temp = begin();
    00224
    00225                       while(temp != end())
    00226                                  edges += (*temp++).second.size();
    00227
    00228                       if(!directed)
    00229                                  edges /= 2;
    00230                       return edges;
    00231            }
    00232
    00233            // Type for next function
    00234            enum VertStatus {notVisited, visited, processed};
    00235
    00236            template<class VertexType, class EdgeType>
    00237            int Graph<VertexType, EdgeType>::sucessors(int index) {
    00238                       typename Successor::const_iterator
    00239                       start  = operator[](index).second.begin(),
    00240                       end    = operator[](index).second.end();
    00241                       int nSucc = 0;
    00242                       while(start != end)
    00243                       {
    00244                                  nSucc++;
    00245                                  ++start;
    00246                       }
    00247
    00248                       return nSucc;
    00249            }
    00250            template<class VertexType, class EdgeType>
    00251            void Graph<VertexType, EdgeType>::CycleAndConnect(std::ostream& os) {
    00252                       int Cycles = 0;
    00253                       int ComponentNumber = 0;
    00254                       std::stack<int, std::vector<int> > verticesStack;  // vertices to be visited
    00255
    00256                       /* In order to prevent multiple visits to vertices in possible
    00257                       cycles, which entails the risk of infinite loops, the vertices
    00258                       are marked for having been visited or finished being processed.
    00259                       This purpose is served by the vector VertexState. */
    00260
    00261                       // assign all vertices the state `not visited'
    00262                       std::vector<VertStatus> VertexState(size(), notVisited);
    00263
    00264                       /* If, starting from one vertex, an attempt is made to reach all
    00265                       other vertices, success is not guaranteed in weakly or
    00266                       non-connected graphs. Therefore, each vertex is visited. If it
    00267                       is found that a vertex has already been visited, it does not
    00268                       need to be processed any further. */
    00269
    00270                       // visit all vertices
    00271                       for(size_t i = 0; i < size(); ++i)
    00272                       {
    00273                                  if(VertexState[i] == notVisited)
    00274                                  {
    00275                                             ++ComponentNumber;
    00276                                             // store on stack for further processing
    00277                                             verticesStack.push(i);
    00278
    00279                                             // process stack
    00280                                             while(!verticesStack.empty())
    00281                                             {
    00282                                                        int theVertex = verticesStack.top();
    00283                                                        verticesStack.pop();
    00284                                                        if(VertexState[theVertex] == visited)
    00285                                                        VertexState[theVertex] = processed;
    00286                                                        else
    00287                                                        if(VertexState[theVertex] == notVisited)
    00288                                                        {
    00289                                                                   VertexState[theVertex] = visited;
    00290                                                                   // new vertex, earmark for processed mark
    00291                                                                   verticesStack.push(theVertex);
    00292
    00293                                                                   /* If one of the successors of a newly found vertex
    00294                                                                              bears the visited mark, the algorithm has already
    00295                                                                              passed this point once, and there is a cycle. */
    00296
    00297                                                                   // earmark successor:
    00298                                                                   typename Successor::const_iterator
    00299                                                                              start  = operator[](theVertex).second.begin(),
    00300                                                                              end    = operator[](theVertex).second.end();
    00301
    00302                                                                   while(start != end)
    00303                                                                   {
    00304                                                                              int Succ = (*start).first;
    00305
    00306                                                                              if(VertexState[Succ] == visited)
    00307                                                                              {
    00308                                                                                         ++Cycles;   // someone's been here already!
    00309                                                                                         (*pOut) << "at least vertex "
    00310                                                                                         << operator[](Succ).first
    00311                                                                                         << " lies in a cycle\n";
    00312                                                                              }
    00313
    00314                                                                              /* Otherwise, the vertex has already been
    00315                                                                                         processed and therefore should not be
    00316                                                                                         considered again, or it has not yet been
    00317                                                                                         visited and is earmarked on the stack. */
    00318
    00319                                                                              if(VertexState[Succ] == notVisited)
    00320                                                                                         verticesStack.push(Succ);
    00321                                                                              ++start;
    00322                                                                   }
    00323                                                        }
    00324                                             }  // stack empty?
    00325                                  }     //  if(VertexState}...
    00326                       }       // for()} ...
    00327
    00328                       /* Now we only need the output. In case of directed, weakly
    00329                       connected graphs, the algorithm counts several components. In
    00330                       order to make the output conform to the above definitions,
    00331                       although with less content of information, a distinction is
    00332                       made as to whether the graph is directed or not. */
    00333
    00334                       if(directed)
    00335                       {
    00336                                  if(ComponentNumber == 1)
    00337                                             os << "The graph is strongly connected.\n";
    00338                                  else
    00339                                             os << "The graph is not or weakly "
    00340                                                        "connected.\n";
    00341                       }
    00342                       else
    00343                                  os         << "The graph has "
    00344                                             << ComponentNumber
    00345                                             << " component(s)." << std::endl;
    00346
    00347                       os << "The graph has ";
    00348                       if(Cycles == 0)
    00349                                  os << "no ";
    00350                       os << "cycles." << std::endl;
    00351            }
    00352
    00353            template<class VertexType, class EdgeType>
    00354            std::ostream& operator<<(std::ostream& os, Graph<VertexType,EdgeType>& G)
    00355            {
    00356                       // display of vertices with successors
    00357                       for(size_t i = 0; i < G.size(); ++i)
    00358                       {
    00359                                  os << G[i].first << " <";
    00360                                  typename Graph<VertexType,EdgeType>::Successor::const_iterator
    00361                                                                                         startN = G[i].second.begin(),
    00362                                                                                         endN   = G[i].second.end();
    00363
    00364                                  while(startN != endN)
    00365                                  {
    00366                                             os << G[(*startN).first].first << ' ' // vertex
    00367                                             << (*startN).second << ' ';        // edge value
    00368                                             ++startN;
    00369                                  }
    00370                                  os << ">" << std::endl;
    00371                       }
    00372                       return os;
    00373            }
    00374 } // namespace br_stl
    00375
    00376
    00377
    00378 #endif
    00379

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines