快速图遍历

引言

在我的最后一个应用中，我需要将一个图分割成两个或多个平衡的深度子图。这是一个运动学链，每一个不对称意味着需要多乘两个矩阵。所以我一直在寻找能够做到这一点的算法，但找到的任何算法都无法直接应用于我的情况，除非付出巨大的适配工作量。因此，我开发了一种新的算法，它几乎适用于所有问题（分割、最短路径等），并且能在线性时间内完成。我将其称为“湖中石子的算法”。如果我理解正确的话，它将一个NP-hard问题简化为线性问题。（我不是信息论专家……但这个算法确实有效……非常有效）

Using the Code

它非常简单。我们不是沿着路径移动，而是沿着节点的半径移动。这就是我将其称为湖中石子的原因。它的工作原理就像从石子激起的波纹一样。为了保存我们在前进过程中遇到的所有节点，我们需要构建一个合适的数据结构：一棵树。但我们不是用同一棵树来构建，而是使用另一种数据结构，即指向树的最后一层叶子节点的指针数组。在每次碰撞时，我们进行相应的考虑。例如：如果我们正在搜索最短路径，我们将修剪掉最长的路径。如果我们试图分割图，我们将节点分配到树的左分支而不是右分支，依此类推。

//
// Let us create our graph:
struct graph{
    unsigned index;
    relation* *relations;
    unsigned relations_count;
    char isflaged;
    void *mydata;
}
struct relation
{
    unsigned index;
    struct graph*node;
    void *otherdata;
    relation*counterrelation;
}

这是我们的图，我们假设你已经在某个地方存储了你的图的数组。我们的求解器将如下所示

// Let us create our solver: 
struct tree_solver{ 
	struct graph*node; 
	unsigned n;//relations count departing from here except the parent
	unsigned buffer;//it is going to create an amount of slots 
	//enough to contain all the relations, except the parent, but 
	//due our pruning criteria, it can be bigger than the effective count of leafs 
	struct tree_solver**leafs;
	struct tree_solver*parent;
	 //struct tree_solver *last_hub; if you want pruning efficiently
	 double my_comparedata; //the count, the depth, whatever you want
	char stop;
}

struct tree_solver * new_leaf(struct tree_solver *parent, struct graph *node)
{
	struct tree_solver *ts=(struct tree_solver *)malloc(sizeof(struct tree_solver));
       	ts->node=node;
	ts->stop=0;
	ts->n=0;
	ts->buffer=node->relations_count-1;
	ts->parent=parent;
	ts->leafs=(struct tree_solver*)calloc(ts->buffer;sizeof(struct tree_solver);
	ts->my_comparadata+=parent?parent->my_comparedata:0;//some operation here
}

int next_row(struct tree_solver **reg, unsigned *reg_count)
{
	unsigned rcount=*reg_count; //is better to save in another variable 
	//because reg_count is going to increase in this function
	//and some branches are going faster than others
	int i,j,second,res;
	struct tree_solver *temp;
	for(i=0;i < rcount;i++)
	{
		second=0;
		res=0;
		temp=reg[i];
		if(reg[i]->stop) continue;
		if(reg[i]->node->isflaged) 
		// do whatever you want here.
		//in my case I switch reg[i] to stop;
		//If comes here, you are sure it is an recent collision
		for (j=0;j < temp->node->relations_count;j++)
			if (temp->node->relations[j]
			->node!=temp->parent->node) // I avoid to get back to  my parent
			{
				temp->leafs[temp->n]=new_leaf(temp,temp->node->relations[j]);
				if (second)
					reg[(*reg_count)++]=temp->leafs[temp->n++];
				else
				{
					reg[i]=temp->leafs[temp->n++];
					second=1;
					res=1;		
				}	
			}  	
	}
}

struct tree_solver * travers(struct graph *root)
{
	 unsgigned reg_count=0;
	 struct tree_solver *ts=new_leaf(NULL, root);
	//supposed you have some where an node_count declared, 
        //we are going to create an array of pointers
	// to the last leafs. The worst scenario is exactly node_count big, 
        //an full flat graph. For small 
	// graphs we can assume it as size. For bigger ones, may be you create a buffer, 
        // reallocate and so on 
	 struct tree_solver **reg=(struct tree_solver **)malloc(sizeof(struct tree_solver*) *node_count);
	reg[0]=ts;reg_count++;
	while(next_row(reg,& reg_count) 
		;
	return ts;
}

就这样。经过几个步骤后，你就可以遍历整个图。

历史

这是一个漫长的故事……