| 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/gra_util.h
Go to the documentation of this file.

    00001 #ifndef GRAPH_UTILITIES_H
    00002 #define GRAPH_UTILITIES_H
    00003
    00004 #include<place.h>
    00005 #include<graph.h>
    00006 #include<fstream>
    00007 #include<myrandom.h>
    00008 #include<string>
    00009 #include<iostream>
    00010
    00011 namespace br_stl {
    00012
    00013 /* During automatic creation of an undirected graph, a name must be
    00014    generated for each vertex. The following auxiliary function
    00015    converts the current number into a string object which is entered
    00016    as identifier. */
    00017
    00018 // auxiliary function for generating strings out of numbers
    00019 std::string i2string(unsigned int i) {
    00020     if(i==0) return std::string("0");
    00021     char buf[] = "0000000000000000";
    00022     char *pos = buf + sizeof(buf)-1;  // point to end
    00023
    00024     do
    00025       *--pos = i % 10 + '0';
    00026     while(i /=10);
    00027     return std::string(pos);
    00028 }
    00029
    00030 /* The function create_vertex_set() creates a number of vertices with
    00031    random coordinates between 0 and maxX or maxY in a graph G
    00032    according to its size (G.size()). */
    00033
    00034 template<class EdgeType>
    00035 void create_vertex_set(Graph<Place, EdgeType>& G,
    00036                   int count, int maxX, int maxY) {
    00037     Random xRandom(maxX),
    00038            yRandom(maxY);
    00039
    00040     // create vertices with random coordinates
    00041     int i = -1;
    00042     while(++i < count)
    00043       G.insert(Place(xRandom(), yRandom(),i2string(i)));
    00044 }
    00045
    00046 template<class EdgeType>
    00047 void connectNeighbors(Graph<Place, EdgeType>& G) {
    00048     for(size_t i = 0; i < G.size(); ++i) {
    00049        Place iPlace = G[i].first;
    00050
    00051        for(size_t j = i+1; j < G.size(); ++j) {
    00052           Place jPlace = G[j].first;
    00053
    00054           Place MidPoint((iPlace.X()+jPlace.X())/2,
    00055                          (iPlace.Y()+jPlace.Y())/2);
    00056
    00057          /* The following loop is not run-time optimized. A possible
    00058             optimization could be to sort the places by their x
    00059             coordinates so that only a small relevant range must be
    00060             searched. The relevant range results from the fact that
    00061             the places to be compared must lie inside a circle around
    00062             the mid-point whose diameter is equal to the distance
    00063             between the places i and j. */
    00064
    00065           size_t k = 0;
    00066           unsigned long int e2 = DistSquare(iPlace, MidPoint);
    00067
    00068           while(k < G.size()) {      // not run-time optimized
    00069              if(k != j && k != i &&
    00070                 DistSquare(G[k].first, MidPoint) < e2)
    00071                     break;
    00072              ++k;
    00073           }
    00074
    00075           if(k == G.size())  {// no nearer place found
    00076              EdgeType dist = Distance(iPlace, jPlace);
    00077              G.connectVertices(i, j, dist);
    00078           }
    00079        }
    00080     }
    00081 }
    00082
    00083
    00084 // Only for undirected graphs!
    00085 template<class EdgeType>
    00086 void createTeXfile(const char * Filename,
    00087                    Graph<Place, EdgeType>& G,
    00088                    double ScalingFactor,
    00089                    int xMax, int yMax) {
    00090     assert(!G.isDirected());
    00091     std::ofstream Output(Filename);
    00092
    00093     if(!Output) {
    00094         std::cerr << Filename
    00095              << " cannot be opened!\n";
    00096         exit(1);
    00097     }
    00098
    00099     Output  << "%% This is a generated file!\n"
    00100          << "\\unitlength 1.00mm\n"
    00101          << "\\begin{picture}("
    00102          << xMax << ','
    00103          << yMax << ")\n";
    00104
    00105     for(size_t iv = 0; iv < G.size(); ++iv) {
    00106        // Point
    00107        Output << "\\put("
    00108                << G[iv].first.X()*ScalingFactor
    00109                << ','
    00110                << G[iv].first.Y()*ScalingFactor
    00111                << "){\\circle*{1.0}}\n";
    00112
    00113        // node name
    00114        Output << "\\put("
    00115                << (1.0 + G[iv].first.X()*ScalingFactor)
    00116                << ','
    00117                << G[iv].first.Y()*ScalingFactor
    00118                << "){\\makebox(0,0)[lb]{{\\tiny "
    00119                << G[iv].first            // name
    00120                << "}}}\n";
    00121
    00122        /* All edges are drawn. In order to prevent them from appearing
    00123           twice in the undirected graph, they are only drawn in the
    00124           direction of the greater index. */
    00125
    00126        typename Graph<Place,EdgeType>::Successor::const_iterator I =
    00127          //       std::map< int, EdgeType >::const_iterator I =
    00128                            G[iv].second.begin();
    00129
    00130        while(I != G[iv].second.end()) {
    00131           size_t n = (*I).first;
    00132           if(n > iv) {             // otherwise, ignore
    00133              double x1,x2,y1,y2,dx,dy;
    00134              x1 =  G[iv].first.X()*ScalingFactor;
    00135              y1 =  G[iv].first.Y()*ScalingFactor;
    00136              x2 =  G[n].first.X()*ScalingFactor;
    00137              y2 =  G[n].first.Y()*ScalingFactor;
    00138              dx = x2-x1; dy = y2-y1;
    00139              double dist = std::sqrt(dx*dx+dy*dy);
    00140              int wdh = int(5*dist);
    00141              dx = dx/wdh; dy = dy/wdh;
    00142              Output << "\\multiput(" << x1 << "," << y1 << ")("
    00143               << dx << "," << dy << "){" << wdh
    00144                    << "}{\\circle*{0.1}}\n";
    00145           }
    00146           ++I;
    00147        }
    00148     }
    00149     Output << "\\end{picture}\n";
    00150 }
    00151
    00152 /* This is similar to createTeXfile, but creates
    00153    metapost-output which can with metapost directly
    00154    be converted to postscript. The adaption of this routine
    00155    was made by Andreas Scherer.
    00156    Only for undirected graphs! */
    00157
    00158 template<class EdgeType>
    00159 void createMPfile(char * Filename,
    00160                   Graph<Place, EdgeType>& G,
    00161                   double ScalingFactor) {
    00162     assert(!G.isDirected());
    00163     std::ofstream Output(Filename);
    00164
    00165     if(!Output) {
    00166         std::cerr << Filename
    00167              << " cannot be opened!\n";
    00168         exit(1);
    00169     }
    00170
    00171     Output  << "%%%% createMPfile(): This is a generated file!\n"
    00172          << "input boxes\n\n"
    00173          << "beginfig(1);\nu=1mm; % unitlength\n"
    00174          << "defaultscale := 0.8; % small numbers\n";
    00175
    00176     for(register size_t iv = 0; iv < G.size(); ++iv) {
    00177        // Point
    00178        Output << " drawdot( "
    00179                << G[iv].first.X()*ScalingFactor
    00180                << "u, "
    00181                << G[iv].first.Y()*ScalingFactor
    00182                << "u)  withpen pencircle scaled 1mm;\n";
    00183
    00184        // node name
    00185        Output << " label.urt( \""
    00186               << G[iv].first << "\", ( "
    00187                << G[iv].first.X()*ScalingFactor
    00188                << "u, "
    00189                << G[iv].first.Y()*ScalingFactor
    00190                << "u) ); " << std::endl;
    00191
    00192        /* All edges are drawn. In order to prevent them from appearing
    00193           twice in the undirected graph, they are only drawn in the
    00194           direction of the greater index. */
    00195
    00196
    00197        typename Graph<Place, EdgeType>::Successor::const_iterator I =
    00198          //        std:: map<int, EdgeType>::const_iterator I =
    00199                            G[iv].second.begin();
    00200
    00201        while(I != G[iv].second.end()) {
    00202           size_t n = (*I).first;
    00203           if(n > iv) {             // otherwise, ignore
    00204              Output << "  draw ( "
    00205                     << G[iv].first.X()*ScalingFactor << "u, "
    00206                     << G[iv].first.Y()*ScalingFactor
    00207                     << "u ) -- ( "
    00208                     << G[n].first.X()*ScalingFactor << "u, "
    00209                     << G[n].first.Y()*ScalingFactor
    00210                     << "u );" << std::endl;
    00211           }
    00212           ++I;
    00213        }
    00214     }
    00215     Output << "endfig;" << std::endl << "end." << std::endl;
    00216 }
    00217
    00218 /* This function (written by A. Scherer) writes a path
    00219    within a graph as a separate metapost-file */
    00220
    00221 template<class EdgeType>
    00222 void writeMPpath(char * Filename,
    00223                  Graph<Place, EdgeType>& G,
    00224                  std::vector< int >& V,
    00225                  double ScalingFactor,
    00226                  int Start) {
    00227     std::ofstream Output(Filename);
    00228
    00229     if(!Output) {
    00230         std::cerr << Filename
    00231              << " cannot be opened!\n";
    00232         exit(1);
    00233     }
    00234
    00235     Output  << "%%%% writeMPpath(): This is a generated file!\n"
    00236             << "beginfig( 1 );\nu=1mm; % unitlength" << std::endl
    00237             << "pickup pencircle scaled 2pt;\n"  // line width
    00238             << "  draw ( "
    00239             << G[ Start ].first.X() * ScalingFactor
    00240          << "u, "
    00241          << G[ Start ].first.Y() * ScalingFactor
    00242          << "u)";
    00243
    00244      while ( V[ Start ] >= 0 ) {
    00245          int Successor = V[ Start ];
    00246          Output << std::endl << "    -- ( "
    00247              << G[ Successor ].first.X() * ScalingFactor
    00248              << "u, "
    00249              << G[ Successor ].first.Y() * ScalingFactor
    00250              << " u)";
    00251          Start = Successor;
    00252      }
    00253      Output << ";\n" << "endfig;\n" << "end." << std::endl;
    00254 }
    00255
    00256 } // namespace br_stl
    00257
    00258 #endif  // graphUtilities
    00259

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines