doxygen: add newline after \file
[blender.git] / source / blender / depsgraph / intern / builder / deg_builder_transitive.cc
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2015 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup depsgraph
22  */
23
24 #include "intern/builder/deg_builder_transitive.h"
25
26 #include "MEM_guardedalloc.h"
27
28 #include "intern/node/deg_node.h"
29 #include "intern/node/deg_node_component.h"
30 #include "intern/node/deg_node_operation.h"
31
32 #include "intern/depsgraph.h"
33 #include "intern/debug/deg_debug.h"
34
35 namespace DEG {
36
37 /* -------------------------------------------------- */
38
39 /* Performs a transitive reduction to remove redundant relations.
40  * https://en.wikipedia.org/wiki/Transitive_reduction
41  *
42  * XXX The current implementation is somewhat naive and has O(V*E) worst case
43  * runtime.
44  * A more optimized algorithm can be implemented later, e.g.
45  *
46  *   http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf
47  *
48  * Care has to be taken to make sure the algorithm can handle the cyclic case
49  * too! (unless we can to prevent this case early on).
50  */
51
52 enum {
53         OP_VISITED = 1,
54         OP_REACHABLE = 2,
55 };
56
57 static void deg_graph_tag_paths_recursive(Node *node)
58 {
59         if (node->custom_flags & OP_VISITED) {
60                 return;
61         }
62         node->custom_flags |= OP_VISITED;
63         for (Relation *rel : node->inlinks) {
64                 deg_graph_tag_paths_recursive(rel->from);
65                 /* Do this only in inlinks loop, so the target node does not get
66                  * flagged. */
67                 rel->from->custom_flags |= OP_REACHABLE;
68         }
69 }
70
71 void deg_graph_transitive_reduction(Depsgraph *graph)
72 {
73         int num_removed_relations = 0;
74         for (OperationNode *target : graph->operations) {
75                 /* Clear tags. */
76                 for (OperationNode *node : graph->operations) {
77                         node->custom_flags = 0;
78                 }
79                 /* Mark nodes from which we can reach the target
80                  * start with children, so the target node and direct children are not
81                  * flagged. */
82                 target->custom_flags |= OP_VISITED;
83                 for (Relation *rel : target->inlinks) {
84                         deg_graph_tag_paths_recursive(rel->from);
85                 }
86                 /* Remove redundant paths to the target. */
87                 for (Node::Relations::const_iterator it_rel = target->inlinks.begin();
88                      it_rel != target->inlinks.end();
89                      )
90                 {
91                         Relation *rel = *it_rel;
92                         if (rel->from->type == NodeType::TIMESOURCE) {
93                                 /* HACK: time source nodes don't get "custom_flags" flag
94                                  * set/cleared. */
95                                 /* TODO: there will be other types in future, so iterators above
96                                  * need modifying. */
97                                 ++it_rel;
98                         }
99                         else if (rel->from->custom_flags & OP_REACHABLE) {
100                                 rel->unlink();
101                                 OBJECT_GUARDED_DELETE(rel, Relation);
102                                 ++num_removed_relations;
103                         }
104                         else {
105                                 ++it_rel;
106                         }
107                 }
108         }
109         DEG_DEBUG_PRINTF((::Depsgraph *)graph, BUILD, "Removed %d relations\n", num_removed_relations);
110 }
111
112 }  // namespace DEG