graph.cpp

bayes network 的分三角形的算法

#include "StdAfx.h"
#include ".\graph.h"

Graph::Graph(void):
nodeNumber(0),edgeNumber(0),weight(1)
{
}

//拷贝构造函数
Graph::Graph(const Graph &g)
{
	//复制来源矩阵
	nodeNumber=g.nodeNumber;	//设置总节点数
	edgeNumber=g.edgeNumber;	//设置边的总数
	weight=g.weight;			//拷贝权重
	//用来源矩阵元素，初始化邻接矩阵
	for(int i=0;i<nodeNumber;i++)
		for(int j=0;j<nodeNumber;j++)
			nodeMatrix[i][j]=g.nodeMatrix[i][j];
	//创建对应的节点表
	for(int i=0;i<nodeNumber;i++)
		nodes[i]=g.nodes[i];
}

Graph::~Graph(void)
{
}

//创建图的实例
void Graph::Create(int number)
{
	nodeNumber=number;	//设置总节点数
	//初始化邻接矩阵,自己和自己连通
	for(int i=0;i<nodeNumber;i++)
		for(int j=0;j<nodeNumber;j++)
		{
			if(i==j)
				nodeMatrix[i][j]=1;
			else
				nodeMatrix[i][j]=0;
		}
}

//添加节点信息
void Graph::AddNode(GraphNode const &node,int index)
{
	nodes[index]=node;
	//计算图的权重，等于节点权重的乘积
	weight*=node.weight;
}

//添加边信息
void Graph::AddRelationship(int from,int to)
{
	nodeMatrix[from][to]=1;
	edgeNumber++;
	//记录其父节点
	nodes[to].parentID.push_back(from);
}

//删除边
void Graph::RemoveRelationship(int from,int to)
{
	nodeMatrix[from][to]=0;
	edgeNumber--;
}

//查看图的内存结构
void Graph::Dump()
{
	for(int i=0;i<nodeNumber;i++)
		cout<<"第"<<i<<"个节点：名称"<<nodes[i].name<<endl;
	cout<<"边数："<<edgeNumber<<endl;
	//写矩阵内容
	for(int i=0;i<nodeNumber;i++)
	{
		for(int j=0;j<nodeNumber;j++)
			cout<<nodeMatrix[i][j]<<'\t';
		cout<<endl;
	}
}

//赋值操作符
Graph Graph::operator=(const Graph &g)
{
	//复制来源矩阵
	nodeNumber=g.nodeNumber;	//设置总节点数
	edgeNumber=g.edgeNumber;	//拷贝边的总数
	weight=g.weight;			//拷贝权重

	//用来源矩阵元素，初始化邻接矩阵
	for(int i=0;i<nodeNumber;i++)
		for(int j=0;j<nodeNumber;j++)
			nodeMatrix[i][j]=g.nodeMatrix[i][j];
	//创建对应的节点表
	for(int i=0;i<nodeNumber;i++)
		nodes[i]=g.nodes[i];

	return *this;
}

//产生道义图
Graph Graph::GenerateGm()
{
	Graph tmpGraph(*this);
	//连接双亲
	for(int i=0;i<tmpGraph.nodeNumber;i++)
	{
		//取得一个节点
		GraphNode node=tmpGraph.nodes[i];
		//遍历该节点双亲,正反两次关系
		for(int itr=0;itr<node.parentID.length;itr++)
		{
			for(int itr_inner=0;itr_inner<node.parentID.length;itr_inner++)
			{
				//如果不是自己，并且之前没有关系，则添加关系
				if(node.parentID[itr]!=node.parentID[itr_inner] && 
					0==tmpGraph.nodeMatrix[node.parentID[itr]][node.parentID[itr_inner]])
					tmpGraph.AddRelationship(node.parentID[itr],node.parentID[itr_inner]);
			}
		}
	}
	//cout<<endl;
	//tmpGraph.Dump();
	//cout<<endl;

	//生成无向无环图，对称复制矩阵元素
	for(int i=0;i<tmpGraph.nodeNumber;i++)
		for(int j=0;j<tmpGraph.nodeNumber;j++)
			//如果单向有关系的话就添加关系成为双向的
			if(1==tmpGraph.nodeMatrix[i][j] && 0==tmpGraph.nodeMatrix[j][i])
				tmpGraph.AddRelationship(j,i);

	//cout<<endl;
	//tmpGraph.Dump();
	//cout<<endl;

	return tmpGraph;
}

//生成三角图
Graph::TriGraph Graph::Triangulate()
{
	Graph gc(GenerateGm());	//产生道义图的副本
	GraphNode selectNode;	//选择的节点
	Graph cluster;
	Graph copyCluster;	//上面那个cluster的副本
	TriGraph savedCluster;

	while(gc.nodeNumber>0)
	{
		selectNode=SelectNode(gc);	//获得选择的节点
		//取得簇的大小，等于相连节点的数目,加上自身
		int clusterSize=static_cast<int>(selectNode.parentID.length+1);
		//创建簇
		cluster.Create(clusterSize);
		//添加簇节点
		int index=0;
		cluster.AddNode(selectNode,index);	//添加自身
		index++;
		for(int itr=0;itr<selectNode.parentID.length;itr++)
		{
			cluster.AddNode(gc.nodes[selectNode.parentID[itr]],index);
			index++;
		}
		//对簇添加相应的边
		copyCluster=cluster;
		for(int i=0;i<cluster.nodeNumber;i++)	//对所有的簇的节点，取其父节点集合
		{
			for(int j=0;j<cluster.nodeNumber;j++)
			{
				//看父节点ID是否等于簇内节点的原有ID
				for(int itr=0;itr<cluster.nodes[i].parentID.length;itr++)
					if(cluster.nodes[i].parentID[itr]==cluster.nodes[j].ID)					
						copyCluster.AddRelationship(j,i);	//是的话，在簇内添加关系
			}
		}
		//改成三角图
		copyCluster.MakeTriangle();
		for(int i=0;i<copyCluster.nodeNumber;i++)
		{
			for(int j=0;j<copyCluster.nodeNumber;j++)
			{
				//如果不是自身，且cluster中有连线，且gc中没有
				if(i!=j && 
					(1==copyCluster.nodeMatrix[i][j] || 1==copyCluster.nodeMatrix[j][i]) &&
					0==gc.nodeMatrix[copyCluster.nodes[i].ID][copyCluster.nodes[j].ID])
				{
					gc.AddRelationship(copyCluster.nodes[i].ID,copyCluster.nodes[j].ID);
				}
			}
		}

		//cout<<endl;
		//copyCluster.Dump();
		//cout<<endl;

		//是否为已经保存过的簇
		if(!IsSaved(copyCluster,savedCluster))
			savedCluster.push_back(copyCluster);
		//从gc中删除n和所有边
		gc.RemoveNode(selectNode.ID);
		//清空簇
		cluster.Clear();
	}
	return savedCluster;
}

GraphNode Graph::SelectNode(const Graph &gc)
{
	Graph cluster;
	Graph copyCluster;
	GraphNode selectNode;
	int numberNodes=gc.nodeNumber;	//道义图副本的节点数
	int numberEdges=gc.edgeNumber;	//道义图副本的边数
	int maxEdgesToAdd=numberNodes*(numberNodes-1)-numberEdges;	//加入到簇的最大边数的极大值
	int edgesToAdd;				//加入到簇的边数
	int maxWeight=gc.weight;	//取得图的权重

	for(int i=0;i<gc.nodeNumber;i++)	//对每个节点
	{
		//取得簇的大小，等于相连节点的数目,加1，包括自身
		int clusterSize=static_cast<int>(gc.nodes[i].parentID.length+1);
		//创建簇
		cluster.Create(clusterSize);
		//添加簇节点
		int index=0;
		cluster.AddNode(gc.nodes[i],index);	//添加自身
		index++;
		for(int itr=0;itr<gc.nodes[i].parentID.length;itr++)
		{
			cluster.AddNode(gc.nodes[gc.nodes[i].parentID[itr]],index);
			index++;
		}
		//对簇添加相应的边
		copyCluster=cluster;	//复制一个簇
		for(int m=0;m<cluster.nodeNumber;m++)	//对所有的簇的节点，取其父节点集合
		{
			for(int n=0;n<cluster.nodeNumber;n++)
			{
				//看父节点ID是否等于簇内节点的原有ID
				for(int itr=0;itr<cluster.nodes[m].parentID.length;itr++)
					if(cluster.nodes[m].parentID[itr]==cluster.nodes[n].ID)					
						copyCluster.AddRelationship(n,m);	//是的话，在簇内添加关系
			}
		}

		//选择加入边最少的簇
		edgesToAdd=((copyCluster.nodeNumber-3)*2+3)*2
			-copyCluster.edgeNumber;	//形成三角图应该有的边数减去实际边数
		if(edgesToAdd<maxEdgesToAdd)	//如果是最小添加边
		{
			selectNode=cluster.nodes[0];
			maxEdgesToAdd=edgesToAdd;
		}
		else if(edgesToAdd==maxEdgesToAdd)	//如果最小添加边一样，比较权重
		{
			if(cluster.weight<=maxWeight)	//如果权重小于或者相等
			{
				selectNode=cluster.nodes[0];
				maxWeight=cluster.weight;
			}
		}
		//清空簇
		cluster.Clear();
	}

	return selectNode;
}

//清空图
void Graph::Clear()
{
	//节点数和边数置零
	nodeNumber=edgeNumber=0;
	//权重置1
	weight=1;
}

//判断是否为已经保存过的簇
bool Graph::IsSaved(const Graph &cluster,const TriGraph &savedCluster)
{
	for(int itr=0;itr<savedCluster.length;itr++)
		if(cluster<=savedCluster[itr])	//如果cluster包含在已保存过的某个簇中
			return true;
	return false;
}

//判断两个图的是否是包含关系
bool Graph::operator<=(const Graph &g) const
{
	if(nodeNumber>g.nodeNumber)	//如果节点数量上就多，返回false
		return false;
	else
	{
		int count=0;
		for(int i=0;i<nodeNumber;i++)
			for(int j=0;j<g.nodeNumber;j++)
				if(nodes[i].ID==g.nodes[j].ID)
					count++;
		if(count==nodeNumber)	//如果所有节点均在g的节点之内则返回true
			return true;
		else
			return false;
	}
}

//移除节点，还有其关系
void Graph::RemoveNode(int index)
{
	//减少权重
	weight=weight/nodes[index].weight;
	//删除关系
	for(int i=0;i<nodes[index].parentID.length;i++)
	{
		RemoveRelationship(index,nodes[index].parentID[i]);
		RemoveRelationship(nodes[index].parentID[i],index);
		//删除该节点的父节点中的父节点的自己
		for(int itr=0;itr<nodes[nodes[index].parentID[i]].parentID.length;itr++)
		{
			if(nodes[nodes[index].parentID[i]].parentID[itr]==index)
			{
				for(int m=itr;m<nodes[nodes[index].parentID[i]].parentID.length-1;m++)
				{
					nodes[nodes[index].parentID[i]].parentID[m]=nodes[nodes[index].parentID[i]].parentID[m+1];				
				}
				nodes[nodes[index].parentID[i]].parentID.length -= 1;
			}
		}
	}
	//删除掉没用的关系行
	for(int i=index;i<nodeNumber;i++)
		for(int j=0;j<nodeNumber;j++)
			nodeMatrix[i][j]=nodeMatrix[i+1][j];
	for(int i=0;i<nodeNumber;i++)
		for(int j=index;j<nodeNumber;j++)
			nodeMatrix[i][j]=nodeMatrix[i][j+1];
	//删除节点，移动后面的节点覆盖它
	for(int i=index;i<nodeNumber;i++)
	{
		nodes[i]=nodes[i+1];
		//对应调整节点编号
		NotifyChangeID(nodes[i],i);
	}
	nodeNumber--;

	//cout<<endl;
	//this->Dump();
	//cout<<endl;
}

//通知父节点该节点号变动
void Graph::NotifyChangeID(GraphNode &n,int id)
{
	for(int i=0;i<n.parentID.length;i++)
	{
		for(int j=0;j<nodes[n.parentID[i]].parentID.length;j++)
		{
			if(nodes[n.parentID[i]].parentID[j]==n.ID)
				nodes[n.parentID[i]].parentID[j]=id;
		}
	}
	n.ID=id;
}

//连线成为三角型
void Graph::MakeTriangle()
{
	//清空关系
	ClearRelationship();
	//两两相连
	for(int i=0;i<nodeNumber;i++)
		for(int j=0;j<nodeNumber;j++)		
			if(i!=j)	//排出自身
				AddRelationship(i,j);
}

//清空关系
void Graph::ClearRelationship()
{
	for(int i=0;i<nodeNumber;i++)
		for(int j=0;j<nodeNumber;j++)
			if(i!=j)
				nodeMatrix[i][j]=0;

	//边数置零
	edgeNumber=0;
}