From d18b8150ba16f4a930b213dae1f4fb369cb3d0bf Mon Sep 17 00:00:00 2001
From: Tim Dwyer <tgdwyer@gmail.com>
Date: Fri, 14 Jul 2006 04:09:40 +0000
Subject: - Connectors with end-markers now constrained to point downwards in
 graph layout  - vpsc namespace added to libvpsc

(bzr r1408)
---
 src/libvpsc/solve_VPSC.cpp | 52 +++++++++++++++++++++++-----------------------
 1 file changed, 26 insertions(+), 26 deletions(-)

(limited to 'src/libvpsc/solve_VPSC.cpp')

diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp
index 44918951d..ff0ff96bf 100644
--- a/src/libvpsc/solve_VPSC.cpp
+++ b/src/libvpsc/solve_VPSC.cpp
@@ -19,37 +19,35 @@
 #include <sstream>
 #ifdef RECTANGLE_OVERLAP_LOGGING
 #include <fstream>
-using std::ios;
-using std::ofstream;
-using std::endl;
 #endif
+#include <map>
+
+using namespace std;
 
-using std::ostringstream;
-using std::list;
-using std::set;
+namespace vpsc {
 
 static const double ZERO_UPPERBOUND=-0.0000001;
 
-IncVPSC::IncVPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) 
-	: VPSC(n,vs,m,cs) {
+IncSolver::IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) 
+	: Solver(n,vs,m,cs) {
 	inactive.assign(cs,cs+m);
 	for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) {
 		(*i)->active=false;
 	}
 }
-VPSC::VPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) {
+Solver::Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) {
 	bs=new Blocks(n, vs);
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	printBlocks();
-	assert(!constraintGraphIsCyclic(n,vs));
+	//assert(!constraintGraphIsCyclic(n,vs));
 #endif
 }
-VPSC::~VPSC() {
+Solver::~Solver() {
 	delete bs;
 }
 
 // useful in debugging
-void VPSC::printBlocks() {
+void Solver::printBlocks() {
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
 	for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
@@ -71,7 +69,7 @@ void VPSC::printBlocks() {
 * first) fixing the position of variables inside blocks relative to one
 * another so that constraints internal to the block are satisfied.
 */
-void VPSC::satisfy() {
+void Solver::satisfy() {
 	list<Variable*> *vs=bs->totalOrder();
 	for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) {
 		Variable *v=*i;
@@ -93,7 +91,7 @@ void VPSC::satisfy() {
 	delete vs;
 }
 
-void VPSC::refine() {
+void Solver::refine() {
 	bool solved=false;
 	// Solve shouldn't loop indefinately
 	// ... but just to make sure we limit the number of iterations
@@ -137,12 +135,12 @@ void VPSC::refine() {
  * refinement is possible by splitting the block. This is done repeatedly
  * until no further improvement is possible.
  */
-void VPSC::solve() {
+void Solver::solve() {
 	satisfy();
 	refine();
 }
 
-void IncVPSC::solve() {
+void IncSolver::solve() {
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
 	f<<"solve_inc()..."<<endl;
@@ -171,7 +169,7 @@ void IncVPSC::solve() {
  * over an active constraint between the two variables.  We choose the 
  * constraint with the most negative lagrangian multiplier. 
  */
-void IncVPSC::satisfy() {
+void IncSolver::satisfy() {
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
 	f<<"satisfy_inc()..."<<endl;
@@ -185,6 +183,11 @@ void IncVPSC::satisfy() {
 		if(lb != rb) {
 			lb->merge(rb,v);
 		} else {
+			if(lb->isActiveDirectedPathBetween(v->right,v->left)) {
+				// cycle found, relax the violated, cyclic constraint
+				v->gap = v->slack();
+				continue;
+			}
 			if(splitCtr++>10000) {
 				throw "Cycle Error!";
 			}
@@ -215,7 +218,7 @@ void IncVPSC::satisfy() {
 	printBlocks();
 #endif
 }
-void IncVPSC::moveBlocks() {
+void IncSolver::moveBlocks() {
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
 	f<<"moveBlocks()..."<<endl;
@@ -229,7 +232,7 @@ void IncVPSC::moveBlocks() {
 	f<<"  moved blocks."<<endl;
 #endif
 }
-void IncVPSC::splitBlocks() {
+void IncSolver::splitBlocks() {
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
 #endif
@@ -271,7 +274,7 @@ void IncVPSC::splitBlocks() {
  * Scan constraint list for the most violated constraint, or the first equality
  * constraint
  */
-Constraint* IncVPSC::mostViolated(ConstraintList &l) {
+Constraint* IncSolver::mostViolated(ConstraintList &l) {
 	double minSlack = DBL_MAX;
 	Constraint* v=NULL;
 #ifdef RECTANGLE_OVERLAP_LOGGING
@@ -304,15 +307,12 @@ Constraint* IncVPSC::mostViolated(ConstraintList &l) {
 	return v;
 }
 
-#include <map>
-using std::map;
-using std::vector;
 struct node {
 	set<node*> in;
 	set<node*> out;
 };
 // useful in debugging - cycles would be BAD
-bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
+bool Solver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) {
 	map<Variable*, node*> varmap;
 	vector<node*> graph;
 	for(unsigned i=0;i<n;i++) {
@@ -359,7 +359,7 @@ bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
 }
 
 // useful in debugging - cycles would be BAD
-bool VPSC::blockGraphIsCyclic() {
+bool Solver::blockGraphIsCyclic() {
 	map<Block*, node*> bmap;
 	vector<node*> graph;
 	for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
@@ -414,4 +414,4 @@ bool VPSC::blockGraphIsCyclic() {
 	}
 	return false;
 }
-
+}
-- 
cgit v1.2.3