1/**************************************************************************/
2/* graph_edit_arranger.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#include "graph_edit_arranger.h"
32
33#include "scene/gui/graph_edit.h"
34
35void GraphEditArranger::arrange_nodes() {
36 ERR_FAIL_NULL(graph_edit);
37
38 if (!arranging_graph) {
39 arranging_graph = true;
40 } else {
41 return;
42 }
43
44 Dictionary node_names;
45 HashSet<StringName> selected_nodes;
46
47 bool arrange_entire_graph = true;
48 for (int i = graph_edit->get_child_count() - 1; i >= 0; i--) {
49 GraphNode *graph_element = Object::cast_to<GraphNode>(graph_edit->get_child(i));
50 if (!graph_element) {
51 continue;
52 }
53
54 node_names[graph_element->get_name()] = graph_element;
55
56 if (graph_element->is_selected()) {
57 arrange_entire_graph = false;
58 }
59 }
60
61 HashMap<StringName, HashSet<StringName>> upper_neighbours;
62 HashMap<StringName, Pair<int, int>> port_info;
63 Vector2 origin(FLT_MAX, FLT_MAX);
64
65 float gap_v = 100.0f;
66 float gap_h = 100.0f;
67
68 for (int i = graph_edit->get_child_count() - 1; i >= 0; i--) {
69 GraphNode *graph_element = Object::cast_to<GraphNode>(graph_edit->get_child(i));
70 if (!graph_element) {
71 continue;
72 }
73
74 if (graph_element->is_selected() || arrange_entire_graph) {
75 selected_nodes.insert(graph_element->get_name());
76 HashSet<StringName> s;
77 List<GraphEdit::Connection> connection_list;
78 graph_edit->get_connection_list(&connection_list);
79 for (List<GraphEdit::Connection>::Element *E = connection_list.front(); E; E = E->next()) {
80 GraphNode *p_from = Object::cast_to<GraphNode>(node_names[E->get().from_node]);
81 if (E->get().to_node == graph_element->get_name() && (p_from->is_selected() || arrange_entire_graph) && E->get().to_node != E->get().from_node) {
82 if (!s.has(p_from->get_name())) {
83 s.insert(p_from->get_name());
84 }
85 String s_connection = String(p_from->get_name()) + " " + String(E->get().to_node);
86 StringName _connection(s_connection);
87 Pair<int, int> ports(E->get().from_port, E->get().to_port);
88 if (port_info.has(_connection)) {
89 Pair<int, int> p_ports = port_info[_connection];
90 if (p_ports.first < ports.first) {
91 ports = p_ports;
92 }
93 }
94 port_info.insert(_connection, ports);
95 }
96 }
97 upper_neighbours.insert(graph_element->get_name(), s);
98 }
99 }
100
101 if (!selected_nodes.size()) {
102 arranging_graph = false;
103 return;
104 }
105
106 HashMap<int, Vector<StringName>> layers = _layering(selected_nodes, upper_neighbours);
107 _crossing_minimisation(layers, upper_neighbours);
108
109 Dictionary root, align, sink, shift;
110 _horizontal_alignment(root, align, layers, upper_neighbours, selected_nodes);
111
112 HashMap<StringName, Vector2> new_positions;
113 Vector2 default_position(FLT_MAX, FLT_MAX);
114 Dictionary inner_shift;
115 HashSet<StringName> block_heads;
116
117 for (const StringName &E : selected_nodes) {
118 inner_shift[E] = 0.0f;
119 sink[E] = E;
120 shift[E] = FLT_MAX;
121 new_positions.insert(E, default_position);
122 if ((StringName)root[E] == E) {
123 block_heads.insert(E);
124 }
125 }
126
127 _calculate_inner_shifts(inner_shift, root, node_names, align, block_heads, port_info);
128
129 for (const StringName &E : block_heads) {
130 _place_block(E, gap_v, layers, root, align, node_names, inner_shift, sink, shift, new_positions);
131 }
132 origin.y = Object::cast_to<GraphNode>(node_names[layers[0][0]])->get_position_offset().y - (new_positions[layers[0][0]].y + (float)inner_shift[layers[0][0]]);
133 origin.x = Object::cast_to<GraphNode>(node_names[layers[0][0]])->get_position_offset().x;
134
135 for (const StringName &E : block_heads) {
136 StringName u = E;
137 float start_from = origin.y + new_positions[E].y;
138 do {
139 Vector2 cal_pos;
140 cal_pos.y = start_from + (real_t)inner_shift[u];
141 new_positions.insert(u, cal_pos);
142 u = align[u];
143 } while (u != E);
144 }
145
146 // Compute horizontal coordinates individually for layers to get uniform gap.
147 float start_from = origin.x;
148 float largest_node_size = 0.0f;
149
150 for (unsigned int i = 0; i < layers.size(); i++) {
151 Vector<StringName> layer = layers[i];
152 for (int j = 0; j < layer.size(); j++) {
153 float current_node_size = Object::cast_to<GraphNode>(node_names[layer[j]])->get_size().x;
154 largest_node_size = MAX(largest_node_size, current_node_size);
155 }
156
157 for (int j = 0; j < layer.size(); j++) {
158 float current_node_size = Object::cast_to<GraphNode>(node_names[layer[j]])->get_size().x;
159 Vector2 cal_pos = new_positions[layer[j]];
160
161 if (current_node_size == largest_node_size) {
162 cal_pos.x = start_from;
163 } else {
164 float current_node_start_pos = start_from;
165 if (current_node_size < largest_node_size / 2) {
166 if (!(i || j)) {
167 start_from -= (largest_node_size - current_node_size);
168 }
169 current_node_start_pos = start_from + largest_node_size - current_node_size;
170 }
171 cal_pos.x = current_node_start_pos;
172 }
173 new_positions.insert(layer[j], cal_pos);
174 }
175
176 start_from += largest_node_size + gap_h;
177 largest_node_size = 0.0f;
178 }
179
180 graph_edit->emit_signal(SNAME("begin_node_move"));
181 for (const StringName &E : selected_nodes) {
182 GraphNode *graph_node = Object::cast_to<GraphNode>(node_names[E]);
183 graph_node->set_drag(true);
184 Vector2 pos = (new_positions[E]);
185
186 if (graph_edit->is_snapping_enabled()) {
187 float snapping_distance = graph_edit->get_snapping_distance();
188 pos = pos.snapped(Vector2(snapping_distance, snapping_distance));
189 }
190 graph_node->set_position_offset(pos);
191 graph_node->set_drag(false);
192 }
193 graph_edit->emit_signal(SNAME("end_node_move"));
194 arranging_graph = false;
195}
196
197int GraphEditArranger::_set_operations(SET_OPERATIONS p_operation, HashSet<StringName> &r_u, const HashSet<StringName> &r_v) {
198 switch (p_operation) {
199 case GraphEditArranger::IS_EQUAL: {
200 for (const StringName &E : r_u) {
201 if (!r_v.has(E)) {
202 return 0;
203 }
204 }
205 return r_u.size() == r_v.size();
206 } break;
207 case GraphEditArranger::IS_SUBSET: {
208 if (r_u.size() == r_v.size() && !r_u.size()) {
209 return 1;
210 }
211 for (const StringName &E : r_u) {
212 if (!r_v.has(E)) {
213 return 0;
214 }
215 }
216 return 1;
217 } break;
218 case GraphEditArranger::DIFFERENCE: {
219 for (HashSet<StringName>::Iterator E = r_u.begin(); E;) {
220 HashSet<StringName>::Iterator N = E;
221 ++N;
222 if (r_v.has(*E)) {
223 r_u.remove(E);
224 }
225 E = N;
226 }
227 return r_u.size();
228 } break;
229 case GraphEditArranger::UNION: {
230 for (const StringName &E : r_v) {
231 if (!r_u.has(E)) {
232 r_u.insert(E);
233 }
234 }
235 return r_u.size();
236 } break;
237 default:
238 break;
239 }
240 return -1;
241}
242
243HashMap<int, Vector<StringName>> GraphEditArranger::_layering(const HashSet<StringName> &r_selected_nodes, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours) {
244 HashMap<int, Vector<StringName>> l;
245
246 HashSet<StringName> p = r_selected_nodes, q = r_selected_nodes, u, z;
247 int current_layer = 0;
248 bool selected = false;
249
250 while (!_set_operations(GraphEditArranger::IS_EQUAL, q, u)) {
251 _set_operations(GraphEditArranger::DIFFERENCE, p, u);
252 for (const StringName &E : p) {
253 HashSet<StringName> n = r_upper_neighbours[E];
254 if (_set_operations(GraphEditArranger::IS_SUBSET, n, z)) {
255 Vector<StringName> t;
256 t.push_back(E);
257 if (!l.has(current_layer)) {
258 l.insert(current_layer, Vector<StringName>{});
259 }
260 selected = true;
261 t.append_array(l[current_layer]);
262 l.insert(current_layer, t);
263 HashSet<StringName> V;
264 V.insert(E);
265 _set_operations(GraphEditArranger::UNION, u, V);
266 }
267 }
268 if (!selected) {
269 current_layer++;
270 uint32_t previous_size_z = z.size();
271 _set_operations(GraphEditArranger::UNION, z, u);
272 if (z.size() == previous_size_z) {
273 WARN_PRINT("Graph contains cycle(s). The cycle(s) will not be rearranged accurately.");
274 Vector<StringName> t;
275 if (l.has(0)) {
276 t.append_array(l[0]);
277 }
278 for (const StringName &E : p) {
279 t.push_back(E);
280 }
281 l.insert(0, t);
282 break;
283 }
284 }
285 selected = false;
286 }
287
288 return l;
289}
290
291Vector<StringName> GraphEditArranger::_split(const Vector<StringName> &r_layer, const HashMap<StringName, Dictionary> &r_crossings) {
292 if (!r_layer.size()) {
293 return Vector<StringName>();
294 }
295
296 StringName p = r_layer[Math::random(0, r_layer.size() - 1)];
297 Vector<StringName> left;
298 Vector<StringName> right;
299
300 for (int i = 0; i < r_layer.size(); i++) {
301 if (p != r_layer[i]) {
302 StringName q = r_layer[i];
303 int cross_pq = r_crossings[p][q];
304 int cross_qp = r_crossings[q][p];
305 if (cross_pq > cross_qp) {
306 left.push_back(q);
307 } else {
308 right.push_back(q);
309 }
310 }
311 }
312
313 left.push_back(p);
314 left.append_array(right);
315 return left;
316}
317
318void GraphEditArranger::_horizontal_alignment(Dictionary &r_root, Dictionary &r_align, const HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours, const HashSet<StringName> &r_selected_nodes) {
319 for (const StringName &E : r_selected_nodes) {
320 r_root[E] = E;
321 r_align[E] = E;
322 }
323
324 if (r_layers.size() == 1) {
325 return;
326 }
327
328 for (unsigned int i = 1; i < r_layers.size(); i++) {
329 Vector<StringName> lower_layer = r_layers[i];
330 Vector<StringName> upper_layer = r_layers[i - 1];
331 int r = -1;
332
333 for (int j = 0; j < lower_layer.size(); j++) {
334 Vector<Pair<int, StringName>> up;
335 StringName current_node = lower_layer[j];
336 for (int k = 0; k < upper_layer.size(); k++) {
337 StringName adjacent_neighbour = upper_layer[k];
338 if (r_upper_neighbours[current_node].has(adjacent_neighbour)) {
339 up.push_back(Pair<int, StringName>(k, adjacent_neighbour));
340 }
341 }
342
343 int start = (up.size() - 1) / 2;
344 int end = (up.size() - 1) % 2 ? start + 1 : start;
345 for (int p = start; p <= end; p++) {
346 StringName Align = r_align[current_node];
347 if (Align == current_node && r < up[p].first) {
348 r_align[up[p].second] = lower_layer[j];
349 r_root[current_node] = r_root[up[p].second];
350 r_align[current_node] = r_root[up[p].second];
351 r = up[p].first;
352 }
353 }
354 }
355 }
356}
357
358void GraphEditArranger::_crossing_minimisation(HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours) {
359 if (r_layers.size() == 1) {
360 return;
361 }
362
363 for (unsigned int i = 1; i < r_layers.size(); i++) {
364 Vector<StringName> upper_layer = r_layers[i - 1];
365 Vector<StringName> lower_layer = r_layers[i];
366 HashMap<StringName, Dictionary> c;
367
368 for (int j = 0; j < lower_layer.size(); j++) {
369 StringName p = lower_layer[j];
370 Dictionary d;
371
372 for (int k = 0; k < lower_layer.size(); k++) {
373 unsigned int crossings = 0;
374 StringName q = lower_layer[k];
375
376 if (j != k) {
377 for (int h = 1; h < upper_layer.size(); h++) {
378 if (r_upper_neighbours[p].has(upper_layer[h])) {
379 for (int g = 0; g < h; g++) {
380 if (r_upper_neighbours[q].has(upper_layer[g])) {
381 crossings++;
382 }
383 }
384 }
385 }
386 }
387 d[q] = crossings;
388 }
389 c.insert(p, d);
390 }
391
392 r_layers.insert(i, _split(lower_layer, c));
393 }
394}
395
396void GraphEditArranger::_calculate_inner_shifts(Dictionary &r_inner_shifts, const Dictionary &r_root, const Dictionary &r_node_names, const Dictionary &r_align, const HashSet<StringName> &r_block_heads, const HashMap<StringName, Pair<int, int>> &r_port_info) {
397 for (const StringName &E : r_block_heads) {
398 real_t left = 0;
399 StringName u = E;
400 StringName v = r_align[u];
401 while (u != v && (StringName)r_root[u] != v) {
402 String _connection = String(u) + " " + String(v);
403
404 GraphNode *gnode_from = Object::cast_to<GraphNode>(r_node_names[u]);
405 GraphNode *gnode_to = Object::cast_to<GraphNode>(r_node_names[v]);
406
407 Pair<int, int> ports = r_port_info[_connection];
408 int port_from = ports.first;
409 int port_to = ports.second;
410
411 Vector2 pos_from = gnode_from->get_output_port_position(port_from) * graph_edit->get_zoom();
412 Vector2 pos_to = gnode_to->get_input_port_position(port_to) * graph_edit->get_zoom();
413
414 real_t s = (real_t)r_inner_shifts[u] + (pos_from.y - pos_to.y) / graph_edit->get_zoom();
415 r_inner_shifts[v] = s;
416 left = MIN(left, s);
417
418 u = v;
419 v = (StringName)r_align[v];
420 }
421
422 u = E;
423 do {
424 r_inner_shifts[u] = (real_t)r_inner_shifts[u] - left;
425 u = (StringName)r_align[u];
426 } while (u != E);
427 }
428}
429
430float GraphEditArranger::_calculate_threshold(StringName p_v, StringName p_w, const Dictionary &r_node_names, const HashMap<int, Vector<StringName>> &r_layers, const Dictionary &r_root, const Dictionary &r_align, const Dictionary &r_inner_shift, real_t p_current_threshold, const HashMap<StringName, Vector2> &r_node_positions) {
431#define MAX_ORDER 2147483647
432#define ORDER(node, layers) \
433 for (unsigned int i = 0; i < layers.size(); i++) { \
434 int index = layers[i].find(node); \
435 if (index > 0) { \
436 order = index; \
437 break; \
438 } \
439 order = MAX_ORDER; \
440 }
441
442 int order = MAX_ORDER;
443 float threshold = p_current_threshold;
444 if (p_v == p_w) {
445 int min_order = MAX_ORDER;
446 GraphEdit::Connection incoming;
447 List<GraphEdit::Connection> connection_list;
448 graph_edit->get_connection_list(&connection_list);
449 for (List<GraphEdit::Connection>::Element *E = connection_list.front(); E; E = E->next()) {
450 if (E->get().to_node == p_w) {
451 ORDER(E->get().from_node, r_layers);
452 if (min_order > order) {
453 min_order = order;
454 incoming = E->get();
455 }
456 }
457 }
458
459 if (incoming.from_node != StringName()) {
460 GraphNode *gnode_from = Object::cast_to<GraphNode>(r_node_names[incoming.from_node]);
461 GraphNode *gnode_to = Object::cast_to<GraphNode>(r_node_names[p_w]);
462 Vector2 pos_from = gnode_from->get_output_port_position(incoming.from_port) * graph_edit->get_zoom();
463 Vector2 pos_to = gnode_to->get_input_port_position(incoming.to_port) * graph_edit->get_zoom();
464
465 // If connected block node is selected, calculate thershold or add current block to list.
466 if (gnode_from->is_selected()) {
467 Vector2 connected_block_pos = r_node_positions[r_root[incoming.from_node]];
468 if (connected_block_pos.y != FLT_MAX) {
469 //Connected block is placed, calculate threshold.
470 threshold = connected_block_pos.y + (real_t)r_inner_shift[incoming.from_node] - (real_t)r_inner_shift[p_w] + pos_from.y - pos_to.y;
471 }
472 }
473 }
474 }
475 if (threshold == FLT_MIN && (StringName)r_align[p_w] == p_v) {
476 // This time, pick an outgoing edge and repeat as above!
477 int min_order = MAX_ORDER;
478 GraphEdit::Connection outgoing;
479 List<GraphEdit::Connection> connection_list;
480 graph_edit->get_connection_list(&connection_list);
481 for (List<GraphEdit::Connection>::Element *E = connection_list.front(); E; E = E->next()) {
482 if (E->get().from_node == p_w) {
483 ORDER(E->get().to_node, r_layers);
484 if (min_order > order) {
485 min_order = order;
486 outgoing = E->get();
487 }
488 }
489 }
490
491 if (outgoing.to_node != StringName()) {
492 GraphNode *gnode_from = Object::cast_to<GraphNode>(r_node_names[p_w]);
493 GraphNode *gnode_to = Object::cast_to<GraphNode>(r_node_names[outgoing.to_node]);
494 Vector2 pos_from = gnode_from->get_output_port_position(outgoing.from_port) * graph_edit->get_zoom();
495 Vector2 pos_to = gnode_to->get_input_port_position(outgoing.to_port) * graph_edit->get_zoom();
496
497 // If connected block node is selected, calculate thershold or add current block to list.
498 if (gnode_to->is_selected()) {
499 Vector2 connected_block_pos = r_node_positions[r_root[outgoing.to_node]];
500 if (connected_block_pos.y != FLT_MAX) {
501 //Connected block is placed. Calculate threshold
502 threshold = connected_block_pos.y + (real_t)r_inner_shift[outgoing.to_node] - (real_t)r_inner_shift[p_w] + pos_from.y - pos_to.y;
503 }
504 }
505 }
506 }
507#undef MAX_ORDER
508#undef ORDER
509 return threshold;
510}
511
512void GraphEditArranger::_place_block(StringName p_v, float p_delta, const HashMap<int, Vector<StringName>> &r_layers, const Dictionary &r_root, const Dictionary &r_align, const Dictionary &r_node_name, const Dictionary &r_inner_shift, Dictionary &r_sink, Dictionary &r_shift, HashMap<StringName, Vector2> &r_node_positions) {
513#define PRED(node, layers) \
514 for (unsigned int i = 0; i < layers.size(); i++) { \
515 int index = layers[i].find(node); \
516 if (index > 0) { \
517 predecessor = layers[i][index - 1]; \
518 break; \
519 } \
520 predecessor = StringName(); \
521 }
522
523 StringName predecessor;
524 StringName successor;
525 Vector2 pos = r_node_positions[p_v];
526
527 if (pos.y == FLT_MAX) {
528 pos.y = 0;
529 bool initial = false;
530 StringName w = p_v;
531 real_t threshold = FLT_MIN;
532 do {
533 PRED(w, r_layers);
534 if (predecessor != StringName()) {
535 StringName u = r_root[predecessor];
536 _place_block(u, p_delta, r_layers, r_root, r_align, r_node_name, r_inner_shift, r_sink, r_shift, r_node_positions);
537 threshold = _calculate_threshold(p_v, w, r_node_name, r_layers, r_root, r_align, r_inner_shift, threshold, r_node_positions);
538 if ((StringName)r_sink[p_v] == p_v) {
539 r_sink[p_v] = r_sink[u];
540 }
541
542 Vector2 predecessor_root_pos = r_node_positions[u];
543 Vector2 predecessor_node_size = Object::cast_to<GraphNode>(r_node_name[predecessor])->get_size();
544 if (r_sink[p_v] != r_sink[u]) {
545 real_t sc = pos.y + (real_t)r_inner_shift[w] - predecessor_root_pos.y - (real_t)r_inner_shift[predecessor] - predecessor_node_size.y - p_delta;
546 r_shift[r_sink[u]] = MIN(sc, (real_t)r_shift[r_sink[u]]);
547 } else {
548 real_t sb = predecessor_root_pos.y + (real_t)r_inner_shift[predecessor] + predecessor_node_size.y - (real_t)r_inner_shift[w] + p_delta;
549 sb = MAX(sb, threshold);
550 if (initial) {
551 pos.y = sb;
552 } else {
553 pos.y = MAX(pos.y, sb);
554 }
555 initial = false;
556 }
557 }
558 threshold = _calculate_threshold(p_v, w, r_node_name, r_layers, r_root, r_align, r_inner_shift, threshold, r_node_positions);
559 w = r_align[w];
560 } while (w != p_v);
561 r_node_positions.insert(p_v, pos);
562 }
563
564#undef PRED
565}
566