Cleanup: remove redundant doxygen \file argument
[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 \ingroup depsgraph
21  */
22
23 #include "intern/builder/deg_builder_transitive.h"
24
25 #include "MEM_guardedalloc.h"
26
27 #include "intern/node/deg_node.h"
28 #include "intern/node/deg_node_component.h"
29 #include "intern/node/deg_node_operation.h"
30
31 #include "intern/depsgraph.h"
32 #include "intern/debug/deg_debug.h"
33
34 namespace DEG {
35
36 /* -------------------------------------------------- */
37
38 /* Performs a transitive reduction to remove redundant relations.
39  * https://en.wikipedia.org/wiki/Transitive_reduction
40  *
41  * XXX The current implementation is somewhat naive and has O(V*E) worst case
42  * runtime.
43  * A more optimized algorithm can be implemented later, e.g.
44  *
45  *   http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf
46  *
47  * Care has to be taken to make sure the algorithm can handle the cyclic case
48  * too! (unless we can to prevent this case early on).
49  */
50
51 enum {
52         OP_VISITED = 1,
53         OP_REACHABLE = 2,
54 };
55
56 static void deg_graph_tag_paths_recursive(Node *node)
57 {
58         if (node->custom_flags & OP_VISITED) {
59                 return;
60         }
61         node->custom_flags |= OP_VISITED;
62         for (Relation *rel : node->inlinks) {
63                 deg_graph_tag_paths_recursive(rel->from);
64                 /* Do this only in inlinks loop, so the target node does not get
65                  * flagged. */
66                 rel->from->custom_flags |= OP_REACHABLE;
67         }
68 }
69
70 void deg_graph_transitive_reduction(Depsgraph *graph)
71 {
72         int num_removed_relations = 0;
73         for (OperationNode *target : graph->operations) {
74                 /* Clear tags. */
75                 for (OperationNode *node : graph->operations) {
76                         node->custom_flags = 0;
77                 }
78                 /* Mark nodes from which we can reach the target
79                  * start with children, so the target node and direct children are not
80                  * flagged. */
81                 target->custom_flags |= OP_VISITED;
82                 for (Relation *rel : target->inlinks) {
83                         deg_graph_tag_paths_recursive(rel->from);
84                 }
85                 /* Remove redundant paths to the target. */
86                 for (Node::Relations::const_iterator it_rel = target->inlinks.begin();
87                      it_rel != target->inlinks.end();
88                      )
89                 {
90                         Relation *rel = *it_rel;
91                         if (rel->from->type == NodeType::TIMESOURCE) {
92                                 /* HACK: time source nodes don't get "custom_flags" flag
93                                  * set/cleared. */
94                                 /* TODO: there will be other types in future, so iterators above
95                                  * need modifying. */
96                                 ++it_rel;
97                         }
98                         else if (rel->from->custom_flags & OP_REACHABLE) {
99                                 rel->unlink();
100                                 OBJECT_GUARDED_DELETE(rel, Relation);
101                                 ++num_removed_relations;
102                         }
103                         else {
104                                 ++it_rel;
105                         }
106                 }
107         }
108         DEG_DEBUG_PRINTF((::Depsgraph *)graph, BUILD, "Removed %d relations\n", num_removed_relations);
109 }
110
111 }  // namespace DEG