#include "d:\scilab-4.0\routines\stack-c.h"
void bet __PARAMS((int *a, int m, int n, double *b));

int intbet(fname) 
char *fname;
{
    static int l1, m1, n1, l2,m2;
    static int minlhs=0, maxlhs=1, minrhs=1, maxrhs=1;   //why the minlhs must equal zero??
    static int tmp1,tmp2,tmp3;
    static int m3,n3,m4,n4;

    CheckRhs(minrhs,maxrhs) ;
    CheckLhs(minlhs,maxlhs) ;

    GetRhsVar(1, "i", &m1, &n1, &l1);   //the following sentence must be wrote together!!!! 
    m2=1;
    CreateVar(2, "d", &m2, &m1, &l2);  
    bet(istk(l1), m1, n1, stk(l2));
    /*  Return C (3)  */
    LhsVar(1) = 2;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int s;    // The source
int fur;  // The maximal distance from the source
int **d;  // The array d[h] denotes the set of nodes with distance h from the source
int **g;  // Graph
double *bn; // The node betweenness
double *tn; // The node betweenness for a certain source 
double *w;  // The weight of node 
int *dis;  // The distance from the source
int *que;  // The queue for breadth-first search
int *temp; // The temp queue for breadth-first search
int N;

void Get_Dis() 
{
    int i,j,k,step;

    for (i=0;i<N;i++) {
        dis[i]=-1;
        d[i][0]=0;
    }

    dis[s]=0;
    que[0]=1;
    que[1]=s;
    d[0][0]=1;
    d[0][1]=s;
    k=N-1;
    step=0;

    while (k>0) {
        temp[0]=0;
        step++;
        for (i=1;i<=que[0];i++) {
            for (j=1;j<=g[que[i]][0];j++)
                if (dis[g[que[i]][j]]==-1) {
                    dis[g[que[i]][j]]=step;
                    k--;
                    temp[0]++;
                    temp[temp[0]]=g[que[i]][j];
                }
        }
        for (i=0;i<=temp[0];i++) {
            que[i]=temp[i];
            d[step][i]=temp[i];
        }
    }
    fur=step;
//	sciprint("fur=%i \n",fur);	
    return;
}

void Get_Weight()
{
    int i,j,k,l;
    for (i=0;i<N;i++)
        w[i]=0.0;
    w[s]=1.0;
    for (k=1;k<=fur;k++) {
        for (i=1;i<=d[k][0];i++) {
            j=d[k][i];
            for (l=1;l<=g[j][0];l++) {
                if (dis[g[j][l]]==k-1)
                    w[j]+=w[g[j][l]];
            }
        }
    }
    return;
}


void Get_Bnode()
{
    int i,j,k,l;
    double add;
    for (i=0;i<N;i++)
        tn[i]=1.0;
    Get_Weight();
    for (k=fur;k>1;k--) {
        for (i=1;i<=d[k][0];i++) {
            j=d[k][i];

            for (l=1;l<=g[j][0];l++) {
                if (dis[g[j][l]]==k-1) {
                    if (w[j]!=0) {
                        add=tn[j]*w[g[j][l]]/w[j];
                        tn[g[j][l]]+=add;
//						sciprint("add=%e \n",add);
                    }
                }

            }


        }
    }
    for (i=0;i<N;i++)
        bn[i]+=tn[i];
    bn[s]-=1.0;
    return;
}

void freeall()
{
    free(d);
    free(temp);
    free(dis);
    free(que);
    free(bn);
    free(tn);
    free(w);
    free(g);
}

//#define A(i,k) a[i+(*n)*k]

void bet(a,m,n,c)
int a[];
double c[];
int m,n;
{

    int i,j;
    int node_num;
    node_num=m;
    N=m;
    /////////////////////////////////////////////////
    d=malloc(node_num*sizeof(int *));
    for (i=0;i<node_num;i++)
        d[i]=malloc(600*sizeof(int));   //generate d[N][600]
    ////////////////////////////////////////////////////

    /////////////////////////////////////////////////
    g=malloc(node_num*sizeof(int *));
    for (i=0;i<node_num;i++)
        g[i]=malloc(600*sizeof(int));   //generate g[N][600]
    ////////////////////////////////////////////////////

    dis=(int *) malloc(node_num * sizeof(int));
    temp=(int *) malloc(node_num * sizeof(int));
    que=(int *) malloc(node_num * sizeof(int));
    bn=(double *)malloc(node_num * sizeof(double));
    tn=(double *)malloc(node_num * sizeof(double));
    w=(double *)malloc(node_num* sizeof(double));

    for (i=0;i<node_num;i++) {
        bn[i]=0.0;
        for (j=0;j<=a[i];j++) {
            g[i][j]=a[i+j*node_num];

        }

    }  


    for (s=0;s<node_num;s++) {
        if (s%100==0)
            sciprint("%i\t",s);
        Get_Dis();
        Get_Bnode();

    }


    for (i=0;i<node_num;i++) {
        c[i]=bn[i];
        //     sciprint("%i %d \n",g[i][0],bn[i]);
    }

    freeall();


}