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