d_graph.h

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

#ifndef GRAPH_CLASS
#define GRAPH_CLASS

#include <iostream>
#include <fstream>

#include <set>				// set class
#include <map>				// ist classmap class
#include <vector>			// vector class
#include <list>			// list class
#include <stack>			// stack class
#include <queue>			// queue class
#include <functional>	// less<T>

#include "d_except.h"	// exception classes
#include "d_pqueue.h"	// miniPQ class

// largest positive integer on the machine
const int INFINITY = (int)((unsigned int)~0 >> 1);

using namespace std;

class neighbor
{
	public:
		// index of the destination vertex in the vector vInfo of vertex
		// properties
		int dest;
		// weight of this edge
		int weight;

		// constructor
		neighbor(int d=0, int c=0): dest(d), weight(c)
		{}

		// operators for the neighbor class that compare the
		// destination vertices
		friend bool operator< (const neighbor& lhs, const neighbor& rhs)
		{
			return lhs.dest < rhs.dest;
		}

		friend bool operator== (const neighbor& lhs, const neighbor& rhs)
		{
			return lhs.dest == rhs.dest;
		}
};

// maintains vertex properties, including its set of
// neighbors
template <typename T>
class vertexInfo
{
	public:
		// used by graph algorithms
		enum vertexColor { WHITE, GRAY, BLACK };

		// iterator pointing at a pair<T,int> object in the vertex map
		map<T,int>::iterator vtxMapLoc;

		// set of adjacent (neighbor) objects for the current vertex
		set<neighbor> edges;

		/// maintains the in-degree of the vertex
		int inDegree;

		// indicates whether the object currently represents a vertex
		bool occupied;

		// indicate if a vertex is marked in an algorithm that traverses
		// the vertices of a graph
		vertexColor color;

		// available to algorithms for storing relevant data values
		int dataValue;

		// available to graph algorithms; holds parent which is
		// a vertex that has an edge terminating in the current vertex
		int parent;

		// default constructor
		vertexInfo(): inDegree(0), occupied(true)
		{}

		// constructor with iterator pointing to the vertex in the map
		vertexInfo(map<T,int>::iterator iter):
				vtxMapLoc(iter), inDegree(0), occupied(true)
		{}
};

// priority queue data used by minimumPath() and minSpanningTree() algorithms
class minInfo
{
	public:
		int endV;
		int pathWeight;

		friend bool operator< (minInfo lhs, minInfo rhs)
		{ return lhs.pathWeight < rhs.pathWeight; }
};

template <typename T>
class graph
{
   public:
      class const_iterator: public map< T, int >::const_iterator
      {
         public:
            const_iterator()
            {}

				// converts a map iterator to a graph iterator
            const_iterator(map<T,int>::const_iterator i)
            {
					*((map< T, int >::const_iterator *)this) = i;
				}

				// return the vertex pointed to by the iterator
            const T& operator* () const
            {
               map<T,int>::const_iterator p = *this;

               return (*p).first;
            }
      };

		typedef const_iterator iterator;

		graph();
			// constructor. initialize numVertices and numEdges to 0

		graph(const graph<T>& g);
			// copy constructor

		graph<T>& operator= (const graph<T>& rhs);
			// overloaded assignment operator

		int numberOfVertices() const;
			// return the number of vertices in the graph

		int numberOfEdges() const;
			// return the number of edges in the graph

      bool empty() const;
			// is the graph empty?

		int getWeight(const T& v1, const T& v2) const;
			// return the weight of the edge (v1, v2). if the edge.
			// does not exist, return -1
			// Precondition: v1 and v2 are vertices in the graph. if not
			// the function throws the graphError exception

		void setWeight(const T& v1, const T& v2, int w);
			// update the weight of edge (v1, v2).
			// Precondition: v1 and v2 are vertices in the graph. if not,
			// the function throws the graphError exception
			// Postcondition: the weight of vertex (v1,v2) is w

		int inDegree(const T& v) const;
			// return the number of edges entering  v.
			// Precondition: v is a vertex in the graph. if not,
			// the function throws the graphError exception

		int outDegree(const T& v) const;
			// return the number of edges leaving  v.
			// Precondition: v is a vertex in the graph. if not,
			// the function throws the graphError exception

      set<T> getNeighbors(const T& v) const;
			// return a set containing the neighbors of v.
			// Precondition: v is a vertex in the graph. if not,
			// the function throws the graphError exception

		void insertEdge(const T& v1, const T& v2, int w);
			// add the edge (v1,v2) with specified weight to the graph.
			// Precondition: v1 and v2 are vertices in the graph. if not,
			// the function throws the graphError exception
			// Postcondition: The number of edges increases by 1

		void insertVertex(const T& v);
			// insert v into the graph.
			// Precondition: v is a vertex in the graph. if not,
			// the function throws the graphError exception.
			// Postcondition: the number of vertices increases by 1

		void eraseEdge(const T& v1, const T& v2);
			// erase edge (v1,v2) from the graph
			// Precondition: v1 and v2 are vertices in the graph. if not,
			// the function throws the graphError exception.
			// Postcondition: The number of edges decreases by 1

      void eraseVertex(const T& v);
			// erase v from the graph
			// Precondition: v is a vertex in the graph. if not,
			// the function throws the graphError exception.
			// Postconditions: The number of vertices decreases by 1,
			// and the operation removes all edges to or from v

		void clear();
			// remove all the vertices and edges from the graph

		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;
			// iterator functions returns corresponding map iterator

// "d_galgs.h" implements the graph algorithms using inline code.
// this is necessary for the Borland C++ 5.5 compiler
#include "d_galgs.h"

/*
		LISTING OF THE PROTOTYPES FOR THE GRAPH ALGORITHMS

		friend istream& operator>> (istream& istr, graph<T>& g);
			// input a graph

		friend ostream& operator<< (ostream& ostr, const graph<T>& g);
			// output a graph

		friend set<T> bfs(graph<T>& g, const T& sVertex);
			// perform the breadth-first traversal from sVertex and
			// return the set of visited vertices

		friend int shortestPath(graph<T>& g, const T& sVertex,
										const T& eVertex, list<T>& path);
			// 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 minimumPath(graph<T>& g, const T& sVertex, const T& eVertex,
									  list<T>& path);
			// find the path with minimum total weight from sVertex to eVertex
			// and return the minimum weight

		friend int minSpanTree(graph<T>& g, graph<T>& MST);
			// find the minimum spanning tree for the strongly connected digraph g

		friend bool acyclic(graph<T>& g);
			// determine if the graph is acyclic

		friend void dfsVisit(graph<T>& g, const T& sVertex, list<T>& dfsList,
									bool checkForCycle);
			// depth-first visit assuming a WHITE starting vertex. dfsList
			// contains the visited vertices in reverse order of finishing time.
			// when checkForCycle is true, the function throws an exception if
			// it detects a cycle

		friend void dfs(graph<T>& g, list<T>& dfsList);
			// depth-first search. dfsList contains all the graph vertices in the
			// reverse order of their finishing times

		friend void topologicalSort(graph<T>& g, list<T>& tlist);
			// find a topological sort of an acyclic graph

		friend graph<T> transpose(graph<T>& g);
			// return the transpose of the graph

		friend void strongComponents(graph<T>& g, vector<set<T> >& component);
			// find the strong components of the graph
*/

	private:
      typedef map<T,int> vertexMap;

		vertexMap vtxMap;
			// store vertex in a map with its name as the key and the index
			// of the corresponding vertexInfo object in the vInfo
			// vector as the value

		vector<vertexInfo<T> > vInfo;
			// list of vertexInfo objects corresponding to the vertices

		int numVertices;
		int numEdges;
			// current size (vertices and edges) of the graph

		stack<int> availStack;
			// availability stack for storing unused indices in vInfo

		int getvInfoIndex(const T& v) const;
     		// uses vtxMap to obtain the index of v in vInfo
};

// uses vtxMap to obtain the index of v in vInfo
template <typename T>
int graph<T>::getvInfoIndex(const T& v) const
{
	// iter used in map lookup
	vertexMap::const_iterator iter;
	// index that is returned
	int pos;

	// find the map entry with key v
	iter = vtxMap.find(v);

	// make sure v is in the map
	if (iter == vtxMap.end())
		pos = -1;
	else
		// the index into vInfo is the value of the map entry
		pos = (*iter).second;

	return pos;
}

// constructor. initialize numVertices and numEdges to 0
template <typename T>
graph<T>::graph(): numVertices(0), numEdges(0)
{}

// copy constructor
template <typename T>
graph<T>::graph(const graph<T>& g)
{
	*this = g;	// copy g to current object
}

// overloaded assignment operator
template <typename T>
graph<T>& graph<T>::operator= (const graph<T>& rhs)
{
	vertexMap::iterator mi;

	// can't copy a graph to itself
	if (this == &rhs)
		return *this;

	// copy rhs to current object
	vtxMap = rhs.vtxMap;
	vInfo = rhs.vInfo;
	numVertices = rhs.numVertices;
	numEdges = rhs.numEdges;
	availStack = rhs.availStack;

	// update each vtxMapLoc value of objects in vInfo so it points
	// to a key-value pair in the copy of rhs.vtxMap and not rhs.vtxMap
	for (mi=vtxMap.begin();mi != vtxMap.end();mi++)
			vInfo[(*mi).second].vtxMapLoc = mi;

	return *this;
}

// ATTRIBUTE TESTING FUNCTIONS

template <typename T>
int graph<T>::numberOfVertices() const
{
	return numVertices;
}