main.cpp

计算ldpc低密度奇偶校验矩阵中4环的个数。

#include<iostream> 
#include<fstream>
#include <vector>

using namespace std;

struct Node
{
	vector<int> next;
};

typedef vector<Node> Nodevector;

void main(void)
{
	int n,k,i,j,p,degree,num,overlap,count;
	Node node;
	vector<int> rowdegree,coldegree;
	Nodevector row,col;
	bool FindNode(vector<int>&node,int target);
	ifstream infile("checkmatrix.dat");

	infile>>n;
	infile>>k;

	for(i=0;i<n-k;i++)
	{
		infile>>degree;
		rowdegree.push_back(degree);
	}

	for(i=0;i<n;i++)
	{
		infile>>degree;
		coldegree.push_back(degree);
	}

	for(i=0;i<n-k;i++)
	{
		row.push_back(node);
		for(j=0;j<rowdegree[i];j++)
		{
			infile>>num;
			row[i].next.push_back(num);
		}
	}

	for(i=0;i<n;i++)
	{
		col.push_back(node);
		for(j=0;j<coldegree[i];j++)
		{
			infile>>num;
			col[i].next.push_back(num);
		}
	}

	cout<<"读入完毕!"<<endl;

/*	for(i=0;i<row.size();i++)
	{
		for(j=0;j<row[i].next.size();j++)
		{
			if(!FindNode(col[row[i].next[j]].next,i))
			{
				cout<<"col "<<row[i].next[j]<<" doesn't connect with row "<<i<<endl;
				cout<<"bad list!"<<endl;
				return;
			}
		}
	}
	cout<<"good list!"<<endl;
*/
	count=0;
	for(i=0;i<row.size();i++)
	{
		for(p=i+1;p<row.size();p++)
		{
		    overlap=0;
	    	for(j=0;j<row[i].next.size();j++)
			{
	    		if(FindNode(row[p].next,row[i].next[j]))
				{
					overlap++;
				}
			}
			if(overlap>1)
			{
				cout<<i<<" 与 "<<p<<" 存在4环!"<<endl;
				count++;
			}
		}
	}
	cout<<"共存在 "<<count<<" 个4环!"<<endl;
	return;
}


bool FindNode(vector<int>&node,int target)
{
    if(node.empty())
		return false;

	for(size_t i = 0; i < node.size(); i++)
	{
		if(node[i] == target)
		{
			return true;
		}
	}
	return false;	
}