COMPMID-1505: Add native grouping support at graph level

Change-Id: Iedc91b0aee743b59af5140c8acb8124548da3163
Reviewed-on: https://eu-gerrit-1.euhpc.arm.com/144362
Tested-by: Jenkins <bsgcomp@arm.com>
Reviewed-by: Giorgio Arena <giorgio.arena@arm.com>
Reviewed-by: Michele DiGiorgio <michele.digiorgio@arm.com>

3 files changed, 55 insertions, 124 deletions

diff --git a/arm_compute/graph/algorithms/Algorithms.h b/arm_compute/graph/algorithms/Algorithms.h
index f89856f327..7af2455e93 100644
--- a/arm_compute/graph/algorithms/Algorithms.h
+++ b/arm_compute/graph/algorithms/Algorithms.h
@@ -24,6 +24,6 @@
 #ifndef __ARM_COMPUTE_GRAPH_ALGORITHMS_H__
 #define __ARM_COMPUTE_GRAPH_ALGORITHMS_H__
 
-#include "arm_compute/graph/algorithms/BFS.h"
+#include "arm_compute/graph/algorithms/TopologicalSort.h"
 
 #endif /* __ARM_COMPUTE_GRAPH_ALGORITHMS_H__ */
diff --git a/arm_compute/graph/algorithms/BFS.h b/arm_compute/graph/algorithms/BFS.h
deleted file mode 100644
index 97292d733b..0000000000
--- a/arm_compute/graph/algorithms/BFS.h
+++ /dev/null
@@ -1,123 +0,0 @@
-/*
- * Copyright (c) 2018 ARM Limited.
- *
- * SPDX-License-Identifier: MIT
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to
- * deal in the Software without restriction, including without limitation the
- * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
- * sell copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in all
- * copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-#ifndef __ARM_COMPUTE_GRAPH_ALGORITHM_BFS_H__
-#define __ARM_COMPUTE_GRAPH_ALGORITHM_BFS_H__
-
-#include "arm_compute/graph/Graph.h"
-
-#include <list>
-#include <vector>
-
-namespace arm_compute
-{
-namespace graph
-{
-namespace detail
-{
-/** Checks if all the input dependencies of a node have been visited
- *
- * @param[in] node    Node to check
- * @param[in] visited Vector that contains the visited information
- *
- * @return True if all inputs dependencies have been visited else false
- */
-inline bool all_inputs_are_visited(const INode *node, const std::vector<bool> &visited)
-{
-    ARM_COMPUTE_ERROR_ON(node == nullptr);
-    const Graph *graph = node->graph();
-    ARM_COMPUTE_ERROR_ON(graph == nullptr);
-
-    bool are_all_visited = true;
-    for(const auto &input_edge_id : node->input_edges())
-    {
-        if(input_edge_id != EmptyNodeID)
-        {
-            const Edge *input_edge = graph->edge(input_edge_id);
-            ARM_COMPUTE_ERROR_ON(input_edge == nullptr);
-            ARM_COMPUTE_ERROR_ON(input_edge->producer() == nullptr);
-            if(!visited[input_edge->producer_id()])
-            {
-                are_all_visited = false;
-                break;
-            }
-        }
-    }
-
-    return are_all_visited;
-}
-} // namespace detail
-
-/** Breadth first search traversal
- *
- * @param g Graph to traverse
- *
- * @return A vector with the node id traversal order
- */
-inline std::vector<NodeID> bfs(Graph &g)
-{
-    std::vector<NodeID> bfs_order_vector;
-
-    // Created visited vector
-    std::vector<bool> visited(g.nodes().size(), false);
-
-    // Create BFS queue
-    std::list<NodeID> queue;
-
-    // Push inputs and mark as visited
-    for(auto &input : g.nodes(NodeType::Input))
-    {
-        if(input != EmptyNodeID)
-        {
-            visited[input] = true;
-            queue.push_back(input);
-        }
-    }
-
-    // Iterate over vector and edges
-    while(!queue.empty())
-    {
-        // Dequeue a node from queue and process
-        NodeID n = queue.front();
-        bfs_order_vector.push_back(n);
-        queue.pop_front();
-
-        const INode *node = g.node(n);
-        ARM_COMPUTE_ERROR_ON(node == nullptr);
-        for(const auto &eid : node->output_edges())
-        {
-            const Edge *e = g.edge(eid);
-            ARM_COMPUTE_ERROR_ON(e == nullptr);
-            if(!visited[e->consumer_id()] && detail::all_inputs_are_visited(e->consumer(), visited))
-            {
-                visited[e->consumer_id()] = true;
-                queue.push_back(e->consumer_id());
-            }
-        }
-    }
-
-    return bfs_order_vector;
-}
-} // namespace graph
-} // namespace arm_compute
-#endif /* __ARM_COMPUTE_GRAPH_ALGORITHM_BFS_H__ */
diff --git a/arm_compute/graph/algorithms/TopologicalSort.h b/arm_compute/graph/algorithms/TopologicalSort.h
new file mode 100644
index 0000000000..6684844790
--- /dev/null
+++ b/arm_compute/graph/algorithms/TopologicalSort.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (c) 2018 ARM Limited.
+ *
+ * SPDX-License-Identifier: MIT
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
+ * deal in the Software without restriction, including without limitation the
+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+#ifndef __ARM_COMPUTE_GRAPH_ALGORITHM_TOPOLOGICAL_SORT_H__
+#define __ARM_COMPUTE_GRAPH_ALGORITHM_TOPOLOGICAL_SORT_H__
+
+#include "arm_compute/graph/Types.h"
+
+#include <vector>
+
+namespace arm_compute
+{
+namespace graph
+{
+// Forward declarations
+class Graph;
+
+/** Breadth first search traversal
+ *
+ * @param g Graph to traverse
+ *
+ * @return A vector with the node id traversal order
+ */
+std::vector<NodeID> bfs(Graph &g);
+/** Depth first search traversal
+ *
+ * @param g Graph to traverse
+ *
+ * @return A vector with the node id traversal order
+ */
+std::vector<NodeID> dfs(Graph &g);
+} // namespace graph
+} // namespace arm_compute
+#endif /* __ARM_COMPUTE_GRAPH_ALGORITHM_TOPOLOGICAL_SORT_H__ */