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.
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:
struct tree_solver{
struct graph*node;
unsigned n; unsigned buffer; struct tree_solver**leafs;
struct tree_solver*parent;
double my_comparedata; 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;}
int next_row(struct tree_solver **reg, unsigned *reg_count)
{
unsigned rcount=*reg_count; 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)
for (j=0;j < temp->node->relations_count;j++)
if (temp->node->relations[j]
->node!=temp->parent->node) {
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);
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...