/* Copyright (c) AT&T Corp. All rights reserved. This software may only be used by you under license from AT&T Corp. ("AT&T"). A copy of AT&T's Source Code Agreement is available at AT&T's Internet website having the URL http://www.research.att.com/sw/tools/graphviz/license/ If you received this software without first entering into a license with AT&T, you have an infringing copy of this software and cannot use it without violating AT&T's intellectual property rights. */ // Sanity checks. #include "dynadag/DynaDAG.h" namespace DynaDAG { void FlexiRanks::Check() { iterator ri = begin(), next; if(ri==end()) return; (next=ri)++; while(next!=end()) { index a = IndexOfIter(ri), b = IndexOfIter(next); assert(Above(a,b)); ri = next++; } } void ConseqRanks::Check() { } void Config::checkEdges(bool strict) { for(DDModel::graphedge_iter ei = model.edges().begin(); ei!=model.edges().end(); ++ei) { DDModel::Node *t = (*ei)->tail, *h = (*ei)->head; // edges must be path parts or node parts; edges must belong to one node only assert(DDd(*ei).amEdgePart() || DDd(t).amNodePart() && DDd(t).multi==DDd(h).multi); Ranks::index tr = DDd(t).rank, hr = DDd(h).rank; if(strict) // all edges span one rank assert(ranking.Down(tr)==hr); else assert(ranking.Above(tr,hr)); } // nodes in paths belong to one path only for(DDModel::node_iter ni = model.nodes().begin(); ni!=model.nodes().end(); ++ni) { DDModel::Node *n = *ni; if(DDd(n).amEdgePart()) { assert(n->ins().size()==1); assert(n->outs().size()==1); DDModel::Edge *e1 = *n->ins().begin(), *e2 = *n->outs().begin(); assert(DDd(e1).path==DDd(e2).path); } } // view edges' paths connect the tops & bottoms of nodes for(Layout::graphedge_iter ei2 = current->edges().begin(); ei2!=current->edges().end(); ++ei2) { DDPath *path = DDp(*ei2); DDMultiNode *n1 = DDp((*ei2)->tail), *n2 = DDp((*ei2)->head); if(path->first) assert(path->first->tail==n1->bottom()&&path->last->head==n2->top() ||path->first->tail==n2->bottom()&&path->last->head==n1->top()); } } void Config::checkX() { for(Ranks::iterator ri = ranking.begin(); ri!=ranking.end(); ++ri) { Rank *r = *ri; for(NodeV::iterator ni = r->order.begin(); ni!=r->order.end(); ++ni) if(ni!=r->order.begin()) #ifdef X_STRICTLY_INCREASING assert(DDd(*ni).cur.x>DDd(*(ni-1)).cur.x); #else assert(DDd(*ni).cur.x>=DDd(*(ni-1)).cur.x); #endif } } void XSolver::checkLRConstraints() { bool missing = false; for(Config::Ranks::iterator ri = config.ranking.begin(); ri!=config.ranking.end(); ++ri) { Rank *r = *ri; for(NodeV::iterator ni = r->order.begin(); ni!=r->order.end(); ++ni) if(DDModel::Node *left = config.Left(*ni)) { DDCGraph::Node *l = DDd(left).getXcon().n, *n = DDd(*ni).getXcon().n; assert(l&&n); DDCGraph::Edge *e = cg.find_edge(l,n); if(!e) { report(r_error,"constraint missing between %x (%s %x) and %x (%s %x)\n", left,type(left),thing(left),*ni,type(*ni),thing(*ni)); missing = true; } else assert(DDNS::NSd(e).minlen >= ROUND(xScale*config.UVSep(left,*ni))); /* // (hopeless) // don't allow extraneous constraints: only edge,stab, and L-R are good for(DDCGraph::edge_iter ei = n->ins().begin(); ei!=n->ins().end(); ++ei) { DDCGraph::Edge *e2 = *ei; assert(e2==e || e2->tail == DDd(*ni).getXcon().stab || gd<ConstraintType>(e2->tail).why==ConstraintType::orderEdgeStraighten); } */ } } assert(!missing); } void XSolver::checkEdgeConstraints() { for(DDModel::graphedge_iter ei = config.model.edges().begin(); ei!=config.model.edges().end(); ++ei) if(DDd(*ei).amEdgePart()) { DDCGraph::Node *cn = DDd(*ei).cn; assert(cn); assert(cn->ins().size()==0); if(cn->outs().size()!=2) { report(r_error,"AARGH! Why isn't node %p of %s %p constrained with\n", (*ei)->tail,DDd((*ei)->tail).amEdgePart()?"path":"multinode",thing((*ei)->tail)); report(r_error,"node %p of %s %p????\n",(*ei)->head,DDd((*ei)->head).amEdgePart()? "path":"multinode",thing((*ei)->head)); throw InternalErrorException(); } } } void Ranker::checkStrongConstraints(ChangeQueue &changeQ) { for(Layout::graphedge_iter ei = config.current->edges().begin(); ei!=config.current->edges().end(); ++ei) { DDCGraph::Edge *strong = DDp(*ei)->strong; if(strong) assert(DDNS::NSd(strong).minlen==rankLength(*ei)); } } /* void DynaDAG::checkAll(ddview_t *view) { config.CheckRanks(); int r; for(r = view->config->low; r <= view->config->high; r++) dd_check_rank(view,r); dd_check_edges(view->layout); } void Config::CheckRanks() { for(int i = low; i<high; ++i) { Rank *r = GetRank(i); r->check(i); } for(RankV::iterator ri = ranking.begin(); ri!=ranking.end(); ++ri) (*ri)->check(); } void Rank::check(int r) { Agnode_t *ln,*rn,**list; int i; rank_t *rd; DDModel::Node *ln=0; for(NodeV::iterator ni = order.begin(); ni!=order.end(); ++ni) { assert(DDd(*ni).inConfig); assert(DDd(*ni).rank == r); dd_check_elts(*ni); if(ln) { assert(DDd(ln).order + 1 == DDd(*ni).order); assert(DDd(ln).cur.x + BASE(view)->client->separation.x <= dd_pos(rn).x); } ln = rn; } assert (i == rd->n); } void dd_check_containment(ddview_t *view, int r, Agnode_t *n, int must_be_in) { Agnode_t *rn; for(rn = dd_leftmost(view,r); rn; rn = dd_right(view,rn)) { if(must_be_in) { if(n == rn) break; } else assert (n != rn); } if(must_be_in) assert (n == rn); } ilbool dd_check_pathnode(ddview_t *view, Agnode_t *n) { rank_t *rd; int i,r; i = dd_order(n); r = dd_rank(n); rd = dd_rankd(view,r); assert(rd->v[i] == n); return FALSE; } void dd_check_vnode_path(ddview_t *view, Agedge_t **vpath) { int i; Agedge_t *e,*f; f = NILedge; for(i = 0; (e = vpath[i]); i++) { dd_check_pathnode(view,agtail(e)); if(i > 0) assert(dd_is_a_vnode(agtail(e))); f = e; } dd_check_pathnode(view,aghead(f)); } void dd_check_elts(ddview_t *view, Agnode_t *n) { Agedge_t *e,*f,*fst,*lst; if(dd_is_a_vnode(n)) return; for(e = agfstout(n); e; e = agnxtout(e)) { fst = dd_first_elt(e); lst = dd_last_elt(e); for(f = fst; f; f = agfstout(aghead(f))) { dd_check_pathnode(view,aghead(f)); if(f == lst) break; } } } void dd_check_newranks(Agraph_t *g) { Agnode_t *n; Agedge_t *e; for(n = agfstnode(g); n; n = agnxtnode(n)) { if(dd_is_a_vnode(n)) continue; for(e = agfstout(n); e; e = agnxtout(e)) { if(NOT(dd_constraint(e))) continue; assert (dd_newrank(dd_pathhead(e)) - dd_newrank(dd_pathtail(e)) >= 1); } } } static void check_mg(Agraph_t *g, Agraph_t *root) { Agnode_t *mn; Agedge_t *me; for(mn = agfstnode(g); mn; mn = agnxtnode(mn)) { assert(mn->base.data); assert(agsubnode(root,mn,FALSE)); for(me = agfstout(mn); me; me = agnxtout(me)) { assert(me->base.data); assert(agsubedge(root,me,FALSE)); } } } void dd_check_model(ddview_t *view) { Agraph_t *root; root = BASE(view)->model.main; check_mg(root,root); check_mg(BASE(view)->model.v[IL_INS],root); check_mg(BASE(view)->model.e[IL_INS],root); check_mg(BASE(view)->model.v[IL_MOD],root); check_mg(BASE(view)->model.e[IL_MOD],root); check_mg(BASE(view)->model.v[IL_DEL],root); check_mg(BASE(view)->model.e[IL_DEL],root); } void dd_check_really_gone(Agraph_t *g, Agnode_t *n, ulong id) { Agnode_t *u; Agedge_t *e; assert (agidnode(g,id,FALSE) == NILnode); for(u = agfstnode(g); u; u = agnxtnode(u)) { assert(u != n); for(e = agfstedge(u); e; e = agnxtedge(e,u)) assert(e->node != n); } } void dd_check_vnodes(ddview_t *view) { Agnode_t *n; Agedge_t *e; for(n = agfstnode(view->layout); n; n = agnxtnode(n)) { if(NOT(dd_is_a_vnode(n))) continue; e = agfstin(n); if(e == NILedge) abort(); e = agfstout(n); if(e == NILedge) abort(); } } static int CLcnt = 0; void dd_check_links(ddview_t *view) { Agraph_t *model, *layout; Agnode_t *mn, *ln; Agedge_t *me, *le, *mme; ddpath_t *path; dd_check_model(view); model = BASE(view)->model.main; layout = view->layout; for(mn = agfstnode(model); mn; mn = agnxtnode(mn)) { ln = dd_rep(mn); if(ln == NILnode) continue; assert(dd_node(ln)->model == mn); for(me = agfstedge(mn); me; me = agnxtedge(me,mn)) { path = dd_pathrep(me); mme = path->model; if(mme == NILedge) continue; assert((mme == me) || (mme == AGOPP(me))); } } for(ln = agfstnode(layout); ln; ln = agnxtnode(ln)) { if(dd_is_a_vnode(ln) == FALSE) { mn = dd_node(ln)->model; assert(mn); assert(agsubnode(model,mn,FALSE) == mn); assert(ln == dd_rep(mn)); for(le = agfstedge(ln); le; le = agnxtedge(le,ln)) { path = dd_edge(le)->path; me = path->model; assert(agsubedge(model,me,FALSE) == me); } } else { assert(agfstin(ln) != NILedge); assert(agfstout(ln) != NILedge); } } CLcnt++; } */ }