IVGCVSW-1896 : SubGraph selector

Change-Id: Iae9a76b10d84d7ba80136b54355f8d37d2df475d

7 files changed, 982 insertions, 38 deletions

diff --git a/Android.mk b/Android.mk
index a2299a14d4..fc126ac649 100644
--- a/Android.mk
+++ b/Android.mk
@@ -110,6 +110,8 @@ LOCAL_SRC_FILES := \
         src/armnn/Optimizer.cpp \
         src/armnn/Runtime.cpp \
         src/armnn/SerializeLayerParameters.cpp \
+        src/armnn/SubGraph.cpp \
+        src/armnn/SubGraphSelector.cpp \
         src/armnn/InternalTypes.cpp \
         src/armnn/Layer.cpp \
         src/armnn/LoadedNetwork.cpp \
@@ -196,6 +198,7 @@ LOCAL_SRC_FILES := \
 	src/armnn/test/UtilsTests.cpp \
 	src/armnn/test/GraphTests.cpp \
 	src/armnn/test/RuntimeTests.cpp \
+        src/armnn/test/SubGraphTests.cpp \
 	src/armnn/test/TensorTest.cpp \
 	src/armnn/test/NetworkTests.cpp \
 	src/armnn/test/InstrumentTests.cpp \
diff --git a/CMakeLists.txt b/CMakeLists.txt
index dcd097c705..9ae6e972f1 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -228,38 +228,49 @@ list(APPEND armnn_sources
     src/armnn/layers/SplitterLayer.cpp
     src/armnn/layers/SubtractionLayer.cpp
     src/armnn/layers/SubtractionLayer.hpp
-    src/armnn/InternalTypes.hpp
+    src/armnn/Descriptors.cpp
+    src/armnn/DeviceSpec.hpp
+    src/armnn/Exceptions.cpp
+    src/armnn/Graph.cpp
+    src/armnn/Graph.hpp
+    src/armnn/IGraphObservable.hpp
+    src/armnn/Instrument.hpp
     src/armnn/InternalTypes.cpp
-    src/armnn/JsonPrinter.hpp
+    src/armnn/InternalTypes.hpp
     src/armnn/JsonPrinter.cpp
+    src/armnn/JsonPrinter.hpp
+    src/armnn/Layer.cpp
     src/armnn/LayerFwd.hpp
     src/armnn/Layer.hpp
-    src/armnn/Layer.cpp
     src/armnn/LayersFwd.hpp
-    src/armnn/Runtime.hpp
-    src/armnn/Runtime.cpp
-    src/armnn/SerializeLayerParameters.cpp
-    src/armnn/SerializeLayerParameters.hpp
-    src/armnn/Descriptors.cpp
-    src/armnn/DeviceSpec.hpp
-    src/armnn/LoadedNetwork.hpp
+    src/armnn/LayerSupportCommon.hpp
+    src/armnn/LayerSupport.cpp
     src/armnn/LoadedNetwork.cpp
-    src/armnn/Exceptions.cpp
-    src/armnn/Graph.hpp
-    src/armnn/Graph.cpp
-    src/armnn/Network.hpp
+    src/armnn/LoadedNetwork.hpp
     src/armnn/Network.cpp
+    src/armnn/Network.hpp
     src/armnn/NetworkUtils.hpp
+    src/armnn/Observable.cpp
+    src/armnn/Observable.hpp
+    src/armnn/Optimizer.cpp
+    src/armnn/Optimizer.hpp
+    src/armnn/Profiling.cpp
     src/armnn/ProfilingEvent.cpp
     src/armnn/ProfilingEvent.hpp
-    src/armnn/Profiling.cpp
-    src/armnn/Instrument.hpp
-    src/armnn/WallClockTimer.hpp
-    src/armnn/WallClockTimer.cpp
+    src/armnn/Profiling.hpp
+    src/armnn/Runtime.cpp
+    src/armnn/Runtime.hpp
+    src/armnn/SerializeLayerParameters.cpp
+    src/armnn/SerializeLayerParameters.hpp
+    src/armnn/SubGraph.cpp
+    src/armnn/SubGraph.hpp
+    src/armnn/SubGraphSelector.cpp
+    src/armnn/SubGraphSelector.hpp
     src/armnn/Tensor.cpp
+    src/armnn/TypeUtils.hpp
     src/armnn/Utils.cpp
-    src/armnn/LayerSupport.cpp
-    src/armnn/LayerSupportCommon.hpp
+    src/armnn/WallClockTimer.cpp
+    src/armnn/WallClockTimer.hpp
     src/armnn/optimizations/All.hpp
     src/armnn/optimizations/ConvertConstants.hpp
     src/armnn/optimizations/MovePermuteUp.hpp
@@ -270,12 +281,7 @@ list(APPEND armnn_sources
     src/armnn/optimizations/SquashEqualSiblings.hpp
     src/armnn/optimizations/OptimizeInverseConversions.hpp
     src/armnn/optimizations/ConvertFp32NetworkToFp16.hpp
-    src/armnn/Optimizer.hpp
-    src/armnn/Optimizer.cpp
     third-party/half/half.hpp
-    src/armnn/IGraphObservable.hpp
-    src/armnn/Observable.hpp
-    src/armnn/Observable.cpp
     )
 
 # Files used for Streamline-based profiling backend
@@ -334,26 +340,27 @@ endif()
 if(BUILD_UNIT_TESTS)
     set(unittest_sources)
     list(APPEND unittest_sources
-        src/armnn/test/UnitTests.cpp
-        src/armnn/test/UnitTests.hpp
+        src/armnn/test/CreateWorkload.hpp
+        src/armnn/test/CsvReaderTest.cpp
         src/armnn/test/EndToEndTest.cpp
-        src/armnn/test/UtilsTests.cpp
+        src/armnn/test/FloatingPointConverterTest.cpp
         src/armnn/test/GraphTests.cpp
+        src/armnn/test/GraphUtils.hpp
+        src/armnn/test/InstrumentTests.cpp
+        src/armnn/test/NetworkTests.cpp
+        src/armnn/test/ObservableTest.cpp
         src/armnn/test/OptimizerTests.cpp
+        src/armnn/test/OptionalTest.cpp
         src/armnn/test/ProfilerTests.cpp
+        src/armnn/test/ProfilingEventTest.cpp
         src/armnn/test/RuntimeTests.cpp
         src/armnn/test/RuntimeTests.hpp
-        src/armnn/test/CreateWorkload.hpp
-        src/armnn/test/TensorTest.cpp
+        src/armnn/test/SubGraphTests.cpp
         src/armnn/test/TensorHelpers.hpp
-        src/armnn/test/CsvReaderTest.cpp
-        src/armnn/test/NetworkTests.cpp
-        src/armnn/test/FloatingPointConverterTest.cpp
-        src/armnn/test/ProfilingEventTest.cpp
-        src/armnn/test/GraphUtils.hpp
-        src/armnn/test/InstrumentTests.cpp
-        src/armnn/test/ObservableTest.cpp
-        src/armnn/test/OptionalTest.cpp)
+        src/armnn/test/TensorTest.cpp
+        src/armnn/test/UnitTests.cpp
+        src/armnn/test/UnitTests.hpp
+        src/armnn/test/UtilsTests.cpp)
 
     if(BUILD_TF_PARSER)
         list(APPEND unittest_sources
diff --git a/src/armnn/SubGraph.cpp b/src/armnn/SubGraph.cpp
new file mode 100644
index 0000000000..5d41f32932
--- /dev/null
+++ b/src/armnn/SubGraph.cpp
@@ -0,0 +1,72 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#include "Layer.hpp"
+#include "SubGraph.hpp"
+
+#include <boost/numeric/conversion/cast.hpp>
+
+namespace armnn
+{
+
+SubGraph::SubGraph()
+{
+}
+
+SubGraph::SubGraph(InputSlots && inputs,
+                   OutputSlots && outputs,
+                   Layers && layers)
+: m_InputSlots{inputs}
+, m_OutputSlots{outputs}
+, m_Layers{layers}
+{
+}
+
+const SubGraph::InputSlots & SubGraph::GetInputSlots() const
+{
+    return m_InputSlots;
+}
+
+const SubGraph::OutputSlots & SubGraph::GetOutputSlots() const
+{
+    return m_OutputSlots;
+}
+
+const InputSlot* SubGraph::GetInputSlot(unsigned int index) const
+{
+    return m_InputSlots.at(index);
+}
+
+InputSlot* SubGraph::GetInputSlot(unsigned int index)
+{
+    return  m_InputSlots.at(index);
+}
+
+const OutputSlot* SubGraph::GetOutputSlot(unsigned int index) const
+{
+    return m_OutputSlots.at(index);
+}
+
+OutputSlot* SubGraph::GetOutputSlot(unsigned int index)
+{
+    return m_OutputSlots.at(index);
+}
+
+unsigned int SubGraph::GetNumInputSlots() const
+{
+    return boost::numeric_cast<unsigned int>(m_InputSlots.size());
+}
+
+unsigned int SubGraph::GetNumOutputSlots() const
+{
+    return boost::numeric_cast<unsigned int>(m_OutputSlots.size());
+}
+
+const SubGraph::Layers & SubGraph::GetLayers() const
+{
+    return m_Layers;
+}
+
+} // namespace armnn
diff --git a/src/armnn/SubGraph.hpp b/src/armnn/SubGraph.hpp
new file mode 100644
index 0000000000..312bb115eb
--- /dev/null
+++ b/src/armnn/SubGraph.hpp
@@ -0,0 +1,53 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#pragma once
+
+#include "Layer.hpp"
+
+#include <vector>
+#include <unordered_set>
+
+namespace armnn
+{
+
+///
+/// The SubGraph class represents a subgraph of a Graph.
+/// The data it holds, points to data held by layers of the Graph, so the
+/// the contents of the SubGraph becomes invalid when the Layers are destroyed
+/// or changed.
+///
+class SubGraph final
+{
+public:
+    using InputSlots = std::vector<InputSlot *>;
+    using OutputSlots = std::vector<OutputSlot *>;
+    using Layers = std::unordered_set<Layer *>;
+
+    SubGraph();
+    SubGraph(InputSlots && inputs,
+             OutputSlots && outputs,
+             Layers && layers);
+
+    const InputSlots & GetInputSlots() const;
+    const OutputSlots & GetOutputSlots() const;
+    const Layers & GetLayers() const;
+
+    const InputSlot* GetInputSlot(unsigned int index) const;
+    InputSlot* GetInputSlot(unsigned int index);
+
+    const OutputSlot* GetOutputSlot(unsigned int index) const;
+    OutputSlot* GetOutputSlot(unsigned int index);
+
+    unsigned int GetNumInputSlots() const;
+    unsigned int GetNumOutputSlots() const;
+
+private:
+    InputSlots m_InputSlots;
+    OutputSlots m_OutputSlots;
+    Layers m_Layers;
+};
+
+} // namespace armnn
diff --git a/src/armnn/SubGraphSelector.cpp b/src/armnn/SubGraphSelector.cpp
new file mode 100644
index 0000000000..b87e2b73b1
--- /dev/null
+++ b/src/armnn/SubGraphSelector.cpp
@@ -0,0 +1,182 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#include "SubGraphSelector.hpp"
+#include "Graph.hpp"
+#include <boost/assert.hpp>
+#include <algorithm>
+#include <unordered_map>
+
+namespace armnn
+{
+
+namespace
+{
+
+struct LayerSelectionInfo
+{
+    using LayerInfoContainer = std::unordered_map<Layer*, LayerSelectionInfo>;
+    static constexpr uint32_t InitialSplitId() { return 1; }
+
+    LayerSelectionInfo(Layer* layer, const SubGraphSelector::LayerSelectorFunction& selector)
+    : m_Layer{layer}
+    , m_SplitId{0}
+    , m_IsSelected{selector(*layer)}
+    {
+        // fill topology information by storing direct children
+        for (auto&& slot = m_Layer->BeginOutputSlots(); slot != m_Layer->EndOutputSlots(); ++slot)
+        {
+            for (InputSlot* childLayerInputSlot : slot->GetConnections())
+            {
+                Layer& childLayer = childLayerInputSlot->GetOwningLayer();
+                m_DirectChildren.push_back(&childLayer);
+            }
+        }
+    }
+
+    void MarkChildrenSplits(LayerInfoContainer& network,
+                            uint32_t splitId,
+                            bool prevSelected)
+    {
+        if (m_SplitId < splitId)
+        {
+            m_SplitId = splitId;
+        }
+
+        // introduce a new split point at all non-selected points, but only if the
+        // previous point was selected. this prevents creating a new subgraph at
+        // every non-selected layer
+        if (!m_IsSelected && prevSelected)
+        {
+            ++m_SplitId;
+        }
+
+        for (auto& layer : m_DirectChildren)
+        {
+            auto it = network.find(layer);
+            BOOST_ASSERT_MSG(it != network.end(), "All layers must be part of the topology.");
+            if (it != network.end())
+            {
+                it->second.MarkChildrenSplits(network, m_SplitId, m_IsSelected);
+            }
+        }
+    }
+
+    bool IsInputLayer() const
+    {
+        return m_Layer->GetType() == armnn::LayerType::Input;
+    }
+
+    void CollectNonSelectedInputs(SubGraph::InputSlots& slots,
+                                  const SubGraphSelector::LayerSelectorFunction& selector)
+    {
+        for (auto&& slot = m_Layer->BeginInputSlots(); slot != m_Layer->EndInputSlots(); ++slot)
+        {
+            OutputSlot* parentLayerOutputSlot = slot->GetConnectedOutputSlot();
+            BOOST_ASSERT_MSG(parentLayerOutputSlot != nullptr, "The slots must be connected here.");
+            if (parentLayerOutputSlot)
+            {
+                Layer& parentLayer = parentLayerOutputSlot->GetOwningLayer();
+                if (selector(parentLayer) == false)
+                {
+                    slots.push_back(&(*slot));
+                }
+            }
+        }
+    }
+
+    void CollectNonSelectedOutputSlots(SubGraph::OutputSlots& slots,
+                                       const SubGraphSelector::LayerSelectorFunction& selector)
+    {
+        for (auto&& slot = m_Layer->BeginOutputSlots(); slot != m_Layer->EndOutputSlots(); ++slot)
+        {
+            for (InputSlot* childLayerInputSlot : slot->GetConnections())
+            {
+                Layer& childLayer = childLayerInputSlot->GetOwningLayer();
+                if (selector(childLayer) == false)
+                {
+                    slots.push_back(&(*slot));
+                }
+            }
+        }
+    }
+
+    std::vector<Layer*> m_DirectChildren;
+    Layer* m_Layer;
+    uint32_t m_SplitId;
+    bool m_IsSelected;
+};
+
+} // namespace <anonymous>
+
+SubGraphSelector::SubGraphs
+SubGraphSelector::SelectSubGraphs(Graph& graph,
+                                  const LayerSelectorFunction& selector)
+{
+    LayerSelectionInfo::LayerInfoContainer layerInfo;
+
+    for (auto& layer : graph)
+    {
+        layerInfo.emplace(layer, LayerSelectionInfo{layer, selector});
+    }
+
+    uint32_t splitNo = LayerSelectionInfo::InitialSplitId();
+    for (auto& info : layerInfo)
+    {
+        if (info.second.IsInputLayer())
+        {
+            // for each input layer we mark the graph where subgraph
+            // splits need to happen because of the dependency between
+            // the selected and non-selected nodes
+            info.second.MarkChildrenSplits(layerInfo, splitNo, false);
+        }
+    }
+
+    // Collect all selected layers keyed by split id into a map
+    using SelectionInfoPtrs = std::vector<LayerSelectionInfo*>;
+    std::unordered_map<uint32_t, SelectionInfoPtrs> splitMap;
+    for (auto& info : layerInfo)
+    {
+        if (info.second.m_IsSelected)
+        {
+            auto it = splitMap.find(info.second.m_SplitId);
+            if (it == splitMap.end())
+            {
+                splitMap.insert(std::make_pair(info.second.m_SplitId, SelectionInfoPtrs{&info.second}));
+            }
+            else
+            {
+                it->second.push_back(&info.second);
+            }
+        }
+    }
+
+    // Now each non-empty split id represents a subgraph
+    SubGraphs result;
+    for (auto& splitGraph : splitMap)
+    {
+        if (splitGraph.second.empty() == false)
+        {
+            SubGraph::OutputSlots outputs;
+            SubGraph::InputSlots inputs;
+            SubGraph::Layers layers;
+            for (auto&& infoPtr : splitGraph.second)
+            {
+                infoPtr->CollectNonSelectedOutputSlots(outputs, selector);
+                infoPtr->CollectNonSelectedInputs(inputs, selector);
+                layers.insert(infoPtr->m_Layer);
+            }
+            result.emplace_back(
+                std::make_unique<SubGraph>(
+                    std::move(inputs),
+                    std::move(outputs),
+                    std::move(layers)));
+        }
+    }
+
+    return result;
+}
+
+} // namespace armnn
diff --git a/src/armnn/SubGraphSelector.hpp b/src/armnn/SubGraphSelector.hpp
new file mode 100644
index 0000000000..f96b986a2e
--- /dev/null
+++ b/src/armnn/SubGraphSelector.hpp
@@ -0,0 +1,40 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+#pragma once
+
+#include "SubGraph.hpp"
+#include <functional>
+#include <memory>
+
+namespace armnn
+{
+
+class Layer;
+class Graph;
+
+class SubGraphSelector final
+{
+public:
+    using SubGraphPtr = std::unique_ptr<SubGraph>;
+    using SubGraphs = std::vector<SubGraphPtr>;
+    using LayerSelectorFunction = std::function<bool(const Layer&)>;
+
+    /// Selects subgraphs of a graph based on the selector function
+    /// and the algorithm. Since the SubGraphs returns modifiable pointers
+    /// the input and output slots of the graph:
+    ///  1) the graph cannot be const
+    ///  2) the caller need to make sure that the SubGraphs lifetime is
+    ///     shorter than the graph's
+    static SubGraphs SelectSubGraphs(Graph& graph,
+                                     const LayerSelectorFunction& selector);
+
+private:
+    // this is a utility class, don't construct or copy
+    SubGraphSelector() = delete;
+    SubGraphSelector(const SubGraphSelector&) = delete;
+    SubGraphSelector & operator=(const SubGraphSelector&) = delete;
+};
+
+} // namespace armnn
diff --git a/src/armnn/test/SubGraphTests.cpp b/src/armnn/test/SubGraphTests.cpp
new file mode 100644
index 0000000000..4f8b0a920c
--- /dev/null
+++ b/src/armnn/test/SubGraphTests.cpp
@@ -0,0 +1,587 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+#include <boost/test/unit_test.hpp>
+
+#include <armnn/ArmNN.hpp>
+
+#include <Graph.hpp>
+#include <SubGraph.hpp>
+#include <SubGraphSelector.hpp>
+
+#include <backends/CpuTensorHandle.hpp>
+
+using namespace armnn;
+
+namespace
+{
+
+//
+// this helper only works if all layers where the inputs connect to are not selected
+//
+SubGraph::InputSlots CreateInputsFrom(const std::vector<Layer *> & layers)
+{
+    SubGraph::InputSlots result;
+    for (auto&& layer : layers)
+    {
+        for (auto&& it = layer->BeginInputSlots(); it != layer->EndInputSlots(); ++it)
+        {
+            result.push_back(&(*it));
+        }
+    }
+    return result;
+}
+
+//
+// this helper only works if all layers where the outputs connect to are not selected
+//
+SubGraph::OutputSlots CreateOutputsFrom(const std::vector<Layer *> & layers)
+{
+    SubGraph::OutputSlots result;
+    for (auto && layer : layers)
+    {
+        for (auto&& it = layer->BeginOutputSlots(); it != layer->EndOutputSlots(); ++it)
+        {
+            result.push_back(&(*it));
+        }
+    }
+    return result;
+}
+
+//
+// this takes the inputs, outputs and layers as a copy and the move these copies into the
+// resulting subgraph, so the pass bay value is intentional
+//
+SubGraphSelector::SubGraphPtr CreateSubGraphFrom(SubGraph::InputSlots inputs,
+                                                 SubGraph::OutputSlots outputs,
+                                                 SubGraph::Layers layers)
+{
+    return std::make_unique<SubGraph>(std::move(inputs), std::move(outputs), std::move(layers));
+}
+
+template <typename T, typename Iterator>
+std::vector<T> ToSortedArray(Iterator begin, Iterator end)
+{
+    std::vector<T> result(begin, end);
+    std::sort(result.begin(), result.end());
+    return result;
+}
+
+template <typename T>
+void CompareVectors(const std::vector<T> & result, const std::vector<T> & expected)
+{
+    BOOST_CHECK_EQUAL_COLLECTIONS(result.begin(), result.end(), expected.begin(), expected.end());
+}
+
+void CompareSubGraphs(SubGraphSelector::SubGraphPtr & result,
+                      SubGraphSelector::SubGraphPtr & expected)
+{
+    // expect both to be valid subgraphs
+    BOOST_TEST((result.get() != nullptr));
+    BOOST_TEST((expected.get() != nullptr));
+
+    if (result.get() != nullptr && expected.get() != nullptr)
+    {
+        // try to detect all other obvious errors too, mainly because here
+        // we can get a nicer error message from boost, the collection test
+        // also report error for these
+        BOOST_TEST(result->GetInputSlots().size() == expected->GetInputSlots().size());
+        BOOST_TEST(result->GetOutputSlots().size() == expected->GetOutputSlots().size());
+        BOOST_TEST(result->GetLayers().size() == expected->GetLayers().size());
+
+        auto resultLayers = ToSortedArray<Layer *>(result->GetLayers().begin(),
+                                                   result->GetLayers().end());
+        auto expectedLayers = ToSortedArray<Layer *>(expected->GetLayers().begin(),
+                                                     expected->GetLayers().end());
+        CompareVectors(resultLayers, expectedLayers);
+
+        auto resultInputs = ToSortedArray<InputSlot *>(result->GetInputSlots().begin(),
+                                                       result->GetInputSlots().end());
+        auto expectedInputs = ToSortedArray<InputSlot *>(expected->GetInputSlots().begin(),
+                                                         expected->GetInputSlots().end());
+        CompareVectors(resultInputs, expectedInputs);
+
+        auto resultOutputs = ToSortedArray<OutputSlot *>(result->GetOutputSlots().begin(),
+                                                         result->GetOutputSlots().end());
+        auto expectedOutputs = ToSortedArray<OutputSlot *>(expected->GetOutputSlots().begin(),
+                                                           expected->GetOutputSlots().end());
+        CompareVectors(resultOutputs, expectedOutputs);
+    }
+}
+
+} // namespace <anonymous>
+
+BOOST_AUTO_TEST_SUITE(SubGraphSelection)
+
+BOOST_AUTO_TEST_CASE(NoSubGraphsForNoMatch)
+{
+    Graph graph;
+
+    auto output = graph.AddLayer<OutputLayer>(0, "output");
+    graph.InsertNewLayer<InputLayer>(output->GetInputSlot(0), 0, "input");
+
+    SubGraphSelector::SubGraphs subGraphs =
+        SubGraphSelector::SelectSubGraphs(graph, [](const Layer &) { return false; });
+
+    BOOST_TEST(subGraphs.empty());
+}
+
+BOOST_AUTO_TEST_CASE(OneSubGraphsSelectedASingleMatch)
+{
+    Graph graph;
+
+    auto output = graph.AddLayer<OutputLayer>(0, "output");
+    graph.InsertNewLayer<InputLayer>(output->GetInputSlot(0), 0, "input");
+
+    SubGraphSelector::SubGraphs subGraphs =
+        SubGraphSelector::SelectSubGraphs(
+            graph,
+            // select the output layer only
+            [](const Layer & l)
+            {
+                bool isOutput = l.GetNameStr().compare("output") == 0;
+                return isOutput;
+            });
+
+    BOOST_TEST(subGraphs.size() == 1);
+    if (subGraphs.size() == 1)
+    {
+        auto expected = CreateSubGraphFrom(CreateInputsFrom({output}),
+                                           // outputs of 'output' will be empty
+                                           CreateOutputsFrom({output}),
+                                           {output});
+
+        CompareSubGraphs(subGraphs[0], expected);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(MultipleLayersSelectedInTheMiddle)
+{
+    Graph graph;
+
+    auto output = graph.AddLayer<OutputLayer>(0, "output");
+    auto mid0 = graph.InsertNewLayer<ActivationLayer>(output->GetInputSlot(0),
+                                                      ActivationDescriptor{},
+                                                      "mid0");
+    auto mid1 = graph.InsertNewLayer<ActivationLayer>(mid0->GetInputSlot(0),
+                                                      ActivationDescriptor{},
+                                                      "mid1");
+    graph.InsertNewLayer<InputLayer>(mid1->GetInputSlot(0), 0, "input");
+
+    SubGraphSelector::SubGraphs subGraphs =
+        SubGraphSelector::SelectSubGraphs(
+            graph,
+            // select the middle layers only
+            [](const Layer & l)
+            {
+                bool toSelect = (l.GetType() == LayerType::Activation);
+                return toSelect;
+            });
+
+    BOOST_TEST(subGraphs.size() == 1);
+    if (subGraphs.size() == 1)
+    {
+        auto expected = CreateSubGraphFrom(CreateInputsFrom({mid1}),
+                                           CreateOutputsFrom({mid0}),
+                                           {mid1, mid0});
+
+        CompareSubGraphs(subGraphs[0], expected);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(IslandInTheMiddle)
+{
+    // This case represent the scenario when a non-selected X1 node placed in the middle
+    // of the selected M* nodes:
+    //
+    // X0 -> M1 -> M2 -> M3 -> X2
+    // X0 -> M4 -> X1 -> M5 -> X2
+    //
+    /*
+          X0
+          / \
+        M1   M4
+         |   |
+        M2   X1 < the island in the middle !
+         |   |
+        M3   M5
+          \ /
+          X2
+    */
+    // The expected result for this is that M1,M2,M3,M4 will be part of one subgraph and
+    // M5 will be part of another subgraph and the input and output slots in the subgraphs
+    // will be set accordingly.
+    //
+    Graph graph;
+
+    OriginsDescriptor mergerDescriptor(2);
+    auto x2 = graph.AddLayer<MergerLayer>(mergerDescriptor, "x2");
+    auto m3 = graph.InsertNewLayer<ActivationLayer>(x2->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m3");
+    auto m2 = graph.InsertNewLayer<ActivationLayer>(m3->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m2");
+    auto m1 = graph.InsertNewLayer<ActivationLayer>(m2->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m1");
+    auto x0 = graph.InsertNewLayer<InputLayer>(m1->GetInputSlot(0), 0, "x0");
+
+    auto m5 = graph.InsertNewLayer<ActivationLayer>(x2->GetInputSlot(1),
+                                                    ActivationDescriptor{},
+                                                    "m5");
+    auto x1 = graph.InsertNewLayer<Convolution2dLayer>(m5->GetInputSlot(0),
+                                                       Convolution2dDescriptor{},
+                                                       "x1");
+    auto m4 = graph.InsertNewLayer<ActivationLayer>(x1->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m4");
+
+    // Connect the other branch to the input layer
+    x0->GetOutputSlot(0).Connect(m4->GetInputSlot(0));
+
+    // All selected 'M*' layers will be of Activation type
+    SubGraphSelector::SubGraphs subGraphs =
+        SubGraphSelector::SelectSubGraphs(
+            graph,
+            // select the middle layers only
+            [](const Layer & l)
+            {
+                bool toSelect = (l.GetType() == LayerType::Activation);
+                return toSelect;
+            });
+
+    // expected results to test against
+    auto largerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m1, m4}),
+                                             CreateOutputsFrom({m3, m4}),
+                                             {m1, m4, m2, m3});
+
+    auto smallerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m5}),
+                                              CreateOutputsFrom({m5}),
+                                              {m5});
+
+    BOOST_TEST(subGraphs.size() == 2);
+    if (subGraphs.size() == 2)
+    {
+        // we need to have valid subgraph pointers here
+        BOOST_TEST((subGraphs[0] != nullptr));
+        BOOST_TEST((subGraphs[1] != nullptr));
+
+        if (subGraphs[0].get() != nullptr && subGraphs[1].get() != nullptr)
+        {
+            // sort the subgraphs by layer size, so it is simpler to test
+            std::sort(subGraphs.begin(), subGraphs.end(),
+                [](SubGraphSelector::SubGraphPtr & lhs, SubGraphSelector::SubGraphPtr & rhs)
+                {
+                    return (lhs->GetLayers().size() < rhs->GetLayers().size());
+                }
+            );
+
+            // one subgraph needs to be size=1 and the other one is 4
+            BOOST_TEST(subGraphs[0]->GetLayers().size() == 1);
+            BOOST_TEST(subGraphs[1]->GetLayers().size() == 4);
+
+            CompareSubGraphs(subGraphs[0], smallerSubGraph);
+            CompareSubGraphs(subGraphs[1], largerSubGraph);
+        }
+    }
+}
+
+BOOST_AUTO_TEST_CASE(MultipleSimpleSubGraphs)
+{
+    // This test case represents the scenario when we have two distinct subgraphs
+    // in a simple linear network. The selected nodes are the M* and the
+    // non-selected ones are the X*
+    //
+    // X1 -> M1 -> M2 -> X2 -> M3 -> X3
+    //
+    // The expected results is two subgraphs, one with {M1, M2} and another one
+    // with {M3}
+    //
+    Graph graph;
+
+    // the graph is constructed in reverse order
+    auto x3 = graph.AddLayer<OutputLayer>(0, "output");
+    auto m3 = graph.InsertNewLayer<ActivationLayer>(x3->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m3");
+    auto x2 = graph.InsertNewLayer<Convolution2dLayer>(m3->GetInputSlot(0),
+                                                       Convolution2dDescriptor{},
+                                                       "x2");
+    auto m2 = graph.InsertNewLayer<ActivationLayer>(x2->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m2");
+    auto m1 = graph.InsertNewLayer<ActivationLayer>(m2->GetInputSlot(0),
+                                                    ActivationDescriptor{},
+                                                    "m1");
+    graph.InsertNewLayer<InputLayer>(m1->GetInputSlot(0), 0, "x1");
+
+    // All selected 'M*' layers will be of Activation type
+    SubGraphSelector::SubGraphs subGraphs =
+        SubGraphSelector::SelectSubGraphs(
+            graph,
+            // select the middle layers only
+            [](const Layer & l)
+            {
+                bool toSelect = (l.GetType() == LayerType::Activation);
+                return toSelect;
+            });
+
+    // expected results to test against
+    auto largerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m1}),
+                                             CreateOutputsFrom({m2}),
+                                             {m1, m2});
+
+    auto smallerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m3}),
+                                              CreateOutputsFrom({m3}),
+                                              {m3});
+
+    BOOST_TEST(subGraphs.size() == 2);
+    if (subGraphs.size() == 2)
+    {
+        // we need to have valid subgraph pointers here
+        BOOST_TEST((subGraphs[0] != nullptr));
+        BOOST_TEST((subGraphs[1] != nullptr));
+
+        if (subGraphs[0].get() != nullptr && subGraphs[1].get() != nullptr)
+        {
+            // sort the subgraphs by layer size, so it is simpler to test
+            std::sort(subGraphs.begin(), subGraphs.end(),
+                [](SubGraphSelector::SubGraphPtr & lhs, SubGraphSelector::SubGraphPtr & rhs)
+                {
+                    return (lhs->GetLayers().size() < rhs->GetLayers().size());
+                }
+            );
+
+            BOOST_TEST(subGraphs[0]->GetLayers().size() == 1);
+            BOOST_TEST(subGraphs[1]->GetLayers().size() == 2);
+
+            CompareSubGraphs(subGraphs[0], smallerSubGraph);
+            CompareSubGraphs(subGraphs[1], largerSubGraph);
+        }
+    }
+}
+
+BOOST_AUTO_TEST_CASE(SimpleLinearTest)
+{
+    //X1 -> M1 -> M2 -> X2
+    //Where the input slots of M1 and the output slots of M2 are to be the sub graph boundaries.
+    Graph graph;
+
+    ActivationDescriptor activationDefaults;
+
+    auto layerX1 = graph.AddLayer<InputLayer>(0, "layerX1");
+    auto layerX2 = graph.AddLayer<OutputLayer>(0, "layerX2");
+    auto layerM1 = graph.AddLayer<ActivationLayer>(activationDefaults, "layerM1");
+    auto layerM2 = graph.AddLayer<ActivationLayer>(activationDefaults, "layerM2");
+
+    //      X1
+    //      |
+    //      M1
+    //      |
+    //      M2
+    //      |
+    //      X2
+
+    layerX1->GetOutputSlot(0).Connect(layerM1->GetInputSlot(0));
+    layerM1->GetOutputSlot(0).Connect(layerM2->GetInputSlot(0));
+    layerM2->GetOutputSlot(0).Connect(layerX2->GetInputSlot(0));
+
+    SubGraphSelector::SubGraphs subGraphs =
+            SubGraphSelector::SelectSubGraphs(
+                    graph,
+                    // select the activation layers M1 and M2
+                    [](const Layer & l)
+                    {
+                        bool toSelect = (l.GetType() == LayerType::Activation);
+                        return toSelect;
+                    });
+
+    BOOST_CHECK(subGraphs.size() == 1);
+    if(subGraphs.size() == 1)
+    {
+        auto expected = CreateSubGraphFrom(CreateInputsFrom({layerM1}),
+                                           CreateOutputsFrom({layerM2}),
+                                           {layerM1, layerM2});
+
+        CompareSubGraphs(subGraphs[0], expected);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(MultiInputSingleOutput)
+{
+    //X1 -> M1 -> M3 -> X3
+    //X2 -> M2 -> M3 -> X3
+    //Where the input slots of {M1, M2} and the output slots of M3 are to be the subgraph boundaries.
+    Graph graph;
+
+    ActivationDescriptor activationDefaults;
+
+    auto layerX1 = graph.AddLayer<InputLayer>(0, "layerX1");
+    auto layerX2 = graph.AddLayer<InputLayer>(1, "layerX2");
+    auto layerM1 = graph.AddLayer<ActivationLayer>(activationDefaults, "layerM1");
+    auto layerM2 = graph.AddLayer<ActivationLayer>(activationDefaults, "layerM2");
+    auto layerM3 = graph.AddLayer<AdditionLayer>("layerM3");
+    auto layerX3 = graph.AddLayer<OutputLayer>(0, "layerX3");
+
+    //  X1  X2
+    //  |   |
+    //  M1  M2
+    //   \  |
+    //    \ |
+    //     \|
+    //      M3
+    //      |
+    //      |
+    //      X3
+
+    layerX1->GetOutputSlot(0).Connect(layerM1->GetInputSlot(0));
+    layerX2->GetOutputSlot(0).Connect(layerM2->GetInputSlot(0));
+    layerM1->GetOutputSlot(0).Connect(layerM3->GetInputSlot(0));
+    layerM2->GetOutputSlot(0).Connect(layerM3->GetInputSlot(1));
+    layerM3->GetOutputSlot(0).Connect(layerX3->GetInputSlot(0));
+
+    SubGraphSelector::SubGraphs subGraphs =
+            SubGraphSelector::SelectSubGraphs(
+                    graph,
+                    // select Activation and Addition Layers M1, M2 and M3
+                    [](const Layer & l)
+                    {
+                        bool toSelect = (l.GetType() == LayerType::Activation
+                                         || l.GetType() == LayerType::Addition);
+                        return toSelect;
+                    });
+
+    BOOST_CHECK(subGraphs.size() == 1);
+    if (subGraphs.size() == 1)
+    {
+        auto expected = CreateSubGraphFrom(CreateInputsFrom({layerM1, layerM2}),
+                                           CreateOutputsFrom({layerM3}),
+                                           {layerM1, layerM2, layerM3});
+
+        CompareSubGraphs(subGraphs[0], expected);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(SingleInputMultiOutput)
+{
+    //X1 -> M1 -> M2 -> X2
+    //X1 -> M1 -> M3 -> X3
+    //Where the input slots of M1 and the output slots of {M2, M3} are to be the subgraph boundaries.
+    Graph graph;
+
+    ActivationDescriptor activationDefaults;
+    ViewsDescriptor viewDefaults(2,4);
+
+    Layer* layerX1 = graph.AddLayer<InputLayer>(0, "layerX1");
+    Layer* layerM1 = graph.AddLayer<SplitterLayer>(viewDefaults, "layerM1");
+    Layer* layerM2 = graph.AddLayer<ActivationLayer>(activationDefaults, "layerM2");
+    Layer* layerM3 = graph.AddLayer<ActivationLayer>(activationDefaults, "layerM3");
+    Layer* layerX2 = graph.AddLayer<OutputLayer>(0, "layerX2");
+    Layer* layerX3 = graph.AddLayer<OutputLayer>(1, "layerX3");
+
+    //      X2
+    //      |
+    //      M1
+    //     /|
+    //    / |
+    //   /  |
+    //  M2  M3
+    //  |   |
+    //  |   |
+    //  X2  X3
+
+    layerX1->GetOutputSlot(0).Connect(layerM1->GetInputSlot(0));
+    layerM1->GetOutputSlot(0).Connect(layerM2->GetInputSlot(0));
+    layerM1->GetOutputSlot(1).Connect(layerM3->GetInputSlot(0));
+    layerM2->GetOutputSlot(0).Connect(layerX2->GetInputSlot(0));
+    layerM3->GetOutputSlot(0).Connect(layerX3->GetInputSlot(0));
+
+    SubGraphSelector::SubGraphs subGraphs =
+            SubGraphSelector::SelectSubGraphs(
+                    graph,
+                    // select Activation and Splitter Layers M1, M2 and M3
+                    [](const Layer & l)
+                    {
+                        bool toSelect = (l.GetType() == LayerType::Activation
+                                         || l.GetType() == LayerType::Splitter);
+                        return toSelect;
+                    });
+
+    BOOST_CHECK(subGraphs.size() == 1);
+    if(subGraphs.size() == 1)
+    {
+        auto expected = CreateSubGraphFrom(CreateInputsFrom({layerM1}),
+                                           CreateOutputsFrom({layerM2, layerM3}),
+                                           {layerM1, layerM2, layerM3});
+
+        CompareSubGraphs(subGraphs[0], expected);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(MultiInputMultiOutput)
+{
+    // This case represents the scenario with multiple inputs and multiple outputs
+    //
+    // X1 -> M1 -> M3 -> M4 -> X3
+    // X2 -> M2 -> M3 -> M5 -> X4
+    //
+    // Where the input slots of {M1, M2} and the output slots of {M4, M5} are to be the subgraph
+    // boundaries.
+
+    Graph graph;
+
+    ActivationDescriptor activationDefaults;
+    OriginsDescriptor mergerDescriptor(2);
+
+    auto x1 = graph.AddLayer<InputLayer>(0, "x1");
+    auto x2 = graph.AddLayer<InputLayer>(1, "x2");
+
+    auto m1 = graph.AddLayer<ActivationLayer>(activationDefaults, "m1");
+    auto m2 = graph.AddLayer<ActivationLayer>(activationDefaults, "m2");
+    auto m3 = graph.AddLayer<MergerLayer>(mergerDescriptor, "m3");
+
+    auto m4 = graph.AddLayer<ActivationLayer>(activationDefaults, "m4");
+    auto m5 = graph.AddLayer<ActivationLayer>(activationDefaults, "m5");
+
+    auto x3 = graph.AddLayer<OutputLayer>(0, "x3");
+    auto x4 = graph.AddLayer<OutputLayer>(1, "x4");
+
+    x1->GetOutputSlot(0).Connect(m1->GetInputSlot(0));
+    x2->GetOutputSlot(0).Connect(m2->GetInputSlot(0));
+
+    m1->GetOutputSlot(0).Connect(m3->GetInputSlot(0));
+    m2->GetOutputSlot(0).Connect(m3->GetInputSlot(1));
+
+    m3->GetOutputSlot(0).Connect(m4->GetInputSlot(0));
+    m3->GetOutputSlot(0).Connect(m5->GetInputSlot(0));
+
+    m4->GetOutputSlot(0).Connect(x3->GetInputSlot(0));
+    m5->GetOutputSlot(0).Connect(x4->GetInputSlot(0));
+
+
+    SubGraphSelector::SubGraphs subGraphs =
+        SubGraphSelector::SelectSubGraphs(
+            graph,
+            // select Activation and Merger Layers M1, M2, M3, M4, M5
+            [](const Layer & l)
+            {
+                bool toSelect = (l.GetType() == LayerType::Activation
+                                 || l.GetType() == LayerType::Merger);
+                return toSelect;
+            });
+
+
+    BOOST_CHECK(subGraphs.size() == 1);
+    if (subGraphs.size() == 1)
+    {
+        auto expected = CreateSubGraphFrom(CreateInputsFrom({m1, m2}),
+                                           CreateOutputsFrom({m4, m5}),
+                                           {m1, m2, m3, m4, m5});
+
+        CompareSubGraphs(subGraphs[0], expected);
+    }
+}
+
+BOOST_AUTO_TEST_SUITE_END()