symbfct.c

斯坦福大学Grant和Boyd教授等开发的凸优化matlab工具箱

    return 0;
} /* etree_ */

/* *********************************************************************** */
/* *********************************************************************** */

/*   Version:        0.3 */
/*   Last modified:  December 27, 1994 */
/*   Authors:        Joseph W.H. Liu */

/*   Mathematical Sciences Section, Oak Ridge National Laboratory */

/* *********************************************************************** */
/* *********************************************************************** */
/* ******     BETREE ..... BINARY TREE REPRESENTATION OF ETREE     ******* */
/* *********************************************************************** */
/* *********************************************************************** */

/*   WRITTEN BY JOSEPH LIU (JUL 17, 1985) */

/*   PURPOSE: */
/*       TO DETERMINE THE BINARY TREE REPRESENTATION OF THE ELIMINATION */
/*       TREE GIVEN BY THE PARENT VECTOR.  THE RETURNED REPRESENTATION */
/*       WILL BE GIVEN BY THE FIRST-SON AND BROTHER VECTORS.  THE ROOT */
/*       OF THE BINARY TREE IS ALWAYS NEQNS. */

/*   INPUT PARAMETERS: */
/*       NEQNS           -   NUMBER OF EQUATIONS. */
/*       PARENT          -   THE PARENT VECTOR OF THE ELIMINATION TREE. */
/*                           IT IS ASSUMED THAT PARENT(I) > I EXCEPT OF */
/*                           THE ROOTS. */

/*   OUTPUT PARAMETERS: */
/*       FSON            -   THE FIRST SON VECTOR. */
/*       BROTHR          -   THE BROTHER VECTOR. */

/* *********************************************************************** */

/* Subroutine */ int betree_(neqns, parent, fson, brothr)
integer *neqns, *parent, *fson, *brothr;
{
    /* System generated locals */
    integer i__1;

    /* Local variables */
    static integer node, ndpar, lroot;


/* ***********************************************************************
 */



/* ***********************************************************************
 */


/* ***********************************************************************
 */

    /* Parameter adjustments */
    --brothr;
    --fson;
    --parent;

    /* Function Body */
    if (*neqns <= 0) {
	return 0;
    }

    i__1 = *neqns;
    for (node = 1; node <= i__1; ++node) {
	fson[node] = 0;
	brothr[node] = 0;
/* L100: */
    }
    lroot = *neqns;
/*       ------------------------------------------------------------ */
/*       FOR EACH NODE := NEQNS-1 STEP -1 DOWNTO 1, DO THE FOLLOWING. */
/*       ------------------------------------------------------------ */
    if (*neqns <= 1) {
	return 0;
    }
    for (node = *neqns - 1; node >= 1; --node) {
	ndpar = parent[node];
	if (ndpar <= 0 || ndpar == node) {
/*               -------------------------------------------------
 */
/*               NODE HAS NO PARENT.  GIVEN STRUCTURE IS A FOREST.
 */
/*               SET NODE TO BE ONE OF THE ROOTS OF THE TREES. */
/*               -------------------------------------------------
 */
	    brothr[lroot] = node;
	    lroot = node;
	} else {
/*               ------------------------------------------- */
/*               OTHERWISE, BECOMES FIRST SON OF ITS PARENT. */
/*               ------------------------------------------- */
	    brothr[node] = fson[ndpar];
	    fson[ndpar] = node;
	}
/* L300: */
    }
    brothr[lroot] = 0;

    return 0;
} /* betree_ */

/* *********************************************************************** */
/* *********************************************************************** */

/*   Version:        0.3 */
/*   Last modified:  December 27, 1994 */
/*   Authors:        Joseph W.H. Liu */

/*   Mathematical Sciences Section, Oak Ridge National Laboratory */

/* *********************************************************************** */
/* *********************************************************************** */
/* ***************     ETPOST ..... ETREE POSTORDERING     *************** */
/* *********************************************************************** */
/* *********************************************************************** */

/*   WRITTEN BY JOSEPH LIU (SEPT 17, 1986) */

/*   PURPOSE: */
/*       BASED ON THE BINARY REPRESENTATION (FIRST-SON,BROTHER) OF */
/*       THE ELIMINATION TREE, A POSTORDERING IS DETERMINED. THE */
/*       CORRESPONDING PARENT VECTOR IS ALSO MODIFIED TO REFLECT */
/*       THE REORDERING. */

/*   INPUT PARAMETERS: */
/*       ROOT            -   ROOT OF THE ELIMINATION TREE (USUALLY IT */
/*                           IS NEQNS). */
/*       FSON            -   THE FIRST SON VECTOR. */
/*       BROTHR          -   THE BROTHR VECTOR. */

/*   UPDATED PARAMETERS: */
/*       PARENT          -   THE PARENT VECTOR. */

/*   OUTPUT PARAMETERS: */
/*       INVPOS          -   INVERSE PERMUTATION FOR THE POSTORDERING. */

/*   WORKING PARAMETERS: */
/*       STACK           -   THE STACK FOR POSTORDER TRAVERSAL OF THE */
/*                           TREE. */

/* *********************************************************************** */

/* Subroutine */ int etpost_(root, fson, brothr, invpos, parent, stack)
integer *root, *fson, *brothr, *invpos, *parent, *stack;
{
    /* System generated locals */
    integer i__1;

    /* Local variables */
    static integer node, itop, ndpar, nunode, num;


/* ***********************************************************************
 */



/* ***********************************************************************
 */


/* ***********************************************************************
 */

    /* Parameter adjustments */
    --stack;
    --parent;
    --invpos;
    --brothr;
    --fson;

    /* Function Body */
    num = 0;
    itop = 0;
    node = *root;
/*       ------------------------------------------------------------- */
/*       TRAVERSE ALONG THE FIRST SONS POINTER AND PUSH THE TREE NODES */
/*       ALONG THE TRAVERSAL INTO THE STACK. */
/*       ------------------------------------------------------------- */
L100:
    ++itop;
    stack[itop] = node;
    node = fson[node];
    if (node > 0) {
	goto L100;
    }
/*           ---------------------------------------------------------- */
/*           IF POSSIBLE, POP A TREE NODE FROM THE STACK AND NUMBER IT. */
/*           ---------------------------------------------------------- */
L200:
    if (itop <= 0) {
	goto L300;
    }
    node = stack[itop];
    --itop;
    ++num;
    invpos[node] = num;
/*               ---------------------------------------------------- */
/*               THEN, TRAVERSE TO ITS YOUNGER BROTHER IF IT HAS ONE. */
/*               ---------------------------------------------------- */
    node = brothr[node];
    if (node <= 0) {
	goto L200;
    }
    goto L100;

L300:
/*       ------------------------------------------------------------ */
/*       DETERMINE THE NEW PARENT VECTOR OF THE POSTORDERING.  BROTHR */
/*       IS USED TEMPORARILY FOR THE NEW PARENT VECTOR. */
/*       ------------------------------------------------------------ */
    i__1 = num;
    for (node = 1; node <= i__1; ++node) {
	nunode = invpos[node];
	ndpar = parent[node];
	if (ndpar > 0) {
	    ndpar = invpos[ndpar];
	}
	brothr[nunode] = ndpar;
/* L400: */
    }

    i__1 = num;
    for (nunode = 1; nunode <= i__1; ++nunode) {
	parent[nunode] = brothr[nunode];
/* L500: */
    }

    return 0;
} /* etpost_ */

/* *********************************************************************** */
/* *********************************************************************** */

/*   Version:        0.3 */
/*   Last modified:  December 27, 1994 */
/*   Authors:        Joseph W.H. Liu */

/*   Mathematical Sciences Section, Oak Ridge National Laboratory */

/* *********************************************************************** */
/* *********************************************************************** */
/* ***********     INVINV ..... CONCATENATION OF TWO INVP     ************ */
/* *********************************************************************** */
/* *********************************************************************** */

/*   WRITTEN BY JOSEPH LIU (JUL 17, 1985) */

/*   PURPOSE: */
/*       TO PERFORM THE MAPPING OF */
/*           ORIGINAL-INVP --> INTERMEDIATE-INVP --> NEW INVP */
/*       AND THE RESULTING ORDERING REPLACES INVP.  THE NEW PERMUTATION */
/*       VECTOR PERM IS ALSO COMPUTED. */

/*   INPUT PARAMETERS: */
/*       NEQNS           -   NUMBER OF EQUATIONS. */
/*       INVP2           -   THE SECOND INVERSE PERMUTATION VECTOR. */

/*   UPDATED PARAMETERS: */
/*       INVP            -   THE FIRST INVERSE PERMUTATION VECTOR.  ON */
/*                           OUTPUT, IT CONTAINS THE NEW INVERSE */
/*                           PERMUTATION. */

/*   OUTPUT PARAMETER: */
/*       PERM            -   NEW PERMUTATION VECTOR (CAN BE THE SAME AS */
/*                           INVP2). */

/* *********************************************************************** */

/* Subroutine */ int invinv_(neqns, invp, invp2, perm)
integer *neqns, *invp, *invp2, *perm;
{
    /* System generated locals */
    integer i__1;

    /* Local variables */
    static integer node, i__, interm;


/* ***********************************************************************
 */



/* ***********************************************************************
 */


/* ***********************************************************************
 */

    /* Parameter adjustments */
    --perm;
    --invp2;
    --invp;

    /* Function Body */
    i__1 = *neqns;
    for (i__ = 1; i__ <= i__1; ++i__) {
	interm = invp[i__];
	invp[i__] = invp2[interm];
/* L100: */
    }

    i__1 = *neqns;
    for (i__ = 1; i__ <= i__1; ++i__) {
	node = invp[i__];
	perm[node] = i__;
/* L200: */
    }

    return 0;
} /* invinv_ */

/* *********************************************************************** */
/* *********************************************************************** */

/*   Version:        0.3 */
/*   Last modified:  December 27, 1994 */
/*   Authors:        Esmond G. Ng and Barry W. Peyton */

/*   Mathematical Sciences Section, Oak Ridge National Laboratory */

/* *********************************************************************** */
/* *********************************************************************** */
/* **********     CHORDR ..... CHILD REORDERING                *********** */
/* *********************************************************************** */
/* *********************************************************************** */

/*   PURPOSE: */
/*       REARRANGE THE CHILDREN OF EACH VERTEX SO THAT THE LAST ONE */
/*       MAXIMIZES (AMONG THE CHILDREN) THE NUMBER OF NONZEROS IN THE */
/*       CORRESPONDING COLUMN OF L.  ALSO DETERMINE AN NEW POSTORDERING */
/*       BASED ON THE STRUCTURE OF THE MODIFIED ELIMINATION TREE. */

/*   INPUT PARAMETERS: */
/*       NEQNS           -   NUMBER OF EQUATIONS. */
/*       (XADJ,ADJNCY)   -   THE ADJACENCY STRUCTURE. */

/*   UPDATED PARAMETERS: */
/*       (PERM,INVP)     -   ON INPUT, THE GIVEN PERM AND INVERSE PERM */
/*                           VECTORS.  ON OUTPUT, THE NEW PERM AND */
/*                           INVERSE PERM VECTORS OF THE NEW */
/*                           POSTORDERING. */
/*       COLCNT          -   COLUMN COUNTS IN L UNDER INITIAL ORDERING; */
/*                           MODIFIED TO REFLECT THE NEW ORDERING. */

/*   OUTPUT PARAMETERS: */
/*       PARENT          -   THE PARENT VECTOR OF THE ELIMINATION TREE */
/*                           ASSOCIATED WITH THE NEW ORDERING. */

/*   WORKING PARAMETERS: */
/*       FSON            -   THE FIRST SON VECTOR. */
/*       BROTHR          -   THE BROTHER VECTOR. */
/*       INVPOS          -   THE INVERSE PERM VECTOR FOR THE */
/*                           POSTORDERING. */

/*   PROGRAM SUBROUTINES: */
/*       BTREE2, EPOST2, INVINV. */

/* *********************************************************************** */

/* Subroutine */ int chordr_(neqns, xadj, adjncy, perm, invp, colcnt, parent, 
	fson, brothr, invpos)
integer *neqns, *xadj, *adjncy, *perm, *invp, *colcnt, *parent, *fson, *
	brothr, *invpos;
{
    extern /* Subroutine */ int btree2_(), epost2_(), invinv_();


/* ***********************************************************************
 */



/* ***********************************************************************
 */

/*       ---------------------------------------------------------- */