d_graph.h

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

template <typename T>
int graph<T>::numberOfEdges() const
{
	return numEdges;
}

template <typename T>
bool graph<T>::empty() const
{
	return numVertices == 0;
}

// ACCESS MEMBER FUNCTIONS

// return the weight of the edge (v1, v2). if the edge
// does not exist, return -1
template <typename T>
int graph<T>::getWeight(const T& v1, const T& v2) const
{
	// find the vInfo indices for the two vertices
	int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2);

	// check for an error
	if (pos1 == -1 || pos2 == -1)
		// if v1 or v2 not in list of vertices, throw an exception
		throw graphError("graph getWeight(): vertex not in the graph");

	// construct an alias for the edge list in vInfo[pos1]
	const set<neighbor>& edgeSet = vInfo[pos1].edges;
	set<neighbor>::const_iterator setIter;

	// search for pos2 in the edge list and return its weight
	// if found; otherwise, return -1 to indicate that the
	// edge does not exist
	if ((setIter = edgeSet.find(neighbor(pos2))) != edgeSet.end())
		return (*setIter).weight;
	else
		return -1;
}

template <typename T>
void graph<T>::setWeight(const T& v1, const T& v2, int w)
{
	// find the vInfo indices for the two vertices
	int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2);

	// check for an error
	if (pos1 == -1 || pos2 == -1)
		// if v1 or v2 not in list of vertices, throw an exception
		throw graphError("graph setWeight(): vertex not in the graph");

	// construct an alias for the edge list in vInfo[pos1]
	set<neighbor>& edgeSet = vInfo[pos1].edges;
	set<neighbor>::iterator setIter;

	// search for pos2 in the edge list and update its weight.
	// if the edge does not exist, throw an exception
	if ((setIter = edgeSet.find(neighbor(pos2))) != edgeSet.end())
		(*setIter).weight = w;
	else
		throw graphError("graph setWeight(): edge not in the graph");
}

// return the number of edges entering  v
template <typename T>
int graph<T>::inDegree(const T& v) const
{
	// find the vInfo index for v
	int pos=getvInfoIndex(v);

	if (pos != -1)
		// in-degree is stored in vInfo[pos]
		return vInfo[pos].inDegree;
	else
		// throw an exception
		throw graphError("graph inDegree(): vertex not in the graph");
}

// return the number of edges leaving  v
template <typename T>
int graph<T>::outDegree(const T& v) const
{
	// find the vInfo index for v
	int pos=getvInfoIndex(v);

	if (pos != -1)
		// out-degree is number of elements in the edge set
		return vInfo[pos].edges.size();
	else
		// throw an exception
		throw graphError("graph outDegree(): vertex not in the graph");
}

// return the list of all adjacent vertices
template <typename T>
set<T> graph<T>::getNeighbors(const T& v) const
{
	// set returned
	set<T> adjVertices;

	// obtain the position of v from the map
	int pos = getvInfoIndex(v);

	// if v not in list of vertices, throw an exception
	if (pos == -1)
		throw
			graphError("graph getNeighbors(): vertex not in the graph");

	// construct an alias for the set of edges in vertex pos
	const set<neighbor>& edgeSet = vInfo[pos].edges;
	// use setIter to traverse the edge set
	set<neighbor>::const_iterator setIter;

	// index of vertexInfo object corresponding to an adjacent vertex
	int aPos;

	for (setIter=edgeSet.begin(); setIter != edgeSet.end(); setIter++)
	{	// "(*setIter).dest" is index into vInfo
		aPos = (*setIter).dest;
		// insert vertex data into a set. vInfo[aPos].vtxMapLoc"
		// is a map iterator. dereference it to access the vertex
		adjVertices.insert ((*vInfo[aPos].vtxMapLoc).first);
	}

   return adjVertices;
}

// GRAPH MODIFICATION MEMBER FUNCTIONS

// add the edge (v1,v2) with specified weight to the graph
template <typename T>
void graph<T>::insertEdge(const T& v1,
								  const T& v2, int w)
{
	// obtain the vInfo indices
	int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2);

	// check for an error
	if (pos1 == -1 || pos2 == -1)
		// if v1 or v2 not in list of vertices, throw an exception
		throw graphError("graph insertEdge(): vertex not in the graph");
	else if (pos1 == pos2)
		// we do not allow self-loops
		throw graphError("graph insertEdge(): self-loops are not allowed");


	// attempt to insert edge (pos2,w) into the edge set of vertex pos1
	pair<set<neighbor>::iterator, bool> result =
			vInfo[pos1].edges.insert(neighbor(pos2,w));

	// make sure edge was not already in the set
	if (result.second)
	{
		// increment the number of edges
		numEdges++;
		// the in-degree of v2 is one more
		vInfo[pos2].inDegree++;
	}
}

// insert v into the graph
template <typename T>
void graph<T>::insertVertex(const T& v)
{
	int index;

	// attempt to insert v into the map with index 0.
	// if successful, insert an iterator pointing at it
	// into the vertex list at location index. index is obtained
	// from the availability stack or by creating a new entry
	// at the back of the vector. fix the map entry to refer
	// to index and increment numVertices. if the insertion did
	// not take place, the vertex already exists. generate an
	// exception
	pair<vertexMap::iterator, bool> result =
		vtxMap.insert(vertexMap::value_type(v,0));
	if (result.second)
	{
		// see if there is an entry in vInfo freed by an earlier
		// call to eraseVertex()
		if (!availStack.empty())
		{
			// yes. get its index
			index = availStack.top();
			availStack.pop();
			// call to constructor builds a empty edge set
			vInfo[index] = vertexInfo<T>(result.first);
		}
		else
		{
			// no. we'll have to increase the size of vInfo
			vInfo.push_back(vertexInfo<T>(result.first));
			index = numVertices;
		}

		(*result.first).second = index;
		numVertices++;
	}
	else
		throw graphError("graph insertVertex(): vertex already in the graph");
}

// erase edge (v1,v2) from the graph
template <typename T>
void graph<T>::eraseEdge(const T& v1, const T& v2)
{
	// obtain the indices of v1 and v2 in vInfo
	int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2);

	// check for an error
	if (pos1 == -1 || pos2 == -1)
		// if v1 or v2 not in list of vertices, throw an exception
		throw graphError("graph eraseEdge(): vertex not in the graph");

	// construct an alias to the edge set of vInfo[pos1]
	set<neighbor>& edgeSet = vInfo[pos1].edges;
	set<neighbor>::iterator setIter;

	// search for pos2 in the edge set
	setIter = edgeSet.find(neighbor(pos2));
	// if pos2 is in the set, erase it; otherwise, output an
	// error message
	if (setIter != edgeSet.end())
	{
		edgeSet.erase(setIter);
		// the in-degree of v2 is one less
		vInfo[pos2].inDegree--;
		numEdges--;
	}
	else
		throw graphError("graph eraseEdge(): edge not in the graph");
}

template <typename T>
void graph<T>::eraseVertex(const T& v)
{
	// use to search for and remove v from the map
	vertexMap::iterator mIter;
	// pos is index of v in the vertex list
	int pos, j;
	// used in removal of edges to v
	set<neighbor>::iterator sIter;

	// search the map for the key v
	mIter = vtxMap.find(v);
	// if vertex is not present, terminate the erase
	if (mIter == vtxMap.end())
		// if v not in list of vertices, throw an exception
		throw graphError("graph eraseVertex(): vertex not in the graph");

	// obtain the index of v in vInfo
	pos = (*mIter).second;

	// erase vertex from the map and decrement number of vertices
	vtxMap.erase(mIter);
	numVertices--;

	// mark the vertex entry in vInfo as not occupied. the index pos is now
	// available. push it on the availability stack for use later if we
	// insert a vertex
	vInfo[pos].occupied = false;
	availStack.push(pos);

	// cycle through vInfo and remove all edges going to v
	for (j=0; j < vInfo.size(); j++)
		// skip all unoccupied entries, including pos
		if (vInfo[j].occupied)
		{
			// construct an alias for the set vInfo[j].edges
			set<neighbor>& edgeSet = vInfo[j].edges;

			sIter = edgeSet.begin();
			// cycle through the edge set
			while (sIter != edgeSet.end())
				if ((*sIter).dest == pos)
				{
					// found pos. remove it from the set and
					// decrement the edge count
					edgeSet.erase(sIter);
					numEdges--;
					break;
				}
				else
					// took no action. just move forward
					sIter++;
		}

	// decrement numEdges by the number of edges for vertex v
	numEdges -= vInfo[pos].edges.size();

	// the in-degree for all of v's neighbors must be decreased by 1
	set<neighbor>& edgesFromv = vInfo[pos].edges;
	for (sIter=edgesFromv.begin(); sIter != edgesFromv.end(); sIter++)
	{
		j = (*sIter).dest;
		vInfo[j].inDegree--;
	}

	// clear the edge set. construct an alias for vInfo[pos].edges
	// and use erase to clear the set
	set<neighbor>& edgeSet = vInfo[pos].edges;
	edgeSet.erase(edgeSet.begin(), edgeSet.end());
}

// erase the graph
template <typename T>
void graph<T>::clear()
{
	// clear the vertex list, vertex map and the
	// availability stack
	vInfo.erase(vInfo.begin(), vInfo.end());
	vtxMap.erase(vtxMap.begin(), vtxMap.end());
	while(!availStack.empty())
		availStack.pop();

	// set the number of vertices and edges to 0
	numVertices = 0;
	numEdges = 0;
}

// ITERATOR FUNCTIONS

// each graph iterator function returns
// the corresponding map iterator
template <typename T>
graph<T>::iterator graph<T>::begin()
{
  return graph<T>::iterator(vtxMap.begin());
}

template <typename T>
graph<T>::iterator graph<T>::end()
{
	return graph<T>::iterator(vtxMap.end());
}

template <typename T>
graph<T>::const_iterator graph<T>::begin() const
{
	return graph<T>::iterator(vtxMap.begin());
}

template <typename T>
graph<T>::const_iterator graph<T>::end() const
{
  return graph<T>::iterator(vtxMap.end());
}

#endif	// GRAPH_CLASS