1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /**
3  * @file
4  * Interface between Inkscape code (SPItem) and graphlayout functions.
5  */
6 /*
7  * Authors:
8  *   Tim Dwyer <Tim.Dwyer@infotech.monash.edu.au>
9  *   Abhishek Sharma
10  *
11  * Copyright (C) 2005 Authors
12  *
13  * Released under GNU GPL v2+, read the file 'COPYING' for more information.
14  */
15 
16 #include <algorithm>
17 #include <cstring>
18 #include <iostream>
19 #include <list>
20 #include <map>
21 #include <string>
22 #include <valarray>
23 #include <vector>
24 
25 #include <2geom/transforms.h>
26 
27 #include "conn-avoid-ref.h"
28 #include "desktop.h"
29 #include "graphlayout.h"
30 #include "inkscape.h"
31 
32 #include "3rdparty/adaptagrams/libavoid/router.h"
33 
34 #include "3rdparty/adaptagrams/libcola/cola.h"
35 #include "3rdparty/adaptagrams/libcola/connected_components.h"
36 
37 #include "object/sp-item-transform.h"
38 #include "object/sp-namedview.h"
39 #include "object/sp-path.h"
40 #include "style.h"
41 
42 using namespace cola;
43 using namespace vpsc;
44 
45 /**
46  * Returns true if item is a connector
47  */
isConnector(SPItem const * const item)48 bool isConnector(SPItem const * const item) {
49     SPPath * path = nullptr;
50     if (SP_IS_PATH(item)) {
51         path = SP_PATH(item);
52     }
53     return path && path->connEndPair.isAutoRoutingConn();
54 }
55 
56 struct CheckProgress: TestConvergence {
CheckProgressCheckProgress57     CheckProgress(double d, unsigned i, std::list<SPItem*> & selected, Rectangles & rs,
58             std::map<std::string, unsigned> & nodelookup)
59         : TestConvergence(d, i)
60         , selected(selected)
61         , rs(rs)
62         , nodelookup(nodelookup)
63     {}
operator ()CheckProgress64     bool operator()(const double new_stress, std::valarray<double> & X, std::valarray<double> & Y) override {
65         /* This is where, if we wanted to animate the layout, we would need to update
66          * the positions of all objects and redraw the canvas and maybe sleep a bit
67          cout << "stress="<<new_stress<<endl;
68         cout << "x[0]="<<rs[0]->getMinX()<<endl;
69         for (std::list<SPItem *>::iterator it(selected.begin());
70             it != selected.end();
71             ++it)
72         {
73             SPItem *u=*it;
74             if(!isConnector(u)) {
75                 Rectangle* r=rs[nodelookup[u->id]];
76                 Geom::Rect const item_box(sp_item_bbox_desktop(u));
77                 Geom::Point const curr(item_box.midpoint());
78                 Geom::Point const dest(r->getCentreX(),r->getCentreY());
79                 u->move_rel(Geom::Translate(dest - curr));
80             }
81         }
82         */
83         return TestConvergence::operator()(new_stress, X, Y);
84     }
85     std::list<SPItem*> & selected;
86     Rectangles & rs;
87     std::map<std::string, unsigned> & nodelookup;
88 };
89 
90 /**
91  * Scans the items list and places those items that are
92  * not connectors in filtered
93  */
filterConnectors(std::vector<SPItem * > const & items,std::list<SPItem * > & filtered)94 void filterConnectors(std::vector<SPItem*> const & items, std::list<SPItem*> & filtered) {
95     for (SPItem * item: items) {
96         if (!isConnector(item)) {
97             filtered.push_back(item);
98         }
99     }
100 }
101 
102 /**
103  * Takes a list of inkscape items, extracts the graph defined by
104  * connectors between them, and uses graph layout techniques to find
105  * a nice layout
106  */
graphlayout(std::vector<SPItem * > const & items)107 void graphlayout(std::vector<SPItem*> const & items) {
108     if (items.empty()) return;
109 
110     std::list<SPItem*> selected;
111     filterConnectors(items, selected);
112     std::vector<SPItem*> connectors;
113     std::copy_if(items.begin(), items.end(), std::back_inserter(connectors), [](SPItem* item){return isConnector(item); });
114 
115     if (selected.size() < 2) return;
116 
117     // add the connector spacing to the size of node bounding boxes
118     // so that connectors can always be routed between shapes
119     SPDesktop * desktop = SP_ACTIVE_DESKTOP;
120     double spacing = 0;
121     if (desktop) spacing = desktop->namedview->connector_spacing + 0.1;
122 
123     std::map<std::string, unsigned> nodelookup;
124     Rectangles rs;
125     std::vector<Edge> es;
126     for (SPItem * item: selected) {
127         Geom::OptRect const item_box = item->desktopVisualBounds();
128         if (item_box) {
129             Geom::Point ll(item_box->min());
130             Geom::Point ur(item_box->max());
131             nodelookup[item->getId()] = rs.size();
132             rs.push_back(new Rectangle(ll[0] - spacing, ur[0] + spacing,
133                     ll[1] - spacing, ur[1] + spacing));
134         } else {
135             // I'm not actually sure if it's possible for something with a
136             // NULL item-box to be attached to a connector in which case we
137             // should never get to here... but if such a null box can occur it's
138             // probably pretty safe to simply ignore
139             //fprintf(stderr, "NULL item_box found in graphlayout, ignoring!\n");
140         }
141     }
142 
143     Inkscape::Preferences * prefs = Inkscape::Preferences::get();
144     CompoundConstraints constraints;
145     double ideal_connector_length = prefs->getDouble("/tools/connector/length", 100.0);
146     double directed_edge_height_modifier = 1.0;
147 
148     bool directed       = prefs->getBool("/tools/connector/directedlayout");
149     bool avoid_overlaps = prefs->getBool("/tools/connector/avoidoverlaplayout");
150 
151     for (SPItem* conn: connectors) {
152         SPPath* path = SP_PATH(conn);
153         std::array<SPItem*, 2> attachedItems;
154         path->connEndPair.getAttachedItems(attachedItems.data());
155         if (attachedItems[0] == nullptr) continue;
156         if (attachedItems[1] == nullptr) continue;
157         std::map<std::string, unsigned>::iterator i_iter=nodelookup.find(attachedItems[0]->getId());
158         if (i_iter == nodelookup.end()) continue;
159         unsigned rect_index_first = i_iter->second;
160         i_iter = nodelookup.find(attachedItems[1]->getId());
161         if (i_iter == nodelookup.end()) continue;
162         unsigned rect_index_second = i_iter->second;
163         es.emplace_back(rect_index_first, rect_index_second);
164 
165         if (conn->style->marker_end.set) {
166             if (directed && strcmp(conn->style->marker_end.value(), "none")) {
167                 constraints.push_back(new SeparationConstraint(YDIM, rect_index_first, rect_index_second,
168                                                                ideal_connector_length * directed_edge_height_modifier));
169             }
170         }
171     }
172 
173     EdgeLengths elengths(es.size(), 1);
174     std::vector<Component*> cs;
175     connectedComponents(rs, es, cs);
176     for (Component * c: cs) {
177         if (c->edges.size() < 2) continue;
178         CheckProgress test(0.0001, 100, selected, rs, nodelookup);
179         ConstrainedMajorizationLayout alg(c->rects, c->edges, nullptr, ideal_connector_length, elengths, &test);
180         if (avoid_overlaps) alg.setAvoidOverlaps();
181         alg.setConstraints(&constraints);
182         alg.run();
183     }
184     separateComponents(cs);
185 
186     for (SPItem * item: selected) {
187         if (!isConnector(item)) {
188             std::map<std::string, unsigned>::iterator i = nodelookup.find(item->getId());
189             if (i != nodelookup.end()) {
190                 Rectangle * r = rs[i->second];
191                 Geom::OptRect item_box = item->desktopVisualBounds();
192                 if (item_box) {
193                     Geom::Point const curr(item_box->midpoint());
194                     Geom::Point const dest(r->getCentreX(),r->getCentreY());
195                     item->move_rel(Geom::Translate(dest - curr));
196                 }
197             }
198         }
199     }
200     for (CompoundConstraint * c: constraints) {
201         delete c;
202     }
203     for (Rectangle * r: rs) {
204         delete r;
205     }
206 }
207 // vim: set cindent
208 // vim: ts=4 sw=4 et tw=0 wm=0
209 
210 /*
211   Local Variables:
212   mode:c++
213   c-file-style:"stroustrup"
214   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
215   indent-tabs-mode:nil
216   fill-column:99
217   End:
218 */
219 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
220