Fast Graph Traversal

Introduction

In my last application, I had to divide  a graph in two or more balanced depth subgraphs. It is a kinematics chain, and each unsimmetry means two matrix more to multiply. So I was searching for an algorithm that did it but none of what I found could help me, if not with huge effort to adapt at my case. So I developed a new algorithmus, that works with almost all the problems (divide, shortest path and so on) in linear time. I would call it "algorithmus of stone in lake". And if I did right understand reduce a NP-hard problem to linear problem. (I am not a informatic theoretic... but this algorithm works... very well)

Using the Code

It is quite easy. Instead of moving along a path, we move along the radius of the node. This is the reason I called it stone in lake. It works exactly like the wave generated from a stone. To hold all the nodes that we meet in our way, we build a properly data structure: a tree. But we build it not with the same tree, but with another data structure an array of pointers to the leafs of the last level of the tree. At each collision, we make our consideration. Example: If we are searching for the shortest path, we are going to prune the longest way. If we are trying to divide the graph, we assign the node to the left rather the right branch of tree and so on.

//
// 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;
}

This is our graph , we assume you hold an array somewhere where you store you graph. Our solver is going to look like:

// 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;
}

That is all. After a few steps, you traverse the whole graph.

History

It is a long history...