br_stl Namespace Reference

Data Structures
class	checkedVector
class	dynamic_priority_queue
struct	Empty
class	Graph
struct	IterGreater
Enumerations
enum	VertStatus { notVisited, visited, processed }
Functions
template<class EdgeType>
void	connectNeighbors (Graph< Place, EdgeType > &G)
template<class EdgeType>
void	create_vertex_set (Graph< Place, EdgeType > &G, int count, int maxX, int maxY)
template<class EdgeType>
void	createMPfile (char *Filename, Graph< Place, EdgeType > &G, double ScalingFactor)
template<class EdgeType>
void	createTeXfile (const char *Filename, Graph< Place, EdgeType > &G, double ScalingFactor, int xMax, int yMax)
template<class GraphType, class EdgeType>
void	Dijkstra (GraphType &Gr, std::vector< EdgeType > &Dist, std::vector< int > &Pred, int Start)
std::string	i2string (unsigned int i)
template<class VertexType, class EdgeType>
std::ostream &	operator<< (std::ostream &os, Graph< VertexType, EdgeType > &G)
std::ostream &	operator<< (std::ostream &os, const Empty &)
std::istream &	operator>> (std::istream &is, Empty &)
template<class Container>
void	showSequence (const Container &s, const char *sep=" ", std::ostream &where=std::cout)
template<class GraphType>
bool	topoSort (GraphType &G, std::vector< int > &Result)
template<class EdgeType>
void	writeMPpath (char *Filename, Graph< Place, EdgeType > &G, std::vector< int > &V, double ScalingFactor, int Start)

---

Enumeration Type Documentation

enum br_stl::VertStatus

Enumerator:

notVisited
visited
processed

Definition at line 234 of file graph.h.

{notVisited, visited, processed};

---

Function Documentation

template<class EdgeType>

void br_stl::connectNeighbors

(

Graph< Place, EdgeType > &

G

)

[inline]

Definition at line 47 of file gra_util.h.

References br_stl::Graph< VertexType, EdgeType >::connectVertices(), and br_stl::Graph< VertexType, EdgeType >::size().

                                                 {
    for(size_t i = 0; i < G.size(); ++i) {
       Place iPlace = G[i].first;

       for(size_t j = i+1; j < G.size(); ++j) {
          Place jPlace = G[j].first;

          Place MidPoint((iPlace.X()+jPlace.X())/2,
                         (iPlace.Y()+jPlace.Y())/2);

         /* The following loop is not run-time optimized. A possible
            optimization could be to sort the places by their x
            coordinates so that only a small relevant range must be
            searched. The relevant range results from the fact that
            the places to be compared must lie inside a circle around
            the mid-point whose diameter is equal to the distance
            between the places i and j. */

          size_t k = 0;
          unsigned long int e2 = DistSquare(iPlace, MidPoint);

          while(k < G.size()) {      // not run-time optimized
             if(k != j && k != i &&
                DistSquare(G[k].first, MidPoint) < e2)
                    break;
             ++k;
          }

          if(k == G.size())  {// no nearer place found
             EdgeType dist = Distance(iPlace, jPlace);
             G.connectVertices(i, j, dist);
          }
       }
    }
}

template<class EdgeType>

void br_stl::create_vertex_set	(	Graph< Place, EdgeType > &	G,
		int	count,
		int	maxX,
		int	maxY
	)			[inline]

Definition at line 35 of file gra_util.h.

References i2string(), and br_stl::Graph< VertexType, EdgeType >::insert().

                                                 {
    Random xRandom(maxX),
           yRandom(maxY);

    // create vertices with random coordinates
    int i = -1;
    while(++i < count)
      G.insert(Place(xRandom(), yRandom(),i2string(i)));
}

template<class EdgeType>

void br_stl::createMPfile	(	char *	Filename,
		Graph< Place, EdgeType > &	G,
		double	ScalingFactor
	)			[inline]

Definition at line 159 of file gra_util.h.

References br_stl::Graph< VertexType, EdgeType >::begin(), br_stl::Graph< VertexType, EdgeType >::end(), br_stl::Graph< VertexType, EdgeType >::isDirected(), and br_stl::Graph< VertexType, EdgeType >::size().

                                        {
    assert(!G.isDirected());
    std::ofstream Output(Filename);

    if(!Output) {
        std::cerr << Filename
             << " cannot be opened!\n";
        exit(1);
    }

    Output  << "%%%% createMPfile(): This is a generated file!\n"
         << "input boxes\n\n"
         << "beginfig(1);\nu=1mm; % unitlength\n"
         << "defaultscale := 0.8; % small numbers\n";

    for(register size_t iv = 0; iv < G.size(); ++iv) {
       // Point
       Output << " drawdot( "
               << G[iv].first.X()*ScalingFactor
               << "u, "
               << G[iv].first.Y()*ScalingFactor
               << "u)  withpen pencircle scaled 1mm;\n";

       // node name
       Output << " label.urt( \""
              << G[iv].first << "\", ( "
               << G[iv].first.X()*ScalingFactor
               << "u, "
               << G[iv].first.Y()*ScalingFactor
               << "u) ); " << std::endl;

       /* All edges are drawn. In order to prevent them from appearing
          twice in the undirected graph, they are only drawn in the
          direction of the greater index. */


       typename Graph<Place, EdgeType>::Successor::const_iterator I =
         //        std:: map<int, EdgeType>::const_iterator I =
                           G[iv].second.begin();

       while(I != G[iv].second.end()) {
          size_t n = (*I).first;
          if(n > iv) {             // otherwise, ignore
             Output << "  draw ( "
                    << G[iv].first.X()*ScalingFactor << "u, "
                    << G[iv].first.Y()*ScalingFactor 
                    << "u ) -- ( "
                    << G[n].first.X()*ScalingFactor << "u, "
                    << G[n].first.Y()*ScalingFactor
                    << "u );" << std::endl;
          }
          ++I;
       }
    }
    Output << "endfig;" << std::endl << "end." << std::endl;
}

template<class EdgeType>

void br_stl::createTeXfile	(	const char *	Filename,
		Graph< Place, EdgeType > &	G,
		double	ScalingFactor,
		int	xMax,
		int	yMax
	)			[inline]

Definition at line 86 of file gra_util.h.

References br_stl::Graph< VertexType, EdgeType >::begin(), br_stl::Graph< VertexType, EdgeType >::end(), br_stl::Graph< VertexType, EdgeType >::isDirected(), and br_stl::Graph< VertexType, EdgeType >::size().

                                       {
    assert(!G.isDirected());
    std::ofstream Output(Filename);

    if(!Output) {
        std::cerr << Filename
             << " cannot be opened!\n";
        exit(1);
    }

    Output  << "%% This is a generated file!\n"
         << "\\unitlength 1.00mm\n"
         << "\\begin{picture}("
         << xMax << ','
         << yMax << ")\n";

    for(size_t iv = 0; iv < G.size(); ++iv) {
       // Point
       Output << "\\put("
               << G[iv].first.X()*ScalingFactor
               << ','
               << G[iv].first.Y()*ScalingFactor
               << "){\\circle*{1.0}}\n";

       // node name
       Output << "\\put("
               << (1.0 + G[iv].first.X()*ScalingFactor)
               << ','
               << G[iv].first.Y()*ScalingFactor
               << "){\\makebox(0,0)[lb]{{\\tiny "
               << G[iv].first            // name
               << "}}}\n";

       /* All edges are drawn. In order to prevent them from appearing
          twice in the undirected graph, they are only drawn in the
          direction of the greater index. */

       typename Graph<Place,EdgeType>::Successor::const_iterator I =
         //       std::map< int, EdgeType >::const_iterator I =
                           G[iv].second.begin();

       while(I != G[iv].second.end()) {
          size_t n = (*I).first;
          if(n > iv) {             // otherwise, ignore
             double x1,x2,y1,y2,dx,dy;
             x1 =  G[iv].first.X()*ScalingFactor;
             y1 =  G[iv].first.Y()*ScalingFactor;
             x2 =  G[n].first.X()*ScalingFactor;
             y2 =  G[n].first.Y()*ScalingFactor;
             dx = x2-x1; dy = y2-y1;
             double dist = std::sqrt(dx*dx+dy*dy);
             int wdh = int(5*dist);
             dx = dx/wdh; dy = dy/wdh;
             Output << "\\multiput(" << x1 << "," << y1 << ")("
              << dx << "," << dy << "){" << wdh
                   << "}{\\circle*{0.1}}\n";
          }
          ++I;
       }
    }
    Output << "\\end{picture}\n";
}

template<class GraphType, class EdgeType>

void br_stl::Dijkstra	(	GraphType &	Gr,
		std::vector< EdgeType > &	Dist,
		std::vector< int > &	Pred,
		int	Start
	)			[inline]

Definition at line 35 of file Gra_algo.h.

References TeMAXFLOAT.

                  {
    /* The algorithm proceeds in such a way that the distances are
       estimated and the estimates gradually improved. The distance to
       the starting point is known (0). For all other vertices, the
       worst possible estimate is entered.*/

    Dist = std::vector<EdgeType>(Gr.size(),
          TeMAXFLOAT); // as good as infinity
    Dist[Start] = (EdgeType)0;

    /* The predecessor vector too is initialized with `impossible'
       values. Subsequently, a dynamic priority queue is defined and
       initialized with the distance vector: */

        Pred = std::vector<int>(Gr.size(), -1);
    dynamic_priority_queue<EdgeType> Q(Dist);

    // In the next step, all vertices are extracted  one by one from
    //  the priority queue, and precisely in the order of the estimated
    // distance towards the starting vertex. Obviously, the starting
    //vertex is dealt with first. No vertex is looked at twice. 

    int u;
    while(!Q.empty()) {
       u = Q.topIndex();   // extract vertex with minimum
       Q.pop();

       // Now, the distance estimates for all neighboring vertices of
       //  u are updated. If the previous estimate of the distance
        //  between the current neighbor of u and the starting vertex
       //   (Dist[Neighbor]) is worse than the distance between vertex u
        //  and the starting vertex (Dist[u]) plus the distance between
       //   u and the neighboring vertex (dist), the estimate is
        //  improved: this process is called relaxation. In this case,
        //  the path from the starting vertex to the neighbor cannot be
        //  longer than (Dist[u] + dist). In this case, u would have to
        //  be regarded as predecessor of the neighbor. 
          
        // improve estimates for all neighbors of u
        typename GraphType::Successor::const_iterator
                   I = Gr[u].second.begin();

        while(I != Gr[u].second.end()) {
            int Neighbor = (*I).first;
            EdgeType dist = (*I).second;

            // relaxation
            if(Dist[Neighbor] > Dist[u] + dist) {
               // improve estimate
               Q.changeKeyAt(Neighbor, Dist[u] + dist);
               // u is predecessor of the neighbor
               Pred[Neighbor] = u;
            }
            ++I;
        }
    }
        return;
}

std::string br_stl::i2string

(

unsigned int

i

)

Definition at line 19 of file gra_util.h.

Referenced by create_vertex_set().

                                   {
    if(i==0) return std::string("0");
    char buf[] = "0000000000000000";
    char *pos = buf + sizeof(buf)-1;  // point to end
   
    do
      *--pos = i % 10 + '0';
    while(i /=10);
    return std::string(pos);
}

template<class VertexType, class EdgeType>

std::ostream& br_stl::operator<<	(	std::ostream &	os,
		Graph< VertexType, EdgeType > &	G
	)			[inline]

Definition at line 354 of file graph.h.

        {
                // display of vertices with successors
                for(size_t i = 0; i < G.size(); ++i)
                {
                        os << G[i].first << " <";
                        typename Graph<VertexType,EdgeType>::Successor::const_iterator
                                                                startN = G[i].second.begin(),
                                                                endN   = G[i].second.end();

                        while(startN != endN)
                        {
                                os << G[(*startN).first].first << ' ' // vertex
                                << (*startN).second << ' ';        // edge value
                                ++startN;
                        }
                        os << ">" << std::endl;
                }
                return os;
        }

std::ostream& br_stl::operator<<	(	std::ostream &	os,
		const Empty &
	)			[inline]

Definition at line 48 of file graph.h.

{ return os;}

std::istream& br_stl::operator>>	(	std::istream &	is,
		Empty &
	)			[inline]

Definition at line 49 of file graph.h.

{ return is;}

template<class Container>

void br_stl::showSequence	(	const Container &	s,
		const char *	sep = " ",
		std::ostream &	where = std::cout
	)			[inline]

Definition at line 11 of file showseq.h.

                                               {
   typename Container::const_iterator iter = s.begin();
   while(iter != s.end())
      where << *iter++ << sep;
   where << std::endl;
}

template<class GraphType>

bool br_stl::topoSort	(	GraphType &	G,
		std::vector< int > &	Result
	)			[inline]

Definition at line 99 of file Gra_algo.h.

                               {
    assert(G.isDirected());           // let's play this safe!
    int ResCounter = 0;
    Result = std::vector<int>(G.size(), -1);

    /* The vector Result takes the indices of the correspondingly
       distributed vertices. The counter ResCounter is the position in
       Result where the next entry belongs. */

    vector<int> PredecessorCount(G.size(), 0);
    int VerticesWithoutSuccessor = 0;

    /* For each vertex, the vector PredecessorCount counts how many
       predecessors it has. There are vertices without successors,
       whose number is kept in VerticesWithoutSuccessor. Furthermore,
       the algorithm remains stable if the precondition that a graph
       must not have cycles is violated. The variable
       VerticesWithoutSuccessor is used to recognize this situation
       (see below). */

    /* 
        for(size_t iv = 0; iv < G.size(); ++iv) {
        if(G[iv].second.size() > 0) {    // is predecessor
           typename GraphType::Successor::const_iterator I =
                G[iv].second.begin();
           while(I != G[iv].second.end())
               // update number of predecessors
               ++PredecessorCount[(*I++).first];
        }
        else  { // Vertex is no predecessor, that is, without successor
             // an excessively high number of predecessors is used 
             // for later recognition
             PredecessorCount[iv] =   G.size(); // too many!
             ++VerticesWithoutSuccessor;
        }
    }
        */

    /* The dynamic priority queue is initialized with the vector of
       numbers of predecessors. At the beginning of the queue we find
       those vertices that have no predecessors and therefore are to
       be processed next. Only the vertices which are predecessors
       themselves, that is that have successors are processed. The
       subsequent loop is terminated when the queue only contains
       successor vertices which themselves are not predecessors. Their
       number of predecessors can never be 0 because further above
       they were initialized with too high a value.*/
       
    /* 
        dynamic_priority_queue<int> Q(PredecessorCount);

    // process all predecessors
    while(Q.topKey() == 0) {
        // determine vertex with predecessor number 0
       int oV = Q.topIndex();
       Q.pop();

       Result[ResCounter++] = oV;

       // In order to ensure that this vertex without predecessors oV
        //  is no longer considered in the next cycle, the number of
       //   predecessors of all its successors is decreased by 1. 
          
       typename GraphType::Successor::const_iterator
             I = G[oV].second.begin();
       while(I != G[oV].second.end()) {
          // decrease number of predecessors with 
          // changeKeyAt()}. Do not change directly!
          int V = (*I).first;
          Q.changeKeyAt(V, PredecessorCount[V] -1);
          ++I;
       }
    }

    // Now, all vertices without successors are entered. As a
    //   countercheck, the variable VerticesWithoutSuccessor is
    //   decreased. If the queue contains too many vertices, an error
    //   message is displayed.  
       
    while(!Q.empty()) {
         Result[ResCounter++] = Q.topIndex();
         Q.pop();
         --VerticesWithoutSuccessor;
    }

    if(VerticesWithoutSuccessor < 0)
       std::cerr << "Error: graph contains a cycle!\n";
    return VerticesWithoutSuccessor == 0;
        */
        return;
}

template<class EdgeType>

void br_stl::writeMPpath	(	char *	Filename,
		Graph< Place, EdgeType > &	G,
		std::vector< int > &	V,
		double	ScalingFactor,
		int	Start
	)			[inline]

Definition at line 222 of file gra_util.h.

                            {
    std::ofstream Output(Filename);

    if(!Output) {
        std::cerr << Filename
             << " cannot be opened!\n";
        exit(1);
    }

    Output  << "%%%% writeMPpath(): This is a generated file!\n"
            << "beginfig( 1 );\nu=1mm; % unitlength" << std::endl
            << "pickup pencircle scaled 2pt;\n"  // line width
            << "  draw ( "
            << G[ Start ].first.X() * ScalingFactor
         << "u, "
         << G[ Start ].first.Y() * ScalingFactor
         << "u)";

     while ( V[ Start ] >= 0 ) {
         int Successor = V[ Start ];
         Output << std::endl << "    -- ( "
             << G[ Successor ].first.X() * ScalingFactor
             << "u, "
             << G[ Successor ].first.Y() * ScalingFactor
             << " u)";
         Start = Successor;
     }
     Output << ";\n" << "endfig;\n" << "end." << std::endl;
}

---