lgraph.h

常用算法与数据结构原代码

// file lgraph.h
// linked adjacency list representation of a graph
// initial version

#ifndef LinkedGraph_
#define LinkedGraph_

#include "ldigraph.h"
#include "xcept.h"

class NodeType 
{
	friend class LinkedGraph;
private:
	int left, right;
};

class LinkedGraph : public LinkedDigraph 
{
public:
	LinkedGraph(int Vertices = 10)
        : LinkedDigraph (Vertices) 
	{
	}
	LinkedGraph& Add(int i, int j);
	LinkedGraph& Delete(int i, int j);
	int Degree(int i) const 
	{
		return InDegree(i);
	}
	int OutDegree(int i) const
	{
		return InDegree(i);
	}
	void Input()
    {
		Input(cin);
	}
    void Input(istream& in);
	bool Connected();
	int  LabelComponents(int L[]);
	bool BipartiteCover(int L[], int C[], int& m);
protected:
	LinkedGraph& AddNoCheck(int i, int j);
private:
	void CreateBins(int b, int n);
	void DestroyBins() {delete [] node;
	delete [] bin;}
	void InsertBins(int b, int v);
	void MoveBins(int bMax, int ToBin, int v);
	int *bin;
	NodeType *node;
};

LinkedGraph& LinkedGraph::Add(int i, int j)
{// Add edge (i,j) to the graph.
	if (i < 1 || j < 1 || i > n || j > n || i ==j || Exist(i, j))
		throw BadInput();
	return AddNoCheck(i, j);
}

LinkedGraph& LinkedGraph::AddNoCheck(int i, int j)
{// Add edge (i,j), no error checks.
	h[i].Insert(0,j);
	try 
	{
		h[j].Insert(0,i);
	}
	// on exception, undo first insert
	// and rethrow same exception
	catch (...) 
	{
		h[i].Delete(j);
		throw;
	}
	e++;
	return *this;
}

LinkedGraph& LinkedGraph::Delete(int i, int j)
{// Delete edge (i,j).
	LinkedDigraph::Delete(i,j);
	e++; // compensate
	LinkedDigraph::Delete(j,i);
	return *this;
}

void LinkedGraph::Input(istream& in)
{// Input the adjacency lists.
	// first delete the old graph
	delete [] h;
	
	// input new size and create h
	cout << "Enter the number of vertices in the graph" << endl;
	cin >> n;
	if (n < 0) throw BadInput();
	cout << "Enter the number of edges in the graph" << endl;
	int E;
	cin >> E;
	if (E < 0 || E > n*(n-1)/2) throw BadInput();
	h = new Chain<int> [n+1];
	
	// now input the edges and add them to the adjacency
	// lists
	e = 0;
	int u, v;  // edge end points
	for (int i = 1; i <= E; i++) 
	{
		cout << "Enter edge " << i << endl;
		in >> u >> v;
		if (u < 1 || v < 1 || u > n || v > n)
			throw BadInput();
		AddNoCheck(u,v);
	}
	
	// check for duplicate edges
	bool *seen = new bool [n+1];
	for (i = 1; i <= n; i++)
		seen[i] = false;
	ChainIterator<int> c;
	for (i = 1; i <= n; i++) 
	{// check vertex i
		int *k = c.Initialize(h[i]);
		while (k)
		{// not at list end 
			if (seen[*k]) 
			{// duplicate edge
				delete [] seen;
				throw BadInput();
			}
			else 
				seen[*k] = true;
			k = c.Next();
		}
		// reset seen
		k = c.Initialize(h[i]);  
		while (k) 
		{// not at list end 
			seen[*k] = false;
			k = c.Next();
		}
	}
	
	delete [] seen;
}

// overload >>
istream& operator>>(istream& in, LinkedGraph& x)
{
	x.Input(in);
	return in;
}

bool LinkedGraph::Connected()
{// Return true iff graph is connected.
	
	int n = Vertices();
	
	// set all vertices as not reached
	int *reach = new int [n+1];
	for (int i = 1; i <= n; i++)
		reach[i] = 0;
	
	// mark vertices reachable from vertex 1
	DFS(1, reach, 1);
	
	// check if all vertices marked
	for (i = 1; i <= n; i++)
		if (!reach[i]) return false;
		return true;
}

int LinkedGraph::LabelComponents(int L[])
{// Label the components of the graph.
	// Return the number of components and set L[1:n]
	// to represent a labeling of vertices by component.
	
	int n = Vertices();
	
	// assign all vertices to no component
	for (int i = 1; i <= n; i++)
		L[i] = 0;
	
	int label = 0;  // ID of last component
	// identify components
	for (i = 1; i <= n; i++)
		if (!L[i]) {// unreached vertex
			// vertex i is in a new component
			label++;
			BFS(i, L, label);} // mark new component
		
		return label;
}

void LinkedGraph::CreateBins(int b, int n)
{// Create b empty bins and n nodes.
	node = new NodeType [n+1];
	bin = new int [b+1];
	// set bins empty
	for (int i = 1; i <= b; i++)
		bin[i] = 0;
}

void LinkedGraph::InsertBins(int b, int v)
{// Insert v into bin b unless b is zero.
	if (!b) return;   // do not insert in bin 0
	node[v].left = b; // add at left end
	if (bin[b]) 
		node[bin[b]].left = v;
	node[v].right = bin[b];
	bin[b] = v;
}

void LinkedGraph::MoveBins(int bMax, int ToBin, int v)
{// Move vertex v from its current bin to bin ToBin.
	// nodes to the left and right of v
	int l = node[v].left;
	int r = node[v].right;
	
	// delete from current bin
	if (r) 
		node[r].left = node[v].left;
	if (l > bMax || bin[l] != v) // not left-most one
		node[l].right = r;
	else 
		bin[l] = r;             // left-most in bin l
	
	// add to bin ToBin
	InsertBins(ToBin, v);
}

bool LinkedGraph::BipartiteCover(int L[], int C[], int& m)
{// Find a cover of the bipartite graph.
	// L is the input vertex labeling, L[i] = 1 iff i is
	// in A.  C is an output array that identifies the
	// cover.  Return false if the graph has no cover.
	// If the graph has a cover, return true;
	// return cover size in m; and cover in C[0:m-1].
	
	int n = Vertices();
	
	// create structures
	int SizeOfA = 0;
	for (int i = 1; i <= n; i++) // find size of set A
	{
		if (L[i] == 1) 
			SizeOfA++;
	}
	int SizeOfB = n - SizeOfA;
	CreateBins(SizeOfB, n);
	int *New = new int [n+1];
	// vertex i covers New[i] uncovered vertices of aB
	bool *Change = new bool [n+1];
	// Change[i] is true iff New[i] has changed
	bool *Cov = new bool [n+1];
	// Cov[i] is true iff vertex i is covered
	InitializePos();
	LinkedStack<int> S;
	
	// initialize
	for (i = 1; i <= n; i++) 
	{
		Cov[i] = Change[i] = false;
		if (L[i] == 1) 
		{// i is in A
			New[i] = Degree(i); // i covers this many
			InsertBins(New[i], i);
		}
	}
	
	// construct cover
	int covered = 0,       // # of covered vertices
		MaxBin = SizeOfB;  // max bin that may be
	// nonempty
	m = 0;                 // cursor for C
	while (MaxBin > 0)
	{   // search all bins
		// select a vertex
		if (bin[MaxBin]) 
		{      // bin not empty
			int v = bin[MaxBin]; // first vertex
			C[m++] = v;          // add v to cover
			// label newly covered vertices
			int j = Begin(v), k;
			while (j)
			{
				if (!Cov[j]) 
				{// j not covered yet
					Cov[j] = true;
					covered++;
					// update New
					k = Begin(j);
					while (k) 
					{
						New[k]--;     // j does not count
						if (!Change[k]) 
						{
							S.Add(k);  // stack once only
							Change[k] = true;
						}
						k = NextVertex(j);
					}
				}
				j = NextVertex(v);
			}
			
			// update bins
			while (!S.IsEmpty()) 
			{
				S.Delete(k);
				Change[k] = false;
				MoveBins(SizeOfB, New[k], k);
			}
		}
		else 
			MaxBin--;
	}
	
	DeactivatePos();
	DestroyBins();
	delete [] New;
	delete [] Change;
	delete [] Cov;
	
	return (covered == SizeOfB);
}

#endif