Return to dag_simplex.c CVS log

Up to [Research Unix] / researchv10no / cmd / dag

Annotation of researchv10no/cmd/dag/dag_simplex.c, revision 1.1

1.1     ! root        1: #include       "draw_dag.h"
        !             2: 
        !             3: #include       <sys/types.h>
        !             4: #include       <sys/times.h>
        !             5: #define TIC 60
        !             6: 
        !             7: /*
        !             8:        simplex algorithm to solve LP
        !             9: */
        !            10: 
        !            11: static int     Rows, Cols;
        !            12: static long    *Auxf, *Objf, **Arrp;
        !            13: 
        !            14: 
        !            15: static void readresults(int n_elts, int *array)
        !            16: {
        !            17:        for (int i = 0; i < n_elts; i++)
        !            18:        {
        !            19:                int row = -1;
        !            20:                for(int j = 0; j < Rows; j++)
        !            21:                {
        !            22:                        long val = Arrp[j][i];
        !            23:                        if(val != 0)
        !            24:                        {
        !            25:                                if(row >= 0)
        !            26:                                {
        !            27:                                        row = -1;
        !            28:                                        break;
        !            29:                                }
        !            30:                                else if(val != 1)
        !            31:                                        break;
        !            32:                                else    row = j;
        !            33:                        }
        !            34:                }
        !            35:                array[i] = (row >= 0 ? Arrp[row][Cols-1] : 0);
        !            36:        }
        !            37: }
        !            38: 
        !            39: 
        !            40: 
        !            41: static int FindRow (int col)
        !            42: {
        !            43:        long    quot;
        !            44:        int     minrow = -1;
        !            45:        long    minval = Maxint;
        !            46:        register int maxcol = Cols-1;
        !            47: 
        !            48:        for (register int i = 0; i < Rows; i++)
        !            49:        {
        !            50:                if (Arrp[i][col] <= 0)
        !            51:                        continue;
        !            52:                quot = Arrp[i][maxcol];
        !            53:                if (quot < minval)
        !            54:                {
        !            55:                        minrow = i;
        !            56:                        minval = quot;
        !            57:                }
        !            58:        }
        !            59:        return (minrow);
        !            60: }
        !            61: 
        !            62: static int FindCol()
        !            63: {
        !            64:        long    minval = Maxint;
        !            65:        int     mincol = -1;
        !            66:        register int maxcol = Cols-1;
        !            67: 
        !            68:        for (register int i = 0; i < maxcol; i++)
        !            69:        {
        !            70:                if (Auxf[i] < minval)
        !            71:                {
        !            72:                        mincol = i;
        !            73:                        minval = Auxf[i];
        !            74:                }
        !            75:        }
        !            76:        return (mincol);
        !            77: }
        !            78: 
        !            79: static void MergeRows (register long *row1, register long *row2, int col)
        !            80: {
        !            81:        register long fact, *maxrow1 = row1+Cols;
        !            82: 
        !            83:        switch (fact = row1[col])
        !            84:        {
        !            85:        case 0 :
        !            86:                break;
        !            87:        case 1 :
        !            88:                while(row1 < maxrow1)
        !            89:                        *row1++ -= *row2++;
        !            90:                break;
        !            91:        case -1 :
        !            92:                while(row1 < maxrow1)
        !            93:                        *row1++ += *row2++;
        !            94:                break;
        !            95:        default :
        !            96:                while(row1 < maxrow1)
        !            97:                        *row1++ -= (*row2++)*fact;
        !            98:                break;
        !            99:        }
        !           100: }
        !           101: 
        !           102: void dag_simplex(int rows, int cols,
        !           103:        long **arrp, long *auxf, long *objf, int n_elts, int *array)
        !           104: {
        !           105:        struct tms begtm, endtm;
        !           106:        int     col, row;
        !           107:        long    val;
        !           108: 
        !           109:        Rows = rows;
        !           110:        Cols = cols;
        !           111:        Arrp = arrp;
        !           112:        Auxf = auxf;
        !           113:        Objf = objf;
        !           114: 
        !           115:        if(Verbose)
        !           116:        {
        !           117:                fprintf(stderr,"In simplex: rows = %d, Columns = %d\n",Rows,Cols-1);
        !           118:                times(&begtm);
        !           119:        }
        !           120: 
        !           121:        register int maxcol = Cols-1;
        !           122:        for(int cnt = 0;; cnt++)
        !           123:        {
        !           124:                /* Find least coeff. in auxf. */
        !           125:                col = FindCol();
        !           126:                val = Auxf[col];
        !           127:                if (val >= 0)
        !           128:                {
        !           129:                        if (!Objf)
        !           130:                        {
        !           131:                                if (Verbose)
        !           132:                                        fprintf (stderr, "Passes = %d\n",cnt);
        !           133:                                break;
        !           134:                        }
        !           135:                        Auxf = Objf;
        !           136:                        Objf = NULL;
        !           137:                        continue;
        !           138:                }
        !           139: 
        !           140:                row = FindRow(col);
        !           141:                val = Arrp[row][col];
        !           142:                if (val != 1)
        !           143:                        panic("non-unit pivot");
        !           144:                for(register int i = 0; i < Rows; i++)
        !           145:                        if(i != row)
        !           146:                                MergeRows(Arrp[i], Arrp[row], col);
        !           147:                if(Objf != NULL)
        !           148:                        MergeRows(Objf, Arrp[row], col);
        !           149:                MergeRows(Auxf, Arrp[row], col);
        !           150:                for(i = 0; i < Rows; i++)
        !           151:                        if (Arrp[i][maxcol] < 0)
        !           152:                                panic("Non-canonical form\n");
        !           153:        }
        !           154: 
        !           155:        readresults(n_elts,array);
        !           156: 
        !           157:        if(Verbose)
        !           158:        {
        !           159:                times(&endtm);
        !           160:                int total = (endtm.tms_utime-begtm.tms_utime) +
        !           161:                                (endtm.tms_stime-begtm.tms_stime);
        !           162:                int percent = (total - (total/TIC)*TIC)*100/TIC;
        !           163:                fprintf(stderr,"Time in simplex: %d.%02ds\n",
        !           164:                                total/TIC, percent);
        !           165:        }
        !           166: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.