QPSetup.mesa
Copyright Ó 1990 by Xerox Corporation. All rights reserved.
Ken Shoemake, June 15, 1990 1:58 am PDT
QPSetup: CEDAR DEFINITIONS
= BEGIN
OPEN QPSolve;
ROPE: TYPE ~ Rope.ROPE;
noRow: INT ~ -1;
Graph: TYPE ~ REF GraphRep;
GraphRep: TYPE ~ RECORD [order: INT, nV: NAT, vList: VertexList, eqnList: EqnList];
Vertex: TYPE ~ REF VertexRep;
VertexRep: TYPE ~ RECORD [name: ROPE, visited: INT, tree: Edge, adj: EdgeList, val: REAL ← 0.0, vid: INT];
VertexList: TYPE ~ REF VertexListRep;
VertexListRep: TYPE ~ RECORD [name: ROPE, first: Vertex, rest: VertexList, forward: Skips];
Level: TYPE ~ NAT;
Skips: TYPE ~ REF SkipsRep;
SkipsRep: TYPE ~ RECORD[SEQUENCE level: Level OF VertexList];
Edge: TYPE ~ REF EdgeRep;
EdgeRep: TYPE ~ RECORD [thisEnd, thatEnd: Vertex, eData: EdgeData, dir: REAL ← 1.0];
EdgeList: TYPE ~ LIST OF Edge;
EdgeData: TYPE ~ REF EdgeDataRep;
EdgeDataRep:
TYPE ~
RECORD [
join: Component,
spread: REAL ← 0.0,
squeeze: REAL ← 1.0, -- actually, SqRt[squeeze]
relaxed: REAL ← 0.0,
var: NAT,
val: REAL ← 0.0];
Term: TYPE ~ RECORD [eData: EdgeData, coef: REAL];
TermList: TYPE ~ LIST OF Term;
EqnList: TYPE ~ LIST OF TermList;
Component: TYPE ~ REF ComponentRep;
ComponentRep:
TYPE ~
RECORD [
join: Component,
weight: INT,
edges: EdgeList,
cycleEqns, extraEqns: EqnList];
ComponentList: TYPE ~ LIST OF Component;
FindComponents:
PROC [g: Graph]
RETURNS [compList: ComponentList ←
NIL];
Return list of biconnected components of graph, with necessary cycle equations.
CoupleComponents:
PROC [compList: ComponentList, extraEqns: EqnList]
RETURNS [coupledList: ComponentList];
From list of graph bi-connected components (with cycle equations), and list of constraint equations, create list of coupled components. A coupled component will contain the edges and equations of all components whose edges co-occur as variables in some constraint equation, and will also contain the relevant constraint equations.
FindFreeVars:
PROC [cycleEqns, extraEqns: EqnList, nEqns, nVars:
NAT]
RETURNS [rowOf: IVector];
Return rowOf filled with index of row for free vars, noRow for rest of vars.
Index means little now; just needs to be different from noRow.
SolveComponent:
PROC [component: Component];
Transform component data into QP form and call QPSolve.
SolveGraph:
PROC [g: Graph];
Transform graph into QP form, call QPSolve, propagate positions.
NewGraph: PROC RETURNS [g: Graph];
AcquireVertex: PROC [g: Graph, name: ROPE] RETURNS [v: Vertex];
AcquireEdge: PROC [g: Graph, thisEnd, thatEnd: Vertex] RETURNS [edge: Edge];
SpreadEdge: PROC [g: Graph, edge: Edge, spread: REAL];
SqueezeEdge: PROC [g: Graph, edge: Edge, squeeze: REAL];
RelaxEdge: PROC [g: Graph, edge: Edge, relaxed: REAL];
ConstrainEdges: PROC [g: Graph, termList: TermList];
ListGraph: PROC [g: Graph, full: BOOL ← FALSE] RETURNS [list: LIST OF REF];
ESee: PROC [edge: Edge, full: BOOL ← FALSE] RETURNS [list: LIST OF REF];
ELSee: PROC [edges: EdgeList, full: BOOL ← FALSE] RETURNS [list: LIST OF REF];
ListComp: PROC [comp: Component, full: BOOL ← FALSE] RETURNS [list: LIST OF REF];
END..