src/graphlayout/graphlayout.cpp

   1 /** \file
   2  * Interface between Inkscape code (SPItem) and graphlayout functions.
   3  */
   4 /*
   5 * Authors:
   6 *   Tim Dwyer <tgdwyer@gmail.com>
   7 *
   8 * Copyright (C) 2005 Authors
   9 *
  10 * Released under GNU GPL.  Read the file 'COPYING' for more information.
  11 */
  12 #include "util/glib-list-iterators.h"
  13 #include "graphlayout/graphlayout.h"
  14 #include <iostream>
  15 #include <config.h>
  16
  17 #include "sp-path.h"
  18 #include "sp-item.h"
  19 #include "sp-item-transform.h"
  20 #include "sp-conn-end-pair.h"
  21 #include "conn-avoid-ref.h"
  22 #include "libavoid/connector.h"
  23 #include "libavoid/geomtypes.h"
  24 #include "libcola/cola.h"
  25 #include "libvpsc/generate-constraints.h"
  26 #include <map>
  27 #include <vector>
  28 #include <algorithm>
  29 #include <float.h>
  30
  31 using namespace std;
  32 using namespace cola;
  33
  34 /**
  35  * Returns true if item is a connector
  36  */
  37 bool isConnector(SPItem const *const i) {
  38         SPPath *path = NULL;
  39         if(SP_IS_PATH(i)) {
  40                 path = SP_PATH(i);
  41         }
  42         return path && path->connEndPair.isAutoRoutingConn();
  43 }
  44
  45 /**
  46  * Scans the items list and places those items that are
  47  * not connectors in filtered
  48  */
  49 void filterConnectors(GSList const *const items, list<SPItem *> &filtered) {
  50         for(GSList *i=(GSList *)items; i!=NULL; i=i->next) {
  51                 SPItem *item=SP_ITEM(i->data);
  52                 if(!isConnector(item)) {
  53                         filtered.push_back(item);
  54                 }
  55         }
  56 }
  57 /**
  58 * Takes a list of inkscape items, extracts the graph defined by
  59 * connectors between them, and uses graph layout techniques to find
  60 * a nice layout
  61 */
  62 void graphlayout(GSList const *const items) {
  63         if(!items) {
  64                 return;
  65         }
  66
  67         using Inkscape::Util::GSListConstIterator;
  68         list<SPItem *> selected;
  69         filterConnectors(items,selected);
  70         if (selected.empty()) return;
  71
  72         const unsigned n=selected.size();
  73         cout<<"|V|="<<n<<endl;
  74         //Check 2 or more selected objects
  75         if (n < 2) return;
  76
  77         double minX=DBL_MAX, minY=DBL_MAX, maxX=-DBL_MAX, maxY=-DBL_MAX;
  78
  79         map<string,unsigned> nodelookup;
  80         vector<Rectangle*> rs;
  81         vector<Edge> es;
  82         for (list<SPItem *>::iterator i(selected.begin());
  83                 i != selected.end();
  84                 ++i)
  85         {
  86                 SPItem *u=*i;
  87                 NR::Rect const item_box(sp_item_bbox_desktop(u));
  88                 NR::Point ll(item_box.min());
  89                 NR::Point ur(item_box.max());
  90                 minX=min(ll[0],minX); minY=min(ll[1],minY);
  91                 maxX=max(ur[0],maxX); maxY=max(ur[1],maxY);
  92                 cout<<"Creating node for id: "<<u->id<<endl;
  93                 nodelookup[u->id]=rs.size();
  94                 rs.push_back(new Rectangle(ll[0],ur[0],ll[1],ur[1]));
  95         }
  96
  97
  98         for (list<SPItem *>::iterator i(selected.begin());
  99                 i != selected.end();
 100                 ++i)
 101         {
 102                 SPItem *iu=*i;
 103                 cout<<"Getting neighbours for id: "<<iu->id<<endl;
 104                 unsigned u=nodelookup[iu->id];
 105                 GSList *nlist=iu->avoidRef->getAttachedShapes(Avoid::runningFrom);
 106                 list<SPItem *> neighbours;
 107                 neighbours.insert<GSListConstIterator<SPItem *> >(neighbours.end(),nlist,NULL);
 108                 for (list<SPItem *>::iterator j(neighbours.begin());
 109                                 j != neighbours.end();
 110                                 ++j) {
 111
 112                         SPItem *iv=*j;
 113                         // What do we do if iv not in nodelookup?!?!
 114                         unsigned v=nodelookup[iv->id];
 115                         es.push_back(make_pair(u,v));
 116                 }
 117                 if(nlist) {
 118                         g_slist_free(nlist);
 119                 }
 120         }
 121         double width=maxX-minX;
 122         double height=maxY-minY;
 123         const unsigned E = es.size();
 124         double eweights[E];
 125         fill(eweights,eweights+E,1);
 126
 127         ConstrainedMajorizationLayout alg(rs,es,eweights,width/n);
 128         alg.run();
 129
 130         for (list<SPItem *>::iterator it(selected.begin());
 131                 it != selected.end();
 132                 ++it)
 133         {
 134                 SPItem *u=*it;
 135                 if(!isConnector(u)) {
 136                         Rectangle* r=rs[nodelookup[u->id]];
 137                         NR::Rect const item_box(sp_item_bbox_desktop(u));
 138                         NR::Point const curr(item_box.midpoint());
 139                         NR::Point const dest(r->getCentreX(),r->getCentreY());
 140                         sp_item_move_rel(u, NR::translate(dest - curr));
 141                 }
 142         }
 143 }