www.pudn.com > AdaBoost_weaklearner_1.rar > graph.cpp
// File graph.cpp Graph class template implementation file
// shinnerl@ucla.edu
#ifndef GRAPH_CPP
#define GRAPH_CPP
/*
template
void Graph::getComponent(const V& v0, set& myPiece)
{
// Find all vertices connected to v0, put them in myPiece with v0.
cerr << "\nYou must implement function Graph::getComponent()."
<< std::endl;
assert(0);
}
*/
template // Verify "undirectedness" of graph data
bool Graph::isSymmetric( pair& badEdge )
{
// The weight for edge {u,v} must be stored twice, for both (u,v) and (v,u).
// This function stops as soon as it finds one bad edge and
// passes it back, returning false. If *all* edges are ok, it returns true.
// There is no efficient way to avoid visiting every stored edge *twice*.
//
// Recall, edge (u,v) with weight w is stored in u's Adjacency map as
// the pair (v,w).
bool symmetric = true;
std::map >::iterator p;
for (p = map< V, map >::begin();
p !=map< V, map >::end();
++p)
{
const V& v_i = p->first; // shorthand
map& v_i_map = p->second; // shorthand
if (!v_i_map.empty())
{
std::map::iterator q;
for ( q = v_i_map.begin();
symmetric && q != v_i_map.end();
++q )
{
const V& neighbor = q->first;
W edgeWeight = q->second;
W* counterWeightPtr = findEdge(neighbor, v_i);
if (!counterWeightPtr || (*counterWeightPtr != edgeWeight))
{
symmetric = false;
badEdge.first = v_i;
badEdge.second = neighbor;
}
}
}
}
return symmetric;
}
template
void Graph::insertVertex( const V& v )
{
operator[](v) = map(); // Initially, v has no neighbors.
}
template
void Graph::removeVertex( const V& v )
{
// Before removing v, we must remove all edges incident upon it.
// To do this, we visit every neighbor of v and remove v from
// that neighbor's adjacency map. Then we remove v.
map *Aptr = findVertex( v );
if (Aptr) {
std::map::iterator p;
for ( p = Aptr->map::begin();
p != Aptr->map::end();
++p ) {
map *tAptr = findVertex(p->first);
tAptr->erase( v ); // tAptr nonzero if the Graph is symmetric.
}
}
map >::erase(v);
}
template // Symmetry preserving.
void Graph::removeEdge( const V& v1, const V& v2 )
{
map *A1ptr = findVertex(v1),
*A2ptr = findVertex(v2);
if (A1ptr && A2ptr)
{
if (findEdge(v1, v2))
A1ptr->erase( v2 );
if (findEdge(v2, v1))
A2ptr->erase( v1 );
}
}
template // Symmetry preserving.
void Graph::setEdge(const V& v1, const V& v2, const W& w)
{
map *A1ptr = findVertex(v1),
*A2ptr = findVertex(v2);
if (A1ptr && A2ptr)
{
A1ptr->operator[](v2) = w;
A2ptr->operator[](v1) = w;
}
}
template
map* Graph::findVertex(const V& v) const
{
map* nhbdPtr = 0;
std::map< V, map >::const_iterator p1
= map< V, map >::find(v);
if (p1 != map< V, map >::end())
nhbdPtr = const_cast*>(&(p1->second)); // cast
return nhbdPtr;
}
template
W* Graph::findEdge( const V& v1, const V& v2 ) const
{
W* Wptr = 0;
map* AmapPtr = findVertex(v1);
if (AmapPtr)
{
std::map::iterator p2 = AmapPtr->find(v2);
if (p2 != AmapPtr->end())
Wptr = &(p2->second);
}
return Wptr;
}
template // Vertex adjacency map output
void Graph::print( ostream& os )
{
std::map< V, map >::iterator p;
for (p = map< V, map >::begin();
p !=map< V, map >::end();
++p){
os << p->first;
os << " { ";
std::map::iterator q;
for (q = p->second.begin();
q !=p->second.end();
++q)
os << " ( " << q->first
<< " , " << q->second << " ) ";
os << " } " << std::endl;
}
os << std::endl;
}
template // Vertex adjacency map input
void Graph::read( istream& is )
{
erase();
V v;
map A;
while (is){
is >> v;
if (is){
getAdjacencyMap(is, A);
operator[](v) = A;
}
}
pair badPair;
if (!isSymmetric( badPair ))
{
stringstream info;
info << "\nError in graph input at edge ("
<< badPair.first << " , " << badPair.second << "). \n"
<< "The graph must be undirected. Graph discarded. \n\n"
<< "See sample file \"g1.dat\" for format conventions; note spacing."
<< std::endl;
erase();
throw Error(info.str());
}
}
template // Vertex adjacency map input
void Graph::getAdjacencyMap( istream& is, map& A )
{
A.map::clear();
char ch = ' ';
while ( is && ch != '{')
is >> ch;
bool done = false;
V neighbor;
W weight;
while (is && !done)
{
is >> ch;
done = (!is || ch =='}');
if (!done && ch == '(')
{
is >> neighbor;
is >> ch; // Separating comma.
is >> weight;
is >> ch; // Closing paren.
A[neighbor] = weight;
}
}
}
// --- Begin leastCostPath code ---
template
struct PathVertex // wrapper used by leastCostPath().
{
V vertex;
V predecessor;
W pathWeight;
PathVertex() {}
PathVertex( const V& v, const W& pw ) // For searching.
: vertex(v), pathWeight(pw) {}
PathVertex( const V& v, const V& p, const W& pw )
: vertex(v), predecessor(p), pathWeight(pw) {}
bool operator<( const PathVertex& w ) const
{return (pathWeight < w.pathWeight && vertex != w.vertex)
|| (pathWeight == w.pathWeight && vertex < w.vertex);}
bool operator<=( const PathVertex& w ) const
{return (*this < w )
|| (pathWeight <= w.pathWeight && vertex == w.vertex);}
bool operator>( const PathVertex& w ) const
{return !operator<=(w);}
bool operator>=( const PathVertex& w ) const
{return !operator<(w); }
bool operator==( const PathVertex& w ) const
{return (vertex == w.vertex);}
bool operator!=( const PathVertex& w ) const
{return !operator==(w); }
};
template
ostream& operator<<( ostream& os, const PathVertex& pv )
{os << pv.vertex; return os;}
template
istream& operator>>( istream& is, PathVertex& pv )
{is >> pv.vertex >> pv.predecessor >> pv.pathWeight; return is;}
template
T popLeast ( std::set& theSet )
{
assert (!theSet.empty()); // Precondition: theSet must be nonempty.
std::set::iterator p = theSet.begin();
T answer = *p;
theSet.erase(answer);
return answer;
}
template
W Graph::leastCostPath( const V& vStart, const V& vEnd,
deque& pathDeque ) const
{
// Dijkstra's algorithm. The tree of least cost paths is stored in
// an STL map called "pathMap." Each vertex in the pathMap
// is paired with a unique predecessor (vStart is paired with itself).
//
// The boundary or "edge" of this tree of least cost paths is
// stored twice to support two different modes of access: by
// pathWeight and by vertex.
// The "boundarySet" is also an STL set< PathVertex >.
// Its elements are ordered first by pathWeight and second by
// vertex name, as defined by PathVertex::operator<(...). Its
// least-weight element is efficiently removed and added to
// the pathMap at each step of the algorithm.
// The "boundaryMap" is an STL map that supports simple
// pathWeight look-up by vertex key. It facilitates the
// boundary-weight updating that must be applied to all neighbors
// of each newly added element of the pathMap.
//
// Precondition: Vertex vStart must be in the graph.
map pathMap;
std::set< PathVertex > boundarySet;
map boundaryMap;
bool done = false;
W pathCost(0); // Assuming W=0 makes sense.
if (vStart == vEnd)
done = true;
else // Initialize. Put vStart's neighbors in the boundarySet as triples.
{
pathMap[vStart] = vStart;
map* neighbors = findVertex( vStart );
assert(neighbors);
std::map::iterator p;
for ( p = neighbors->begin(); p != neighbors->end(); ++p )
{
const V& terminus = p->first;
W& edgeWeight = p->second;
boundarySet.insert( PathVertex(terminus, vStart, edgeWeight) );
boundaryMap[terminus] = edgeWeight;
}
}
while (!done && !boundarySet.empty())
{
// Main loop. Get boundary vertex of least pathWeight
// and add it to the table, updating any other
// boundary vertices as appropriate.
PathVertex pvNearest = popLeast( boundarySet );
V& vNew = pvNearest.vertex;
W& pwNew = pvNearest.pathWeight;
boundaryMap.erase( vNew );
pathMap[vNew] = pvNearest.predecessor;
if (vNew != vEnd)
{
map* vNewNeighbors = findVertex( vNew );
std::map::iterator p;
for ( p = vNewNeighbors->begin(); p != vNewNeighbors->end(); ++p )
{
const V& terminus = p->first;
if( pathMap.find(terminus) == pathMap.end() ) // if terminus is not
{ // in the pathMap...
W& edgeWeight = p->second;
W oldWeight; // old weight of terminus in boundaryMap
W npwt = edgeWeight + pwNew; // npwt = new weight of terminus
std::map::iterator pbm = boundaryMap.find(terminus);
if ( pbm != boundaryMap.end() )
{
oldWeight = pbm->second;
if (npwt < oldWeight)
{
boundarySet.erase(PathVertex( terminus, oldWeight ));
boundarySet.insert( PathVertex(terminus, vNew, npwt) );
boundaryMap[terminus] = npwt;
}
}
else
{
boundarySet.insert( PathVertex( terminus, vNew, npwt) );
boundaryMap[terminus] = npwt;
}
}
}
}
else
{
pathCost = pwNew;
done = true;
}
}
if (done && vStart != vEnd) // Get the path from the table as a deque.
{
pathDeque.push_front(vEnd);
V curr = vEnd;
do{
std::map::iterator pps = pathMap.find( curr );
assert( pps != pathMap.end() );
curr = pps->second;
pathDeque.push_front(curr);
}while( curr != vStart );
}
else if (!done)
cout << "\nNo path between those vertices exists." << endl;
else
; // vStart == vEnd
return pathCost;
}
// --- End leastCostPath code ---
#endif