graph.cpp

关于图的一个程序

//FOR GLORY!
//MY HONOR IS MY LIFE!
// 我真诚地保证：
//   
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
//
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
//
// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
//
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
//   
// 0113325   	杨剑锋　　　　　
// 完成于2003.12.23
//


#include "iostream.h"
#include "edge.h"
#include "graph.h"
#include "ctype.h"
#include "stdlib.h"

CGraph<30>	g;

void visit(int a);
void load();
void help();
void runorder();
int gn();
bool rdtu(int a, int b);

int main()
{
	
	help();			//显示帮助信息
	runorder();
	return 0;
}

void visit(int a)
//	功能:	输出图的节点
//	输出:	图的节点信息
//	参数:	
//		a:		图的节点信息
{
	if( a>=0 )
		cout << a << ", ";	//输出节点
	else 
		cout << endl;		//换行
}

void load()
//	功能:	加载一个图
{
	g.clear();		//清空
	g.Insert(20);
	g.Link(0, 1);
	g.Link(0, 2);
	g.Link(0, 3);
	g.Link(1, 4);
	g.Link(2, 3);
	g.Link(3, 4);
	g.Link(1, 5);
	g.Link(1, 6);
	g.Link(2, 7);
	g.Link(5, 7);
	g.Link(6, 8);
	g.Link(2, 9);
	g.Link(6,10);
	g.Link(8,11);
	g.Link(9,12);
	g.Link(5,13);
	g.Link(0,14);
	g.Link(11,15);
	g.Link(12,16);
	g.Link(5,17);
	g.Link(2,18);
	g.Link(11,19);
	g.Link(9,15);
	g.Link(13,17);
	g.Link(6,18);
}

void help()
//	功能:	输出帮助信息
{
	cout << "HELP INFORMATION:"			<< endl		//帮助信息
		 << "	b:	breadth first traversal."		<< endl
		 
		 << "	d:	depth first traversal."		<< endl
		 << "	c:	clear."			<< endl
		 << "	e:	add edge ."		<< endl
		 
		 << "	i:	add node."		<< endl
		 << "	l:	load graph."		<< endl
		 << "	r:	creat a random graph."<< endl
		 << "	p:	search for the special path."	<< endl
		 << "	z:	search for the longest path."	<< endl
		 << "	h:	show help information."	<< endl
		 << "	q:	exit."			<< endl
		 << endl;
}

void runorder()
//	功能:	执行输入的命令
//	输出:	运行结果
{
	int num,num1,num2,num3;;
	char	c;
	do
	{
		cout << endl;
		cout << '>';
		cin >> c;			//得到命令
		switch(c)
		{
		case 'b':			//广度遍历
			num = gn();
			if( num==-1 )	continue;
			cout << "breadth first traversal:" << endl;
			g.bfs(num, visit);
			break;
		case 'c':			//清空图
			g.clear();
			break;
		case 'd':			//深度遍历
			num = gn();		//读取错误
			if( num==-1 )	continue;
			cout << "depth first traversal:" << endl;
			g.dfs(num, visit);
			break;
		case 'e':			//加边
			num1 = gn();
			if(num1==-1)continue;
			num2 = gn();
			if(num2==-1)continue;
			if(g.exist(num1, num2))
			{
				cout << "This edge already exist!" << endl;
				break;
			}
			if(!g.Link(num1, num2))	cout << "Link false!" << endl;
			break;
		case 'h':			//显示帮助信息
			help();
			break;
		case 'l':			//加载一个图
			load();
			cout << "Load successful." << endl;
			break;
		case 'r':			//随即生成一个图
			num1 = gn();
			if( num1==-1 )	continue;
			num2 = gn();
			if( num2==-1 )	continue;
			if( !rdtu(num1, num2) )	cout << "False!" << endl;
			else	cout << "Load successful." << endl;
			break;
		case 'i':			//加点
			if( !g.Insert() )	cout << "Insert false!" << endl;
			break;
		case 'p':			//寻找两点间定长路经
			num1 = gn();
			if( num1==-1 )	continue;
			num2 = gn();
			if( num2==-1 )	continue;
			num3 = gn();
			if( num3==-1 )	continue;
			if( !g.spath(num1, num2, num3, visit) )	cout << "Can't find path!" << endl;
			break;
		case 'z':			//寻找两点间最长路经
			num1 = gn();
			if( num1==-1 )	continue;
			num2 = gn();
			if( num2==-1 )	continue;
			num = g.slp(num1, num2, visit);
			cout << "the length of the path:" << num << endl;
			break;
		case 'q':			//退出
			g.clear();
			return;
		}
	}while(1);
}

int gn()
//	功能:	输入数字
//	返回值:	输入的数值
{
	char	ch;
	int		num;
	cin >> ch;
	if( isdigit(ch) )		//输入正确
	{
		cin.putback(ch);
		cin >> num;
	}
	else
	{						//输入类型错误
		cout << "Input error!" << endl;
		return -1;
	}
	return num;
}

bool rdtu(int a, int b)
//	功能:	随即生成一个连通图
//	返回值:	是否成功
{
	int		i;
	int		v1, v2;
	int		num;
	num = (a*(a-1)) / 2;
	if( b>num )	return false;	//边过多
	if( b<a-1 )	return false;	//边过少，无法建立连通图
	g.clear();
	if( !g.Insert(a) )	return false;	//顶点过多
	for(i=1; i<a; i++)
	{
		do
		{
			v1 = rand()%i;		//随机
		}while( g.exist(i, v1) );	//该边存在
		g.Link(i, v1);		
	}
	for(i=a-1; i<b; i++)
	{
		do
		{
			v1 = rand()%a;
			v2 = rand()%a;
		}while( g.exist(v1,v2) || v1==v2 );	//该边存在
		g.Link(v1, v2);
	}
	return true;
}