d_galgs.h

数据结构c++语言描述stl版 威廉兄弟的好书,值得看,这是配书代码

#ifdef __BORLANDC__
// suppress the warning message that functions containing for are not
// expanded inline
#pragma warn -8027
#endif	// __BORLANDC__


// input a graph
friend istream& operator>> (istream& istr, graph<T>& g)
{
	// nVertices is number of vertices to read
	int i, nVertices, nEdges;
	// use for input of vertices (v1) and edges ( {v1, v2} )
	T v1, v2;
	// edge weight
	int weight;

	if (g.numVertices > 0)
		// remove an existing graph
		g.clear();

	// input the number of vertices
	istr >> nVertices;

	// input the vertices and insert each into the graph
	for (i = 0; i < nVertices; i++)
	{
		istr >> v1;
		g.insertVertex(v1);
	}

	// input the number of edges
	istr >> nEdges;

	// input the vertices and weight for each edge, and
	// insert it into the graph
	for (i = 0; i < nEdges; i++)
	{
		istr >> v1;
		istr >> v2;
		istr >> weight;
		g.insertEdge(v1,v2,weight);
	}

	// return the stream
	return istr;
}

// output a graph
friend ostream& operator<< (ostream& ostr, const graph<T>& g)
{
	vertexInfo<T> vtxInfo;
	set<neighbor>::iterator setIter;

	int i;

	for (i = 0; i < g.vInfo.size(); i++)
	{
		vtxInfo = g.vInfo[i];
		if (vtxInfo.occupied)
		{
			ostr << (*(vtxInfo.vtxMapLoc)).first << ": in-degree " << vtxInfo.inDegree
				  << "  out-degree " << (vtxInfo.edges).size() << endl;
			ostr << "    Edges: ";
			set<neighbor>& edgeSet = vtxInfo.edges;
			for (setIter = edgeSet.begin(); setIter != edgeSet.end(); setIter++)
			{
				ostr << (*(g.vInfo[(*setIter).dest].vtxMapLoc)).first << " ("
					  << (*setIter).weight << ")  ";
			}
			ostr << endl;
		}
	}
	return ostr;
}

// perform the breadth-first traversal from sVertex and
// return the set of visited vertices
friend set<T> bfs(graph<T>& g, const T& sVertex)
{
	// BFS uses a queue to store indices of adjacent vertices from vInfo
   queue<int> visitQueue;

	// set of vertices in BFS
	set<T> visitSet;

	// use to store indices in vInfo
	int currVertex, neighborVertex;

	// use to search edge sets for unvisited vertices
	set<neighbor>::iterator adj;
	int i;

	// find the index of the starting vertex
	currVertex = g.getvInfoIndex(sVertex);

	// check for a nonexistent starting vertex
	if (currVertex == -1)
		throw graphError("graph bfs(): vertex not in the graph");

	// initialize all vertices in the graph to unvisited (WHITE)
	for (i=0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
			g.vInfo[i].color = vertexInfo<T>::WHITE;

   visitQueue.push(currVertex);   // initialize the queue

   while (!visitQueue.empty())
   {
      // remove a vertex from the queue
      currVertex = visitQueue.front();
		visitQueue.pop();
		// indicate that the vertex has been visited
		g.vInfo[currVertex].color = vertexInfo<T>::BLACK;

		// put the vertex in visitSet
		visitSet.insert((*(g.vInfo[currVertex].vtxMapLoc)).first);

		// create an alias for the edge set of currVertex
		set<neighbor>& edgeSet = g.vInfo[currVertex].edges;
		// sequence through the edge set and look for vertices
		// that have not been visited
		for (adj = edgeSet.begin(); adj != edgeSet.end(); adj++)
		{
			neighborVertex = (*adj).dest;

			if (g.vInfo[neighborVertex].color == vertexInfo<T>::WHITE)
			{
				g.vInfo[neighborVertex].color = vertexInfo<T>::GRAY;
				visitQueue.push(neighborVertex);
			}
		}
   }

	return visitSet;
}

// use the breadth-first traversal algorithm to determine the
// minimum number of edges in any path from sVertex to eVertex
// or -1 if no path exists. if a path exists, the list path
// is the sequence of vertices
friend int shortestPath(graph<T>& g, const T& sVertex,
			               const T& eVertex, list<T>& path)
{
   // queue stores vertices as vInfo indices
   queue<int>  visitQueue;

   // eIter scans the vertices in an adjacency set
   set<neighbor>::iterator eIter;

	// flag set true when scan identifies eVertex as a neighbor
	bool foundShortestPath = false;

	// index in vInfo for the source and destination vertices
	// and the index for current vertex and a neighbor
	int pos_sVertex, pos_eVertex, currPos, neighborPos;

	int returnValue;

	// initialize all vertices to undiscoved (WHITE)
	for (int i = 0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
			g.vInfo[i].color = vertexInfo<T>::WHITE;

	// obtain the starting and ending indices
	pos_sVertex = g.getvInfoIndex(sVertex);
	pos_eVertex = g.getvInfoIndex(eVertex);

	if (pos_sVertex == -1 || pos_eVertex == -1)
		throw graphError("graph shortestPath(): vertex not in "
					        "the graph");

 	g.vInfo[pos_sVertex].parent = pos_sVertex;
	g.vInfo[pos_sVertex].dataValue = 0;

	// insert starting vertex into the queue
	visitQueue.push(pos_sVertex);

	while (!visitQueue.empty() && !foundShortestPath)
	{
		// delete a queue entry, and color it BLACK
		currPos = visitQueue.front();
		visitQueue.pop();
		g.vInfo[currPos].color = vertexInfo<T>::BLACK;

		// if we are at eVertex, we have found the shortest
		// path from sVertex to eVertex
		if (currPos == pos_eVertex)
			foundShortestPath = true;
		else
		{
			// create an alias for the adjacency set of currPos
			set<neighbor>& edgeSet = g.vInfo[currPos].edges;

			// for all undiscovered neighbors, update the dataValue,
			// color, and parent fields in the vertexInfo object.
			for (eIter = edgeSet.begin(); eIter != edgeSet.end(); eIter++)
			{
				neighborPos = (*eIter).dest;

				if (g.vInfo[neighborPos].color == vertexInfo<T>::WHITE)
				{
 					g.vInfo[neighborPos].dataValue =
										g.vInfo[currPos].dataValue + 1;
					g.vInfo[neighborPos].parent = currPos;
					g.vInfo[neighborPos].color = vertexInfo<T>::GRAY;
					// add neighbor vertex to the queue
					visitQueue.push(neighborPos);
				}
			}
		}
	}

	// clear path and find the sequence of vertices
	// from sVertex to eVertex
   path.erase(path.begin(), path.end());
   if (foundShortestPath)
	{
		currPos = pos_eVertex;
		while (currPos != pos_sVertex)
		{
			path.push_front((*(g.vInfo[currPos].vtxMapLoc)).first);
			currPos = g.vInfo[currPos].parent;
		}
		path.push_front(sVertex);
		returnValue = g.vInfo[pos_eVertex].dataValue;
   }
   else
      returnValue = -1;

	return returnValue;
}

// find the path with minimum total weight from sVertex to eVertex
// and return the minimum weight
friend int minimumPath(graph<T>& g, const T& sVertex, const T& eVertex,
							  list<T>& path)
{
   // heap (priority queue) that stores minInfo objects
   miniPQ<minInfo,less<minInfo> >  minPathPQ;

   // used when inserting minInfo entries
   // into the priority queue or erasing entries
   minInfo vertexData;
   // adj is edge set of vertex we are visiting. adjiter is used
   // to traverse adj
   set<neighbor> adj;
   set<neighbor>::iterator adjIter;

	bool foundMinPath = false;

	// index in vInfo for the starting and ending vertices
	// position in vInfo of vertex on a path from sVertex
	int pos_sVertex, pos_eVertex, currPos, destPos;

	// computed minimum weight
   int newMinWeight;

	// return value
	int returnValue;

	list<T>::iterator pathIter;

	// initialize all vertices to unmarked (WHITE) and dataValue
	// variables to INFINITY
	for (int i = 0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
		{
			g.vInfo[i].color = vertexInfo<T>::WHITE;
			g.vInfo[i].dataValue = INFINITY;
		}

	// obtain the starting and ending indices
	pos_sVertex = g.getvInfoIndex(sVertex);
	pos_eVertex = g.getvInfoIndex(eVertex);

	if (pos_sVertex == -1 || pos_eVertex == -1)
		throw graphError("graph minimumPath(): vertex not in the graph");


   // formulate initial priority queue entry
   vertexData.endV = pos_sVertex;

   // path weight from sVertex to sVertex is 0
   vertexData.pathWeight = 0;

	// update dataValue in vInfo and set sVertex as parent
	g.vInfo[pos_sVertex].dataValue = 0;
	g.vInfo[pos_sVertex].parent = pos_sVertex;

	// insert starting vertex into the priority queue
   minPathPQ.push(vertexData);

   // process vertices until we find a minimum path to
   // eVertex or the priority queue is empty
   while (!minPathPQ.empty())
   {
      // delete a priority queue entry and record its
      // vertex and path weight from sVertex.
      vertexData = minPathPQ.top();
		minPathPQ.pop();
		currPos = vertexData.endV;

      // if we are at eVertex, we have found the minimum
      // path from sVertex to eVertex
      if (currPos == pos_eVertex)
		{
			foundMinPath = true;
         break;
		}

		if (g.vInfo[currPos].color != vertexInfo<T>::BLACK)
		{
			// mark the vertex so we don't look at it again
			g.vInfo[currPos].color = vertexInfo<T>::BLACK;

			// find all neighbors of the current vertex pos. for each
			// neighbor that has not been visited, generate a minInfo
			// object and insert it into the priority queue provided the
			// total weight to get to the neighbor is better than the
			// current dataValue in vInfo
			adj = g.vInfo[currPos].edges;
			for(adjIter = adj.begin();adjIter != adj.end();
										adjIter++)
			{
				destPos = (*adjIter).dest;

				if (g.vInfo[destPos].color == vertexInfo<T>::WHITE)
				{
					// compare total weight of adding edge to dataValue
					if ((newMinWeight = (g.vInfo[currPos].dataValue +
						 (*adjIter).weight)) < g.vInfo[destPos].dataValue)
					{
						// add minVertexInfo object for new vertex and update
						// dataValue in vInfo
						vertexData.endV = destPos;
						vertexData.pathWeight = newMinWeight;
						g.vInfo[destPos].dataValue = newMinWeight;
						g.vInfo[destPos].parent = currPos;
						minPathPQ.push(vertexData);
					}	// end "if" that checks weights
				}	// end "if" that checks if neighbor is not marked
			}	// end "for"
		}	// end "if" vertex not already marked
	}	// end "while"

	// clear path and setup return
   path.erase(path.begin(), path.end());
   if (foundMinPath)
	{
		currPos = pos_eVertex;
		while (currPos != pos_sVertex)
		{
			path.push_front((*(g.vInfo[currPos].vtxMapLoc)).first);
			currPos = g.vInfo[currPos].parent;
		}
		path.push_front(sVertex);
		returnValue = g.vInfo[pos_eVertex].dataValue;
   }
   else
      returnValue = -1;