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