text:
#include "tensorflow/core/grappler/optimizers/loop_optimizer.h"
#include "tensorflow/cc/ops/standard_ops.h"
#include "tensorflow/core/framework/node_def.pb.h"
#include "tensorflow/core/framework/tensor_testutil.h"
#include "tensorflow/core/grappler/grappler_item.h"
#include "tensorflow/core/grappler/inputs/trivial_test_graph_input_yielder.h"
#include "tensorflow/core/grappler/utils.h"
#include "tensorflow/core/grappler/utils/grappler_test.h"
#include "tensorflow/core/lib/core/status_test_util.h"
#include "tensorflow/core/platform/test.h"

namespace tensorflow {
namespace grappler {

class LoopOptimizerTest : public GrapplerTest {
 protected:
  // These helpers always sets T=DT_FLOAT.
  void AddEnterNode(const string& name, const string& frame,
                    const bool is_constant, const int piterations,
                    const std::vector<string>& inputs, GraphDef* graph) const {
    std::vector<std::pair<string, AttrValue>> attributes;
    AttrValue type;
    type.set_type(DT_FLOAT);
    attributes.emplace_back("T", type);
    AttrValue frame_name;
    frame_name.set_s(frame);
    attributes.emplace_back("frame_name", frame_name);
    AttrValue is_const;
    is_const.set_b(is_constant);
    attributes.emplace_back("is_constant", is_const);
    AttrValue parallel_iterations;
    parallel_iterations.set_i(piterations);
    attributes.emplace_back("parallel_iterations", parallel_iterations);
    AddNode(name, "Enter", inputs, attributes, graph);
  }

  void AddSimpleNode(const string& name, const string& op,
                     const std::vector<string>& inputs, GraphDef* graph) const {
    std::vector<std::pair<string, AttrValue>> attributes;
    AttrValue type;
    type.set_type(DT_FLOAT);
    attributes.emplace_back("T", type);
    AddNode(name, op, inputs, attributes, graph);
  }

  void DisableAllStages(LoopOptimizer* optimizer) {
    LoopOptimizer::LoopOptimizerOptions options;
    options.enable_loop_invariant_node_motion = false;
    options.enable_stack_push_removal = false;
    optimizer->options_ = options;
  }

  void EnableOnlyLoopInvariantNodeMotion(LoopOptimizer* optimizer) {
    DisableAllStages(optimizer);
    optimizer->options_.enable_loop_invariant_node_motion = true;
  }

  void EnableOnlyStackPushRemoval(LoopOptimizer* optimizer) {
    DisableAllStages(optimizer);
    optimizer->options_.enable_stack_push_removal = true;
  }
};

TEST_F(LoopOptimizerTest, Basic) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "InvariantEnter"},
                &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"VariantAdd", "Less/y"}, &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"VariantAdd"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).back(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("VariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("VariantAdd")).back(), 0);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("VariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("VariantAdd")).back(), 0);
  }
}

TEST_F(LoopOptimizerTest, Const) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("Const", "Const", {"^Identity"}, &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "Const"}, &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"VariantAdd", "Less/y"}, &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"VariantAdd"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).back(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("Const")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("Const")).back(), 0);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("Const")).size(), 0);
  }
}

TEST_F(LoopOptimizerTest, ControlOutput) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "InvariantEnter"},
                &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"VariantAdd", "Less/y", "^InvariantAdd"},
                &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"VariantAdd"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).back(), 0);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).back(), 0);
  }
}

TEST_F(LoopOptimizerTest, NestedLoop1) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "InvariantEnter"},
                &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"Exit2", "Less/y"}, &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"Exit2"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  AddEnterNode("InvariantEnter2", "while/while/while_context", true, 1,
               {"VariantAdd"}, &graph);
  AddSimpleNode("InvariantAdd2", "Add", {"InvariantEnter2", "InvariantEnter2"},
                &graph);
  AddSimpleNode("VariantAdd2", "Add", {"InvariantAdd2", "Identity2"}, &graph);
  AddEnterNode("VariantEnter2", "while/while/while_context", false, 1,
               {"VariantEnter"}, &graph);
  AddSimpleNode("Merge2", "Merge", {"VariantEnter2", "NextIteration2"}, &graph);
  AddSimpleNode("Less2/y", "Const", {"^Identity2"}, &graph);
  AddSimpleNode("Less2", "Less", {"VariantAdd2", "Less2/y"}, &graph);
  AddSimpleNode("LoopCond2", "LoopCond", {"Less2"}, &graph);
  AddSimpleNode("Switch2", "Switch", {"Merge2", "LoopCond2"}, &graph);
  AddSimpleNode("Identity2", "Identity", {"Switch2:1"}, &graph);
  AddSimpleNode("NextIteration2", "NextIteration", {"VariantAdd2"}, &graph);
  AddSimpleNode("Exit2", "Exit", {"Switch2"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).back(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).back(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).back(), 0);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).back(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).back(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd")).size(), 0);
  }
}

TEST_F(LoopOptimizerTest, NestedLoop2) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "InvariantEnter"},
                &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"Exit2", "Less/y"}, &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"Exit2"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  AddEnterNode("InvariantEnter2", "while/while/while_context", true, 1,
               {"InvariantAdd"}, &graph);
  AddSimpleNode("InvariantAdd2", "Add", {"InvariantEnter2", "InvariantEnter2"},
                &graph);
  AddSimpleNode("VariantAdd2", "Add", {"InvariantAdd2", "Identity2"}, &graph);
  AddEnterNode("VariantEnter2", "while/while/while_context", false, 1,
               {"VariantEnter"}, &graph);
  AddSimpleNode("Merge2", "Merge", {"VariantEnter2", "NextIteration2"}, &graph);
  AddSimpleNode("Less2/y", "Const", {"^Identity2"}, &graph);
  AddSimpleNode("Less2", "Less", {"VariantAdd2", "Less2/y"}, &graph);
  AddSimpleNode("LoopCond2", "LoopCond", {"Less2"}, &graph);
  AddSimpleNode("Switch2", "Switch", {"Merge2", "LoopCond2"}, &graph);
  AddSimpleNode("Identity2", "Identity", {"Switch2:1"}, &graph);
  AddSimpleNode("NextIteration2", "NextIteration", {"VariantAdd2"}, &graph);
  AddSimpleNode("Exit2", "Exit", {"Switch2"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).back(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).back(), 1);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("VariantAdd2")).back(), 1);
  }
}

TEST_F(LoopOptimizerTest, NestedLoopConst1) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "InvariantEnter"},
                &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"Exit2", "Less/y"}, &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"Exit2"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  AddEnterNode("InvariantEnter2", "while/while/while_context", true, 1,
               {"VariantAdd"}, &graph);
  AddSimpleNode("Const2", "Const", {"^Identity2"}, &graph);
  AddSimpleNode("InvariantAdd2", "Add", {"InvariantEnter2", "Const2"}, &graph);
  AddSimpleNode("VariantAdd2", "Add", {"InvariantAdd2", "Identity2"}, &graph);
  AddEnterNode("VariantEnter2", "while/while/while_context", false, 1,
               {"VariantEnter"}, &graph);
  AddSimpleNode("Merge2", "Merge", {"VariantEnter2", "NextIteration2"}, &graph);
  AddSimpleNode("Less2/y", "Const", {"^Identity2"}, &graph);
  AddSimpleNode("Less2", "Less", {"VariantAdd2", "Less2/y"}, &graph);
  AddSimpleNode("LoopCond2", "LoopCond", {"Less2"}, &graph);
  AddSimpleNode("Switch2", "Switch", {"Merge2", "LoopCond2"}, &graph);
  AddSimpleNode("Identity2", "Identity", {"Switch2:1"}, &graph);
  AddSimpleNode("NextIteration2", "NextIteration", {"VariantAdd2"}, &graph);
  AddSimpleNode("Exit2", "Exit", {"Switch2"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).back(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("Const2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("Const2")).back(), 1);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).back(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("Const2")).size(), 1);
    EXPECT_EQ(frames.Frames(*view.GetNode("Const2")).back(), 0);
  }
}

TEST_F(LoopOptimizerTest, NestedLoopConst2) {
  GraphDef graph;
  AddSimpleNode("In", "Identity", {}, &graph);
  AddEnterNode("InvariantEnter", "while/while_context", true, 1, {"In"},
               &graph);
  AddSimpleNode("InvariantAdd", "Add", {"InvariantEnter", "InvariantEnter"},
                &graph);
  AddSimpleNode("VariantAdd", "Add", {"InvariantAdd", "Identity"}, &graph);
  AddEnterNode("VariantEnter", "while/while_context", false, 1, {"In"}, &graph);
  AddSimpleNode("Merge", "Merge", {"VariantEnter", "NextIteration"}, &graph);
  AddSimpleNode("Less/y", "Const", {"^Identity"}, &graph);
  AddSimpleNode("Less", "Less", {"Exit2", "Less/y"}, &graph);
  AddSimpleNode("LoopCond", "LoopCond", {"Less"}, &graph);
  AddSimpleNode("Switch", "Switch", {"Merge", "LoopCond"}, &graph);
  AddSimpleNode("Identity", "Identity", {"Switch:1"}, &graph);
  AddSimpleNode("NextIteration", "NextIteration", {"Exit2"}, &graph);
  AddSimpleNode("Exit", "Exit", {"Switch"}, &graph);
  AddSimpleNode("Out", "Identity", {"Exit"}, &graph);

  AddEnterNode("InvariantEnter2", "while/while/while_context", true, 1,
               {"InvariantAdd"}, &graph);
  AddSimpleNode("Const2", "Const", {"^Identity2"}, &graph);
  AddSimpleNode("InvariantAdd2", "Add", {"InvariantEnter2", "Const2"}, &graph);
  AddSimpleNode("VariantAdd2", "Add", {"InvariantAdd2", "Identity2"}, &graph);
  AddEnterNode("VariantEnter2", "while/while/while_context", false, 1,
               {"VariantEnter"}, &graph);
  AddSimpleNode("Merge2", "Merge", {"VariantEnter2", "NextIteration2"}, &graph);
  AddSimpleNode("Less2/y", "Const", {"^Identity2"}, &graph);
  AddSimpleNode("Less2", "Less", {"VariantAdd2", "Less2/y"}, &graph);
  AddSimpleNode("LoopCond2", "LoopCond", {"Less2"}, &graph);
  AddSimpleNode("Switch2", "Switch", {"Merge2", "LoopCond2"}, &graph);
  AddSimpleNode("Identity2", "Identity", {"Switch2:1"}, &graph);
  AddSimpleNode("NextIteration2", "NextIteration", {"VariantAdd2"}, &graph);
  AddSimpleNode("Exit2", "Exit", {"Switch2"}, &graph);

  GrapplerItem item;
  item.graph = graph;

  LoopOptimizer optimizer;
  EnableOnlyLoopInvariantNodeMotion(&optimizer);
  GraphDef output;
  TF_EXPECT_OK(optimizer.Optimize(nullptr, item, &output));

  {  // Original graph.
    GraphView view(&graph);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).back(), 1);
    ASSERT_EQ(frames.Frames(*view.GetNode("Const2")).size(), 2);
    EXPECT_EQ(frames.Frames(*view.GetNode("Const2")).back(), 1);
  }

  {  // Optimized graph.
    GraphView view(&output);
    FrameView frames;
    TF_EXPECT_OK(frames.InferFromGraphView(view));

    EXPECT_EQ(frames.num_frames(), 2);
    ASSERT_EQ(frames.Frames(*view.GetNode("InvariantAdd2")).size(), 0);
    ASSERT_EQ(frames.Frames(*view.GetNode("Const2")).size(), 0);
  }
}

void VerifyGraphsEqual(const GraphDef& original_graph,
                       const GraphDef& optimized_graph, const string& func) {
  EXPECT_EQ(original_graph.node_size(), optimized_graph.node_size()) << func;
  for (int i = 0; i < original_graph.node_size(); ++i) {
    const NodeDef& original = original_graph.node(i);
    const NodeDef& optimized = optimized_graph.node(i);
    EXPECT_EQ(original.name(), optimized.name()) << func;
    EXPECT_EQ(original.op(), optimized.op()) << func;
    EXPECT_EQ(original.input_size(), optimized.input_size()) << func;
    for (int j = 0; j < original.input_size(); ++j) {
      EXPECT_EQ(original.input(j), optimized.input(j)) << func;
    }
  }
}

TEST_F(LoopOptimizerTest, NoOp) {
  // This trivial graph is so basic there's nothing to optimize.
  TrivialTestGraphInputYielder fake_input(4, 1, 10, false, {"CPU:0"});
  GrapplerItem item;
  CHECK(fake_input.NextItem(&item));

  LoopOptimizer optimizer;
  EnableOnlyStackPushRemoval(&optimizer);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_EXPECT_OK(status);

  VerifyGraphsEqual(item.graph, output, __FUNCTION__);
}

TEST_F(LoopOptimizerTest, RemovePush_NoOp) {
  GrapplerItem item;
  GraphDef& graph = item.graph;
  AddSimpleNode("c", "Const", {}, &graph);
  // Stack with corresponding push/pop.
  AddSimpleNode("stack1", "StackV2", {}, &graph);
  AddSimpleNode("push1", "StackPushV2", {"stack1", "c"}, &graph);
  AddSimpleNode("pop1", "StackPopV2", {"stack1"}, &graph);
  AddSimpleNode("id1", "Identity", {"pop1"}, &graph);
  // Stack with corresponding push/pop behind Enter.
  AddSimpleNode("stack2", "StackV2", {}, &graph);
  AddEnterNode("enter2_c", "frame_name", false, 1, {"c"}, &graph);
  AddEnterNode("enter2_stack2", "frame_name", false, 1, {"stack2"}, &graph);
  AddSimpleNode("push2", "StackPushV2", {"enter2_stack2", "enter2_c"}, &graph);
  AddSimpleNode("pop2", "StackPopV2", {"enter2_stack2"}, &graph);
  AddSimpleNode("id2", "Identity", {"pop2"}, &graph);
  // Stack with unexpected op type in fanout of Stack.
  AddSimpleNode("stack3", "StackV2", {}, &graph);
  AddSimpleNode("push3", "StackPushV2", {"stack3", "c"}, &graph);
  AddSimpleNode("stop", "StopGradient", {"stack3"}, &graph);

  LoopOptimizer optimizer;
  EnableOnlyStackPushRemoval(&optimizer);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_EXPECT_OK(status);
  VerifyGraphsEqual(item.graph, output, __FUNCTION__);
}

TEST_F(LoopOptimizerTest, RemovePush_NoPopButStackLives) {
  GrapplerItem item;
  GraphDef& graph = item.graph;
  AddSimpleNode("c", "Const", {}, &graph);
  // Stack with corresponding push
  AddSimpleNode("stack1", "StackV2", {}, &graph);
  AddSimpleNode("push1", "StackPushV2", {"stack1", "c"}, &graph);
  // Stack with corresponding push behind Enter.
  AddSimpleNode("stack2", "StackV2", {}, &graph);
  AddEnterNode("enter2_c", "frame_name", false, 1, {"c"}, &graph);
  AddEnterNode("enter2_stack2", "frame_name", false, 1, {"stack2"}, &graph);
  AddSimpleNode("push2", "StackPushV2", {"enter2_stack2", "enter2_c"}, &graph);
  item.keep_ops.push_back("stack1");
  item.keep_ops.push_back("stack2");

  LoopOptimizer optimizer;
  EnableOnlyStackPushRemoval(&optimizer);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_EXPECT_OK(status);
  VerifyGraphsEqual(item.graph, output, __FUNCTION__);
}

TEST_F(LoopOptimizerTest, RemovePushWithoutMatchingPop) {
  GrapplerItem item;
  GraphDef& graph = item.graph;
  AddSimpleNode("c", "Const", {}, &graph);
  // Push without Pop.
  AddSimpleNode("stack1", "StackV2", {}, &graph);
  AddSimpleNode("push1", "StackPushV2", {"stack1", "c"}, &graph);
  // Push without Pop behind Enter.
  AddSimpleNode("stack2", "StackV2", {}, &graph);
  AddEnterNode("enter_c", "frame_name", false, 1, {"c"}, &graph);
  AddEnterNode("enter_stack2", "frame_name", false, 1, {"stack2"}, &graph);
  AddSimpleNode("push2", "StackPushV2", {"enter_stack2", "enter_c"}, &graph);
  // Pop without consumer.
  AddSimpleNode("stack3", "StackV2", {}, &graph);
  AddSimpleNode("push3", "StackPushV2", {"stack3", "c"}, &graph);
  AddSimpleNode("pop3", "StackPopV2", {"stack3"}, &graph);
  // Push for a Pop without consumer that is fetched should not be removed.
  AddSimpleNode("stack4", "StackV2", {}, &graph);
  AddSimpleNode("push4", "StackPushV2", {"stack4", "c"}, &graph);
  AddSimpleNode("pop4", "StackPopV2", {"stack4"}, &graph);

  item.fetch.push_back("pop4");

  LoopOptimizer optimizer;
  EnableOnlyStackPushRemoval(&optimizer);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_EXPECT_OK(status);

  EXPECT_EQ(13, output.node_size());
  for (int i = 0; i < output.node_size(); ++i) {
    const NodeDef& node = output.node(i);
    if (node.name() == "push1") {
      EXPECT_EQ("Identity", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("c", node.input(0));
      EXPECT_EQ("^stack1", node.input(1));
    } else if (node.name() == "push2") {
      EXPECT_EQ("Identity", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("enter_c", node.input(0));
      EXPECT_EQ("^enter_stack2", node.input(1));
    } else if (node.name() == "push3") {
      EXPECT_EQ("Identity", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("c", node.input(0));
      EXPECT_EQ("^stack3", node.input(1));
    } else {
      const NodeDef& orig_node = item.graph.node(i);
      EXPECT_EQ(orig_node.ShortDebugString(), node.ShortDebugString());
    }
  }
}

TEST_F(LoopOptimizerTest, RemoveDeadBranches_ConstantCondition) {
  Scope scope = Scope::NewRootScope();
  Output v_in = ops::Variable(scope.WithOpName("v_in"), {3}, DT_FLOAT);

  Output ctrl1 = ops::Const(scope.WithOpName("ctrl1"), false, TensorShape({}));
  ops::Switch s1(scope.WithOpName("switch1"), v_in, ctrl1);
  Output square1 = ops::Square(scope.WithOpName("square1"), s1.output_false);
  Output sqrt1 = ops::Sqrt(scope.WithOpName("sqrt1"), s1.output_true);

  Output ctrl2 = ops::Const(scope.WithOpName("ctrl2"), true, TensorShape({}));
  ops::Switch s2(scope.WithOpName("switch2"), v_in, ctrl2);
  Output square2 = ops::Square(scope.WithOpName("square2"), s2.output_false);
  Output sqrt2 = ops::Sqrt(scope.WithOpName("sqrt2"), s2.output_true);

  Output ctrl3 = ops::Const(scope.WithOpName("ctrl3"), false, TensorShape({}));
  ops::Switch s3(scope.WithOpName("switch3"), v_in, ctrl3);
  Output square3 = ops::Square(scope.WithOpName("square3"), s3.output_false);
  Output sqrt3 = ops::Sqrt(scope.WithOpName("sqrt3"), s3.output_true);

  Output ctrl4 = ops::Const(scope.WithOpName("ctrl4"), false, TensorShape({}));
  ops::Switch s4(scope.WithOpName("switch4"), v_in, ctrl4);
  Output square4 = ops::Square(scope.WithOpName("square4"), s4.output_false);
  Output sqrt4 = ops::Sqrt(scope.WithOpName("sqrt4"), s4.output_true);

  ops::Merge m1(scope.WithOpName("m1"), {square1, sqrt1});
  ops::Merge m2(scope.WithOpName("m2"), {v_in, square1});
  ops::Merge m3(scope.WithOpName("m3"), {v_in, sqrt1});
  ops::Merge m4(scope.WithOpName("m4"), {square1, sqrt2});
  ops::Merge m5(scope.WithOpName("m5"), {square2, sqrt1});
  ops::Merge m6(scope.WithOpName("m6").WithControlDependencies(sqrt2),
                {v_in, square1});
  ops::Merge m7(scope.WithOpName("m7").WithControlDependencies(sqrt1),
                {v_in, square1});

  ops::Switch s5(scope.WithOpName("switch5"), v_in, ctrl1);
  Output id1 = ops::Identity(scope.WithOpName("id1"), s5.output_false);
  Output id2 = ops::Identity(scope.WithOpName("id2"), s5.output_true);
  ops::Merge m8(scope.WithOpName("m8"), {id1, id2});

  ops::Switch s6(scope.WithOpName("switch6"), v_in, ctrl1);
  Output id3 = ops::Identity(scope.WithOpName("id3"), s6.output_false);
  Output id4 = ops::Identity(scope.WithOpName("id4"), s6.output_true);
  ops::Merge m9(scope.WithOpName("m9"), {id3, id4});

  GrapplerItem item;
  item.fetch.push_back("m8");
  item.fetch.push_back("id4");

  TF_CHECK_OK(scope.ToGraphDef(&item.graph));

  LoopOptimizer optimizer(RewriterConfig::AGGRESSIVE, nullptr);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_CHECK_OK(status);

  for (const NodeDef& node : output.node()) {
    // These nodes should have been pruned
    EXPECT_NE("Square1", node.name());
    EXPECT_NE("Sqrt2", node.name());
    EXPECT_NE("m5", node.name());
    EXPECT_NE("m7", node.name());

    if (node.name() == "m1") {
      // sqrt1 is dead
      EXPECT_EQ("Identity", node.op());
      EXPECT_EQ(1, node.input_size());
      EXPECT_EQ("square1", node.input(0));
    } else if (node.name() == "m2") {
      // both inputs are alive
      EXPECT_EQ("Merge", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("v_in", node.input(0));
      EXPECT_EQ("square1", node.input(1));
    } else if (node.name() == "m3") {
      // sqrt1 is dead
      EXPECT_EQ("Identity", node.op());
      EXPECT_EQ(1, node.input_size());
      EXPECT_EQ("v_in", node.input(0));
    } else if (node.name() == "m4") {
      // both inputs are alive
      EXPECT_EQ("Merge", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("square1", node.input(0));
      EXPECT_EQ("sqrt2", node.input(1));
    } else if (node.name() == "m6") {
      // both inputs are alive and the control dependency can get triggered
      EXPECT_EQ("Merge", node.op());
      EXPECT_EQ(3, node.input_size());
      EXPECT_EQ("v_in", node.input(0));
      EXPECT_EQ("square1", node.input(1));
      EXPECT_EQ("^sqrt2", node.input(2));
    } else if (node.name() == "m8") {
      // The node is to be preserved because of a fetch
      EXPECT_EQ("Merge", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("id1", node.input(0));
      EXPECT_EQ("id2", node.input(1));
    } else if (node.name() == "m9") {
      // The node is to be preserved because of a fetch
      EXPECT_EQ("Merge", node.op());
      EXPECT_EQ(2, node.input_size());
      EXPECT_EQ("id3", node.input(0));
      EXPECT_EQ("id4", node.input(1));
    }
  }
}

TEST_F(LoopOptimizerTest, RemoveDeadBranches_FullyRemoveDeadBranches) {
  const string gdef_ascii = R"EOF(
node {
  name: "episodicreplaybuffer_add_readvariableop_resource"
  op: "_Arg"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_RESOURCE
    }
  }
  attr {
    key: "index"
    value {
      i: 0
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/and_1/x"
  op: "Const"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_BOOL
        tensor_shape {
        }
        bool_val: true
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/begin_episode"
  op: "Const"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_BOOL
        tensor_shape {
        }
        bool_val: false
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Switch"
  op: "Switch"
  input: "EpisodicReplayBuffer/add/and_1/x"
  input: "EpisodicReplayBuffer/add/and_1/x"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/NoOp"
  op: "NoOp"
  input: "^EpisodicReplayBuffer/add/and_1/x"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert/Switch"
  op: "Switch"
  input: "EpisodicReplayBuffer/add/and_1/x"
  input: "EpisodicReplayBuffer/add/and_1/x"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "_class"
    value {
      list {
        s: "loc:@EpisodicReplayBuffer/add/assert_equal/All"
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert/Switch_1"
  op: "Switch"
  input: "EpisodicReplayBuffer/add/begin_episode"
  input: "EpisodicReplayBuffer/add/and_1/x"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "_class"
    value {
      list {
        s: "loc:@EpisodicReplayBuffer/add/begin_episode"
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert/Switch_2"
  op: "Switch"
  input: "EpisodicReplayBuffer/add/begin_episode"
  input: "EpisodicReplayBuffer/add/and_1/x"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "_class"
    value {
      list {
        s: "loc:@EpisodicReplayBuffer/add/end_episode"
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/switch_f"
  op: "Identity"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Switch"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/control_dependency"
  op: "Const"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/NoOp"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_BOOL
        tensor_shape {
        }
        tensor_content: "\001"
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert"
  op: "Assert"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert/Switch"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert/Switch_1"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert/Switch_2"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      list {
        type: DT_BOOL
        type: DT_BOOL
      }
    }
  }
  attr {
    key: "summarize"
    value {
      i: 3
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/control_dependency_1"
  op: "Identity"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/switch_f"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
  attr {
    key: "_class"
    value {
      list {
        s: "loc:@EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/switch_f"
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Merge"
  op: "Merge"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/control_dependency_1"
  input: "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/control_dependency"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Assert"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "N"
    value {
      i: 2
    }
  }
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/FloorMod/y"
  op: "Const"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Merge"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_INT64
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_INT64
        tensor_shape {
        }
        int64_val: 5000
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/ReadVariableOp"
  op: "ReadVariableOp"
  input: "episodicreplaybuffer_add_readvariableop_resource"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Merge"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_INT64
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/Less/y"
  op: "Const"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Merge"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_INT64
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_INT64
        tensor_shape {
        }
        int64_val: 0
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/Less"
  op: "Less"
  input: "EpisodicReplayBuffer/add/ReadVariableOp"
  input: "EpisodicReplayBuffer/add/Less/y"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_INT64
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/or"
  op: "LogicalOr"
  input: "EpisodicReplayBuffer/add/begin_episode"
  input: "EpisodicReplayBuffer/add/Less"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
}
node {
  name: "EpisodicReplayBuffer/add/get_episode_id/pred_id"
  op: "Identity"
  input: "EpisodicReplayBuffer/add/or"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/get_episode_id/Switch"
  op: "Switch"
  input: "EpisodicReplayBuffer/add/or"
  input: "EpisodicReplayBuffer/add/or"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_BOOL
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/get_episode_id/critical_section_execute/AssignVariableOp/Switch"
  op: "Switch"
  input: "episodicreplaybuffer_add_readvariableop_resource"
  input: "EpisodicReplayBuffer/add/get_episode_id/pred_id"
  input: "^EpisodicReplayBuffer/add/ReadVariableOp"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "T"
    value {
      type: DT_RESOURCE
    }
  }
  attr {
    key: "_class"
    value {
      list {
        s: "loc:@EpisodicReplayBuffer/add/ReadVariableOp/resource"
      }
    }
  }
}
node {
  name: "EpisodicReplayBuffer/add/get_episode_id/critical_section_execute/ReadVariableOp_3"
  op: "ReadVariableOp"
  input: "^EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Merge"
  device: "/job:localhost/replica:0/task:0/device:CPU:0"
  attr {
    key: "dtype"
    value {
      type: DT_INT64
    }
  }
}
library {
}
versions {
  producer: 27
}
  )EOF";

  GrapplerItem item;
  CHECK(protobuf::TextFormat::ParseFromString(gdef_ascii, &item.graph));
  item.fetch = {
      "EpisodicReplayBuffer/add/get_episode_id/critical_section_execute/"
      "ReadVariableOp_3"};

  LoopOptimizer optimizer(RewriterConfig::AGGRESSIVE, nullptr);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_CHECK_OK(status);

  bool found_merge = false;
  for (const auto& node : output.node()) {
    if (node.name() ==
        "EpisodicReplayBuffer/add/assert_equal/Assert/AssertGuard/Merge") {
      found_merge = true;
    }
  }

  EXPECT_TRUE(found_merge)
      << "Merge node was deleted, but it shouldn't have been.";
}

TEST_F(LoopOptimizerTest, RemoveDeadBranches_ZeroIterWhile) {
  const string gdef_ascii = R"EOF(
node {
  name: "Const"
  op: "Const"
  attr {
    key: "dtype"
    value {
      type: DT_INT32
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_INT32
        tensor_shape {
        }
        int_val: 20
      }
    }
  }
}
node {
  name: "while/Enter"
  op: "Enter"
  input: "Const"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
  attr {
    key: "frame_name"
    value {
      s: "while/while/"
    }
  }
  attr {
    key: "is_constant"
    value {
      b: false
    }
  }
  attr {
    key: "parallel_iterations"
    value {
      i: 1
    }
  }
}
node {
  name: "while/Merge"
  op: "Merge"
  input: "while/Enter"
  input: "while/NextIteration"
  attr {
    key: "N"
    value {
      i: 2
    }
  }
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
}
node {
  name: "while/Less/y"
  op: "Const"
  input: "^while/Merge"
  attr {
    key: "dtype"
    value {
      type: DT_INT32
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_INT32
        tensor_shape {
        }
        int_val: 10
      }
    }
  }
}
node {
  name: "while/Less"
  op: "Less"
  input: "while/Merge"
  input: "while/Less/y"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
}
node {
  name: "while/LoopCond"
  op: "LoopCond"
  input: "while/Less"
}
node {
  name: "while/Switch"
  op: "Switch"
  input: "while/Merge"
  input: "while/LoopCond"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
  attr {
    key: "_class"
    value {
      list {
        s: "loc:@while/Merge"
      }
    }
  }
}
node {
  name: "while/Identity"
  op: "Identity"
  input: "while/Switch:1"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
}
node {
  name: "while/add/y"
  op: "Const"
  input: "^while/Identity"
  attr {
    key: "dtype"
    value {
      type: DT_INT32
    }
  }
  attr {
    key: "value"
    value {
      tensor {
        dtype: DT_INT32
        tensor_shape {
        }
        int_val: 1
      }
    }
  }
}
node {
  name: "while/add"
  op: "Add"
  input: "while/Identity"
  input: "while/add/y"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
}
node {
  name: "while/NextIteration"
  op: "NextIteration"
  input: "while/add"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
}
node {
  name: "while/Exit"
  op: "Exit"
  input: "while/Switch"
  attr {
    key: "T"
    value {
      type: DT_INT32
    }
  }
}
versions {
  producer: 21
}
  )EOF";

  GrapplerItem item;
  CHECK(protobuf::TextFormat::ParseFromString(gdef_ascii, &item.graph));
  item.fetch = {"while/Exit"};
  auto tensors_expected = EvaluateNodes(item.graph, item.fetch);
  EXPECT_EQ(1, tensors_expected.size());

  LoopOptimizer optimizer(RewriterConfig::AGGRESSIVE, nullptr);
  GraphDef output;
  Status status = optimizer.Optimize(nullptr, item, &output);
  TF_CHECK_OK(status);
  auto tensors_got = EvaluateNodes(output, item.fetch);
  EXPECT_EQ(1, tensors_got.size());
  test::ExpectTensorEqual<int32>(tensors_expected[0], tensors_got[0]);

  int nodes_present = 0;
  for (const NodeDef& node : output.node()) {
    // All nodes connected to Switch's positive check should be pruned.
    if (node.name() == "while/add") {
      LOG(ERROR) << "while/add is present after optimization";
    } else if (node.name() == "while/add/y") {
      LOG(ERROR) << "while/add/y is present after optimization";
    } else if (node.name() == "while/NextIteration") {
      LOG(ERROR) << "while/NextIteration is present after optimization";
    } else if (node.name() == "while/Identity") {
      LOG(ERROR) << "while/Identity is present after optimization";
    }
    ++nodes_present;
  }
  EXPECT_EQ(8, nodes_present);
}

}  // namespace grappler
}  // namespace tensorflow


text:
package org.apache.asterix.test.runtime;

import static org.mockito.Mockito.mock;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import org.apache.asterix.common.annotations.MissingNullInOutFunction;
import org.apache.asterix.om.functions.BuiltinFunctions;
import org.apache.asterix.om.functions.IFunctionDescriptor;
import org.apache.asterix.om.functions.IFunctionDescriptorFactory;
import org.apache.asterix.om.types.ATypeTag;
import org.apache.asterix.om.types.BuiltinType;
import org.apache.asterix.om.types.IAType;
import org.apache.asterix.runtime.evaluators.base.AbstractScalarFunctionDynamicDescriptor;
import org.apache.asterix.runtime.functions.FunctionCollection;
import org.apache.hyracks.algebricks.common.utils.Pair;
import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
import org.apache.hyracks.algebricks.runtime.base.IEvaluatorContext;
import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluator;
import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluatorFactory;
import org.apache.hyracks.algebricks.runtime.evaluators.ConstantEvalFactory;
import org.apache.hyracks.data.std.api.IPointable;
import org.apache.hyracks.data.std.primitive.VoidPointable;
import org.apache.logging.log4j.Level;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.junit.Assert;
import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameter;
import org.junit.runners.Parameterized.Parameters;

/**
 * This test goes through all the functions that should respect the "missing/null in -> missing/null out" behavior
 * and ensures they respect that rule
 */

@RunWith(Parameterized.class)
public class NullMissingTest {

    private static final Logger LOGGER = LogManager.getLogger();

    // those are the functions that need IATypes of their args and use them in the function constructor
    private static Set<FunctionIdentifier> functionsRequiringTypes = new HashSet<>();

    @Parameters(name = "NullMissingTest {index}: {0}")
    public static Collection<Object[]> tests() {
        List<Object[]> tests = new ArrayList<>();

        // Get all the functions
        List<IFunctionDescriptorFactory> functions =
                FunctionCollection.createDefaultFunctionCollection().getFunctionDescriptorFactories();

        // Build the tests
        for (IFunctionDescriptorFactory functionFactory : functions) {
            String className = functionFactory.getClass().getName();
            IFunctionDescriptor functionDescriptor = functionFactory.createFunctionDescriptor();

            // Include only functions annotated with MissingNullInOutFunction
            if (functionDescriptor.getClass().isAnnotationPresent(MissingNullInOutFunction.class)) {

                // We test all functions except record, cast and full-text contains functions,
                // which requires type settings or argument settings.
                // Instead, we test them in runtime tests.
                if (!className.contains("record") && !className.contains("Cast")
                        && !className.contains("FullTextContains")) {
                    tests.add(new Object[] { getTestName(functionDescriptor.getClass()), functionDescriptor });
                } else {
                    LOGGER.log(Level.INFO, "Excluding " + className);
                }
            } else {
                LOGGER.log(Level.INFO, "Excluding " + className);
            }
        }
        return tests;
    }

    private static String getTestName(Class<?> clazz) {
        if (clazz.getEnclosingClass() != null) {
            return clazz.getEnclosingClass().getSimpleName();
        } else if (clazz.getSimpleName().contains("$$Lambda")) {
            return clazz.getSimpleName().replaceAll("\\$\\$Lambda.*", "");
        } else {
            return clazz.getSimpleName();
        }
    }

    @Parameter
    public String testName;

    @Parameter(1)
    public IFunctionDescriptor functionDescriptor;

    @Test
    public void test() throws Exception {
        String className = functionDescriptor.getClass().getName();
        LOGGER.log(Level.INFO, "Testing " + className);

        // Get the arguments combinations
        AbstractScalarFunctionDynamicDescriptor funcDesc = (AbstractScalarFunctionDynamicDescriptor) functionDescriptor;
        int inputArity = funcDesc.getIdentifier().getArity();
        Iterator<Pair<IScalarEvaluatorFactory[], IAType[]>> argEvalFactoryIterator = getArgCombinations(inputArity);
        int index = 0;

        // Test is happening here
        while (argEvalFactoryIterator.hasNext()) {
            Pair<IScalarEvaluatorFactory[], IAType[]> argumentsAndTypesPair = argEvalFactoryIterator.next();

            // Set the IAType if it's needed
            if (functionsRequiringTypes.contains(funcDesc.getIdentifier())) {
                funcDesc.setImmutableStates((Object[]) argumentsAndTypesPair.second);
            }

            // Evaluate
            IScalarEvaluatorFactory evalFactory = funcDesc.createEvaluatorFactory(argumentsAndTypesPair.first);
            IEvaluatorContext ctx = mock(IEvaluatorContext.class);
            IScalarEvaluator evaluator = evalFactory.createScalarEvaluator(ctx);
            IPointable resultPointable = new VoidPointable();
            evaluator.evaluate(null, resultPointable);

            // Result checks
            if (index != 0) {
                Assert.assertEquals(ATypeTag.SERIALIZED_MISSING_TYPE_TAG,
                        resultPointable.getByteArray()[resultPointable.getStartOffset()]);
            } else {
                Assert.assertEquals(ATypeTag.SERIALIZED_NULL_TYPE_TAG,
                        resultPointable.getByteArray()[resultPointable.getStartOffset()]);
            }
            ++index;
        }
    }

    // Generates combinations of arguments and their type
    private Iterator<Pair<IScalarEvaluatorFactory[], IAType[]>> getArgCombinations(int inputArity) {
        int argSize = inputArity >= 0 ? inputArity : 3;
        final int numCombinations = 1 << argSize;
        return new Iterator<Pair<IScalarEvaluatorFactory[], IAType[]>>() {
            private int index = 0;

            @Override
            public boolean hasNext() {
                return index < numCombinations;
            }

            @Override
            public Pair<IScalarEvaluatorFactory[], IAType[]> next() {
                IAType[] argumentTypes = new IAType[argSize];
                IScalarEvaluatorFactory[] scalarEvaluatorFactories = new IScalarEvaluatorFactory[argSize];

                for (int j = 0; j < argSize; ++j) {
                    if ((index & (1 << j)) != 0) {
                        argumentTypes[j] = BuiltinType.AMISSING;
                        scalarEvaluatorFactories[j] =
                                new ConstantEvalFactory(new byte[] { ATypeTag.SERIALIZED_MISSING_TYPE_TAG });
                    } else {
                        argumentTypes[j] = BuiltinType.ANULL;
                        scalarEvaluatorFactories[j] =
                                new ConstantEvalFactory(new byte[] { ATypeTag.SERIALIZED_NULL_TYPE_TAG });
                    }
                }
                ++index;
                return new Pair<>(scalarEvaluatorFactories, argumentTypes);
            }
        };
    }

    // Functions that require the IAType for their test
    @BeforeClass
    public static void buildFunctionsRequiringType() {
        // Those are the functions that need IATypes of their args and use them in the function constructor
        functionsRequiringTypes.add(BuiltinFunctions.ARRAY_POSITION);
        functionsRequiringTypes.add(BuiltinFunctions.ARRAY_CONTAINS);
        functionsRequiringTypes.add(BuiltinFunctions.ARRAY_SORT);
        functionsRequiringTypes.add(BuiltinFunctions.ARRAY_DISTINCT);
        functionsRequiringTypes.add(BuiltinFunctions.ARRAY_EXCEPT);
        functionsRequiringTypes.add(BuiltinFunctions.EQ);
        functionsRequiringTypes.add(BuiltinFunctions.LT);
        functionsRequiringTypes.add(BuiltinFunctions.GT);
        functionsRequiringTypes.add(BuiltinFunctions.GE);
        functionsRequiringTypes.add(BuiltinFunctions.LE);
        functionsRequiringTypes.add(BuiltinFunctions.NEQ);
        functionsRequiringTypes.add(BuiltinFunctions.MISSING_IF);
        functionsRequiringTypes.add(BuiltinFunctions.NAN_IF);
        functionsRequiringTypes.add(BuiltinFunctions.NEGINF_IF);
        functionsRequiringTypes.add(BuiltinFunctions.NULL_IF);
        functionsRequiringTypes.add(BuiltinFunctions.POSINF_IF);
    }
}

redpajama_set_name: RedPajamaGithub


text:
Master: [![Build Status](https://travis-ci.org/sansible/kibana.svg?branch=master)](https://travis-ci.org/sansible/kibana)
Develop: [![Build Status](https://travis-ci.org/sansible/kibana.svg?branch=develop)](https://travis-ci.org/sansible/kibana)

* [Installation and Dependencies](#installation-and-dependencies)
* [Tags](#tags)
* [Examples](#examples)

This role installs Kibana.

For more information on Kibana please visit [elastic kibana](https://www.elastic.co/products/kibana).

**Note** Supports Kibana 4

## Installation and Dependencies

To install run `ansible-galaxy install sansible.kibana` or add this to your
`roles.yml`

```YAML
- name: sansible.kibana
  version: v2.0
```

and run `ansible-galaxy install -p ./roles -r roles.yml`

## Tags

This role uses two tags: **build** and **configure**

* `build` - Installs Kibana and all its dependencies.
* `configure` - Configure and ensures that the Kibana service is running.

## Examples

To install the defaul version (4.1.2):

```YAML
- name: Kibana
  hosts: "{{ hosts }}"

  roles:
    - role: kibana
```

To install RC 5

```YAML
- name: Kibana
  hosts: "{{ hosts }}"

  roles:
    - role: kibana
      sansible_kibana_tarball: "kibana-5.0.0-rc1-linux-x86_64"
      sansible_kibana_download_base_url: https://artifacts.elastic.co/downloads/kibana/
      sansible_kibana_version: 5.0.0-rc1
```

To install a specific version:

```YAML
- name: Kibana
  hosts: "{{ hosts }}"

  roles:
    - role: kibana
      kibana:
      sansible_kibana_tarball: kibana-4.5.2-linux-x64
      sansible_kibana_version: 4.5.2
```


text:
<?php
declare(strict_types=1);

namespace Firehed\U2F;

use Exception;

class SecurityException extends Exception
{
    const SIGNATURE_INVALID = 1;
    const COUNTER_USED = 2;
    const CHALLENGE_MISMATCH = 3;
    const KEY_HANDLE_UNRECOGNIZED = 4;
    const NO_TRUSTED_CA = 5;
    const WRONG_RELYING_PARTY = 6;

    const MESSAGES = [
        self::SIGNATURE_INVALID => 'Signature verification failed',
        self::COUNTER_USED =>
            'Response counter value is too low, indicating a possible replay '.
            'attack or cloned token. It is also possible but unlikely that '.
            'the token\'s internal counter wrapped around. This token should '.
            'be invalidated or flagged for review.',
        self::CHALLENGE_MISMATCH => 'Response challenge does not match request',
        self::KEY_HANDLE_UNRECOGNIZED => 'Key handle has not been registered',
        self::NO_TRUSTED_CA => 'The attestation certificate was not signed by any trusted Certificate Authority',
        self::WRONG_RELYING_PARTY => 'Relying party invalid for this server',
    ];

    public function __construct(int $code)
    {
        parent::__construct(self::MESSAGES[$code] ?? '', $code);
    }
}


text:
/*
 * $Revision: 2552 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
 ***************************************************************/

/** \file
 * \brief Implementation of class Multlevel (used by FMMMLayout).
 *
 * \author Stefan Hachul
 *
 * \par License:
 * This file is part of the Open Graph Drawing Framework (OGDF).
 *
 * \par
 * Copyright (C)<br>
 * See README.txt in the root directory of the OGDF installation for details.
 *
 * \par
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * Version 2 or 3 as published by the Free Software Foundation;
 * see the file LICENSE.txt included in the packaging of this file
 * for details.
 *
 * \par
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * \par
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free
 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 * \see  http://www.gnu.org/copyleft/gpl.html
 ***************************************************************/

#include "Multilevel.h"
#include "Set.h"
#include "Node.h"
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Math.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/energybased/FMMMLayout.h>

namespace ogdf {

void Multilevel::create_multilevel_representations(
	Graph& G,
	NodeArray<NodeAttributes>& A,
	EdgeArray<EdgeAttributes>& E,
	int rand_seed,
	int galaxy_choice,
	int min_Graph_size,
	int random_tries,
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray <NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int & max_level)
{
	//make initialisations;
	srand(rand_seed);
	G_mult_ptr[0] = &G; //init graph at level 0 to the original undirected simple
	A_mult_ptr[0] = &A; //and loopfree connected graph G/A/E
	E_mult_ptr[0] = &E;

	int bad_edgenr_counter = 0;
	int act_level = 0;
	Graph* act_Graph_ptr = G_mult_ptr[0];

	while( (act_Graph_ptr->numberOfNodes() > min_Graph_size) &&
		edgenumbersum_of_all_levels_is_linear(G_mult_ptr,act_level,bad_edgenr_counter) )
	{
		Graph* G_new = new (Graph);
		NodeArray<NodeAttributes>* A_new = OGDF_NEW NodeArray<NodeAttributes>;
		EdgeArray<EdgeAttributes>* E_new = OGDF_NEW EdgeArray<EdgeAttributes>;
		G_mult_ptr[act_level+1] = G_new;
		A_mult_ptr[act_level+1] = A_new;
		E_mult_ptr[act_level+1] = E_new;

		init_multilevel_values(G_mult_ptr,A_mult_ptr,E_mult_ptr,act_level);
		partition_galaxy_into_solar_systems(G_mult_ptr,A_mult_ptr,E_mult_ptr,rand_seed,
			galaxy_choice,random_tries,act_level);
		collaps_solar_systems(G_mult_ptr,A_mult_ptr,E_mult_ptr,act_level);

		act_level++;
		act_Graph_ptr = G_mult_ptr[act_level];
	}
	max_level = act_level;
}

bool Multilevel::edgenumbersum_of_all_levels_is_linear(
	Array<Graph*> &G_mult_ptr,
	int act_level,
	int& bad_edgenr_counter)
{
	if(act_level == 0)
		return true;
	else
	{
		if(G_mult_ptr[act_level]->numberOfEdges()<=
			0.8 * double (G_mult_ptr[act_level-1]->numberOfEdges()))
			return true;
		else if(bad_edgenr_counter < 5)
		{
			bad_edgenr_counter++;
			return true;
		}
		else
			return false;
	}
}

inline void  Multilevel::init_multilevel_values(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int level)
{
	node v;
	forall_nodes(v,*G_mult_ptr[level])
		(*A_mult_ptr[level])[v].init_mult_values();

	edge e;
	forall_edges(e,*G_mult_ptr[level])
		(*E_mult_ptr[level])[e].init_mult_values();
}

inline void Multilevel::partition_galaxy_into_solar_systems(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int rand_seed,
	int galaxy_choice,
	int random_tries,
	int act_level)
{
	create_suns_and_planets(G_mult_ptr, A_mult_ptr, E_mult_ptr, rand_seed, galaxy_choice,
		random_tries, act_level);
	create_moon_nodes_and_pm_nodes(G_mult_ptr, A_mult_ptr, E_mult_ptr, act_level);
}

void Multilevel::create_suns_and_planets(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int rand_seed,
	int galaxy_choice,
	int random_tries,
	int act_level)
{
	Set Node_Set;
	node v, sun_node, planet_node, newNode, pos_moon_node;
	edge sun_edge, e;
	double dist_to_sun;
	List<node> planet_nodes;
	List<node> sun_nodes;

	//make initialisations
	sun_nodes.clear();
	Node_Set.set_seed(rand_seed); //set seed for random number generator
	forall_nodes(v,*G_mult_ptr[act_level])
		if(act_level == 0) (*A_mult_ptr[act_level])[v].set_mass(1);
	if(galaxy_choice == FMMMLayout::gcUniformProb)
		Node_Set.init_node_set(*G_mult_ptr[act_level]);
	else //galaxy_choice != gcUniformProb in FMMMLayout
		Node_Set.init_node_set(*G_mult_ptr[act_level],*A_mult_ptr[act_level]);

	while (!Node_Set.empty_node_set())
	{//while
		//randomly select a sun node
		planet_nodes.clear();
		if(galaxy_choice == FMMMLayout::gcUniformProb)
			sun_node = Node_Set.get_random_node();
		else if (galaxy_choice == FMMMLayout::gcNonUniformProbLowerMass)
			sun_node = Node_Set.get_random_node_with_lowest_star_mass(random_tries);
		else //galaxy_choice == FMMMLayout::gcNonUniformProbHigherMass
			sun_node = Node_Set.get_random_node_with_highest_star_mass(random_tries);
		sun_nodes.pushBack(sun_node);

		//create new node at higher level that represents the collapsed solar_system
		newNode = G_mult_ptr[act_level+1]->newNode();

		//update information for sun_node
		(*A_mult_ptr[act_level])[sun_node].set_higher_level_node(newNode);
		(*A_mult_ptr[act_level])[sun_node].set_type(1);
		(*A_mult_ptr[act_level])[sun_node].set_dedicated_sun_node(sun_node);
		(*A_mult_ptr[act_level])[sun_node].set_dedicated_sun_distance(0);

		//update information for planet_nodes
		forall_adj_edges(sun_edge,sun_node)
		{
			dist_to_sun = (*E_mult_ptr[act_level])[sun_edge].get_length();
			if (sun_edge->source() != sun_node)
				planet_node = sun_edge->source();
			else
				planet_node =  sun_edge->target();
			(*A_mult_ptr[act_level])[planet_node].set_type(2);
			(*A_mult_ptr[act_level])[planet_node].set_dedicated_sun_node(sun_node);
			(*A_mult_ptr[act_level])[planet_node].set_dedicated_sun_distance(dist_to_sun);
			planet_nodes.pushBack(planet_node);
		}

		//delete all planet_nodes and possible_moon_nodes from Node_Set

		ListConstIterator<node> planet_node_ptr;
		//forall_listiterators(node,planet_node_ptr,planet_nodes)
		for(planet_node_ptr = planet_nodes.begin(); planet_node_ptr.valid(); ++planet_node_ptr)
			if(!Node_Set.is_deleted(*planet_node_ptr))
				Node_Set.delete_node(*planet_node_ptr);

		for(planet_node_ptr = planet_nodes.begin(); planet_node_ptr.valid(); ++planet_node_ptr)
			//forall_listiterators(node,planet_node_ptr,planet_nodes)
		{
			forall_adj_edges(e,*planet_node_ptr)
			{
				if(e->source() == *planet_node_ptr)
					pos_moon_node = e->target();
				else
					pos_moon_node = e->source();
				if(!Node_Set.is_deleted(pos_moon_node))
					Node_Set.delete_node(pos_moon_node);
			}
		}
	}//while

	//init *A_mult_ptr[act_level+1] and set NodeAttributes information for new nodes
	A_mult_ptr[act_level+1]->init(*G_mult_ptr[act_level+1]);
	forall_listiterators(node, sun_node_ptr, sun_nodes)
	{
		newNode = (*A_mult_ptr[act_level])[*sun_node_ptr].get_higher_level_node();
		(*A_mult_ptr[act_level+1])[newNode].set_NodeAttributes((*A_mult_ptr[act_level])
			[*sun_node_ptr].get_width(),
			(*A_mult_ptr[act_level])
			[*sun_node_ptr].get_height(),
			(*A_mult_ptr[act_level])
			[*sun_node_ptr].get_position(),
			*sun_node_ptr,NULL);
		(*A_mult_ptr[act_level+1])[newNode].set_mass(0);
	}
}

void Multilevel::create_moon_nodes_and_pm_nodes(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int act_level)
{
	edge e;
	node v, nearest_neighbour_node, neighbour_node, dedicated_sun_node;
	double dist_to_nearest_neighbour, dedicated_sun_distance;
	bool first_adj_edge;
	int neighbour_type;
	edge moon_edge;

	forall_nodes(v,*G_mult_ptr[act_level])
		if((*A_mult_ptr[act_level])[v].get_type() == 0) //a moon node
		{//forall
			//find nearest neighbour node
			first_adj_edge = true;
			forall_adj_edges(e,v)
			{//forall2
				if(v == e->source())
					neighbour_node = e->target();
				else
					neighbour_node = e->source();
				neighbour_type = (*A_mult_ptr[act_level])[neighbour_node].get_type();
				if( (neighbour_type == 2) || (neighbour_type == 3) )
				{//if_1
					if(first_adj_edge)
					{//if
						first_adj_edge = false;
						moon_edge = e;
						dist_to_nearest_neighbour = (*E_mult_ptr[act_level])[e].get_length();
						nearest_neighbour_node =  neighbour_node;
					}//if
					else if(dist_to_nearest_neighbour >(*E_mult_ptr[act_level])[e].get_length())
					{//else
						moon_edge = e;
						dist_to_nearest_neighbour = (*E_mult_ptr[act_level])[e].get_length();
						nearest_neighbour_node = neighbour_node;
					}//else
				}//if_1
			}//forall2
			//find dedic. solar system for v and update information in *A_mult_ptr[act_level]
			//and *E_mult_ptr[act_level]

			(*E_mult_ptr[act_level])[moon_edge].make_moon_edge(); //mark this edge
			dedicated_sun_node = (*A_mult_ptr[act_level])[nearest_neighbour_node].
				get_dedicated_sun_node();
			dedicated_sun_distance = dist_to_nearest_neighbour + (*A_mult_ptr[act_level])
				[nearest_neighbour_node].get_dedicated_sun_distance();
			(*A_mult_ptr[act_level])[v].set_type(4);
			(*A_mult_ptr[act_level])[v].set_dedicated_sun_node(dedicated_sun_node);
			(*A_mult_ptr[act_level])[v].set_dedicated_sun_distance(dedicated_sun_distance);
			(*A_mult_ptr[act_level])[v].set_dedicated_pm_node(nearest_neighbour_node);

			//identify nearest_neighbour_node as a pm_node and update its information

			(*A_mult_ptr[act_level])[nearest_neighbour_node].set_type(3);
			(*A_mult_ptr[act_level])[nearest_neighbour_node].
				get_dedicated_moon_node_List_ptr()->pushBack(v);
		}//forall
}

inline void Multilevel::collaps_solar_systems(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int act_level)
{
	EdgeArray<double> new_edgelength;
	calculate_mass_of_collapsed_nodes(G_mult_ptr, A_mult_ptr, act_level);
	create_edges_edgedistances_and_lambda_Lists(G_mult_ptr, A_mult_ptr, E_mult_ptr,
		new_edgelength, act_level);
	delete_parallel_edges_and_update_edgelength(G_mult_ptr, E_mult_ptr, new_edgelength,
		act_level);
}

inline void Multilevel::calculate_mass_of_collapsed_nodes(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray <NodeAttributes>*> &A_mult_ptr,
	int act_level)
{
	node v;
	node dedicated_sun,high_level_node;

	forall_nodes(v,*G_mult_ptr[act_level])
	{
		dedicated_sun = (*A_mult_ptr[act_level])[v].get_dedicated_sun_node();
		high_level_node =  (*A_mult_ptr[act_level])[dedicated_sun].get_higher_level_node();
		(*A_mult_ptr[act_level+1])[high_level_node].set_mass((*A_mult_ptr[act_level+1])
			[high_level_node].get_mass()+1);
	}
}

void Multilevel::create_edges_edgedistances_and_lambda_Lists(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	EdgeArray<double>& new_edgelength,int
	act_level)
{
	edge e, e_new;
	node s_node, t_node;
	node s_sun_node, t_sun_node;
	node high_level_sun_s, high_level_sun_t;
	double length_e, length_s_edge, length_t_edge, newlength;
	double lambda_s, lambda_t;
	List<edge> inter_solar_system_edges;

	//create new edges at act_level+1 and create for each inter solar system edge  at
	//act_level a link to its corresponding edge

	forall_edges(e,*G_mult_ptr[act_level])
	{//forall
		s_node = e->source();
		t_node = e->target();
		s_sun_node =  (*A_mult_ptr[act_level])[s_node].get_dedicated_sun_node();
		t_sun_node =  (*A_mult_ptr[act_level])[t_node].get_dedicated_sun_node();
		if( s_sun_node != t_sun_node) //a inter solar system edge
		{//if
			high_level_sun_s = (*A_mult_ptr[act_level])[s_sun_node].get_higher_level_node();
			high_level_sun_t = (*A_mult_ptr[act_level])[t_sun_node].get_higher_level_node();

			//create new edge in *G_mult_ptr[act_level+1]
			e_new = G_mult_ptr[act_level+1]->newEdge(high_level_sun_s,high_level_sun_t);
			(*E_mult_ptr[act_level])[e].set_higher_level_edge(e_new);
			inter_solar_system_edges.pushBack(e);
		}//if
	}//forall

	//init new_edgelength calculate the values of new_edgelength and the lambda Lists

	new_edgelength.init(*G_mult_ptr[act_level+1]);
	forall_listiterators(edge, e_ptr, inter_solar_system_edges)
	{//forall
		s_node = (*e_ptr)->source();
		t_node = (*e_ptr)->target();
		s_sun_node =  (*A_mult_ptr[act_level])[s_node].get_dedicated_sun_node();
		t_sun_node =  (*A_mult_ptr[act_level])[t_node].get_dedicated_sun_node();
		length_e = (*E_mult_ptr[act_level])[*e_ptr].get_length();
		length_s_edge =(*A_mult_ptr[act_level])[s_node].get_dedicated_sun_distance();
		length_t_edge =(*A_mult_ptr[act_level])[t_node].get_dedicated_sun_distance();
		newlength = length_s_edge + length_e + length_t_edge;

		//set new edge_length in *G_mult_ptr[act_level+1]
		e_new = (*E_mult_ptr[act_level])[*e_ptr].get_higher_level_edge();
		new_edgelength[e_new] = newlength;

		//create entries in lambda Lists
		lambda_s = length_s_edge/newlength;
		lambda_t = length_t_edge/newlength;
		(*A_mult_ptr[act_level])[s_node].get_lambda_List_ptr()->pushBack(lambda_s);
		(*A_mult_ptr[act_level])[t_node].get_lambda_List_ptr()->pushBack(lambda_t);
		(*A_mult_ptr[act_level])[s_node].get_neighbour_sun_node_List_ptr()->pushBack(
			t_sun_node);
		(*A_mult_ptr[act_level])[t_node].get_neighbour_sun_node_List_ptr()->pushBack(
			s_sun_node);
	}//forall
}

void Multilevel::delete_parallel_edges_and_update_edgelength(
	Array<Graph*> &G_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	EdgeArray<double>& new_edgelength,int
	act_level)
{
	EdgeMaxBucketFunc get_max_index;
	EdgeMinBucketFunc get_min_index;
	edge e_act, e_save;
	Edge f_act;
	List<Edge> sorted_edges;
	Graph* Graph_ptr = G_mult_ptr[act_level+1];
	int save_s_index,save_t_index,act_s_index,act_t_index;
	int counter = 1;

	//make *G_mult_ptr[act_level+1] undirected
	makeSimpleUndirected(*G_mult_ptr[act_level+1]);

	//sort the List sorted_edges
	forall_edges(e_act,*Graph_ptr)
	{
		f_act.set_Edge(e_act,Graph_ptr);
		sorted_edges.pushBack(f_act);
	}

	sorted_edges.bucketSort(0,Graph_ptr->numberOfNodes()-1,get_max_index);
	sorted_edges.bucketSort(0,Graph_ptr->numberOfNodes()-1,get_min_index);

	//now parallel edges are consecutive in sorted_edges
	forall_listiterators(Edge, EdgeIterator,sorted_edges)
	{//for
		e_act = (*EdgeIterator).get_edge();
		act_s_index = e_act->source()->index();
		act_t_index = e_act->target()->index();

		if(EdgeIterator != sorted_edges.begin())
		{//if
			if( (act_s_index == save_s_index && act_t_index == save_t_index) ||
				(act_s_index == save_t_index && act_t_index == save_s_index) )
			{
				new_edgelength[e_save] += new_edgelength[e_act];
				Graph_ptr->delEdge(e_act);
				counter++;
			}
			else
			{
				if (counter > 1)
				{
					new_edgelength[e_save] /= counter;
					counter = 1;
				}
				save_s_index = act_s_index;
				save_t_index = act_t_index;
				e_save = e_act;
			}
		}//if
		else //first edge
		{
			save_s_index = act_s_index;
			save_t_index = act_t_index;
			e_save = e_act;
		}
	}//for

	//treat special case (last edges were multiple edges)
	if(counter >1)
		new_edgelength[e_save] /= counter;

	//init *E_mult_ptr[act_level+1] and import EdgeAttributes
	E_mult_ptr[act_level+1]->init(*G_mult_ptr[act_level+1]);
	forall_edges(e_act,*Graph_ptr)
		(*E_mult_ptr[act_level+1])[e_act].set_length(new_edgelength[e_act]);
}

void Multilevel::find_initial_placement_for_level(
	int level,
	int init_placement_way,
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr)
{
	List<node> pm_nodes;
	set_initial_positions_of_sun_nodes(level, G_mult_ptr, A_mult_ptr);
	set_initial_positions_of_planet_and_moon_nodes(level, init_placement_way, G_mult_ptr,
		A_mult_ptr, E_mult_ptr, pm_nodes);
	set_initial_positions_of_pm_nodes(level, init_placement_way, A_mult_ptr,
		E_mult_ptr, pm_nodes);
}

void Multilevel::set_initial_positions_of_sun_nodes(
	int level,
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray <NodeAttributes>*> &A_mult_ptr)
{
	node v_high, v_act;
	DPoint new_pos;
	forall_nodes(v_high,*G_mult_ptr[level+1])
	{
		v_act = (*A_mult_ptr[level+1])[v_high].get_lower_level_node();
		new_pos = (*A_mult_ptr[level+1])[v_high].get_position();
		(*A_mult_ptr[level])[v_act].set_position(new_pos);
		(*A_mult_ptr[level])[v_act].place();
	}
}

void Multilevel::set_initial_positions_of_planet_and_moon_nodes(
	int level,
	int init_placement_way,
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	List<node>& pm_nodes)
{
	double lambda, dedicated_sun_distance;
	int node_type;
	node v, v_adj, dedicated_sun;
	edge e;
	DPoint new_pos,dedicated_sun_pos, adj_sun_pos;
	List<DPoint> L;
	ListIterator<double> lambdaIterator;

	create_all_placement_sectors(G_mult_ptr,A_mult_ptr,E_mult_ptr,level);
	forall_nodes(v,*G_mult_ptr[level])
	{//for
		node_type = (*A_mult_ptr[level])[v].get_type();
		if(node_type == 3)
			pm_nodes.pushBack(v);
		else if(node_type == 2 || node_type == 4) //a planet_node or moon_node
		{//else
			L.clear();
			dedicated_sun = (*A_mult_ptr[level])[v].get_dedicated_sun_node();
			dedicated_sun_pos = (*A_mult_ptr[level])[dedicated_sun].get_position();
			dedicated_sun_distance = (*A_mult_ptr[level])[v].get_dedicated_sun_distance();

			if(init_placement_way == FMMMLayout::ipmAdvanced)
			{
				forall_adj_edges(e,v)
				{
					if(e->source() != v)
						v_adj = e->source();
					else
						v_adj = e->target();
					if( ( (*A_mult_ptr[level])[v].get_dedicated_sun_node() ==
						(*A_mult_ptr[level])[v_adj].get_dedicated_sun_node() ) &&
						( (*A_mult_ptr[level])[v_adj].get_type() != 1 ) &&
						( (*A_mult_ptr[level])[v_adj].is_placed() ) )
					{
						new_pos = calculate_position(dedicated_sun_pos,(*A_mult_ptr[level])
							[v_adj].get_position(),dedicated_sun_distance,
							(*E_mult_ptr[level])[e].get_length());
						L.pushBack(new_pos);
					}
				}
			}
			if ((*A_mult_ptr[level])[v].get_lambda_List_ptr()->empty())
			{//special case
				if(L.empty())
				{
					new_pos = create_random_pos(dedicated_sun_pos,(*A_mult_ptr[level])
						[v].get_dedicated_sun_distance(),
						(*A_mult_ptr[level])[v].get_angle_1(),
						(*A_mult_ptr[level])[v].get_angle_2());
					L.pushBack(new_pos);
				}
			}//special case
			else
			{//usual case
				lambdaIterator = (*A_mult_ptr[level])[v].get_lambda_List_ptr()->begin();

				forall_listiterators(node, adj_sun_ptr,*(*A_mult_ptr[level])[v].
					get_neighbour_sun_node_List_ptr())
				{
					lambda = *lambdaIterator;
					adj_sun_pos = (*A_mult_ptr[level])[*adj_sun_ptr].get_position();
					new_pos = get_waggled_inbetween_position(dedicated_sun_pos,adj_sun_pos,
						lambda);
					L.pushBack(new_pos);
					if(lambdaIterator != (*A_mult_ptr[level])[v].get_lambda_List_ptr()
						->rbegin())
						lambdaIterator = (*A_mult_ptr[level])[v].get_lambda_List_ptr()
						->cyclicSucc(lambdaIterator);
				}
			}//usual case

			(*A_mult_ptr[level])[v].set_position(get_barycenter_position(L));
			(*A_mult_ptr[level])[v].place();
		}//else
	}//for
}

void Multilevel::create_all_placement_sectors(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int level)
{
	node v_high, w_high, sun_node, v, ded_sun;
	edge e_high;
	List<DPoint> adj_pos;
	double angle_1, angle_2, act_angle_1, act_angle_2, next_angle, min_next_angle;
	DPoint start_pos, end_pos;
	int MAX = 10; //the biggest of at most MAX random selected sectors is choosen
	int steps;
	ListIterator<DPoint> it, next_pos_ptr;
	bool first_angle;

	forall_nodes(v_high,(*G_mult_ptr[level+1]))
	{//forall
		//find pos of adjacent nodes
		adj_pos.clear();
		DPoint v_high_pos ((*A_mult_ptr[level+1])[v_high].get_x(),
			(*A_mult_ptr[level+1])[v_high].get_y());
		forall_adj_edges(e_high,v_high)
			if(!(*E_mult_ptr[level+1])[e_high].is_extra_edge())
			{
				if(v_high == e_high->source())
					w_high = e_high->target();
				else
					w_high = e_high->source();

				DPoint w_high_pos ((*A_mult_ptr[level+1])[w_high].get_x(),
					(*A_mult_ptr[level+1])[w_high].get_y());
				adj_pos.pushBack(w_high_pos);
			}
			if(adj_pos.empty()) //easy case
			{
				angle_1 = 0;
				angle_2 = 6.2831853;
			}
			else if(adj_pos.size() == 1) //special case
			{
				//create angle_1
				start_pos = *adj_pos.begin();
				DPoint x_parallel_pos (v_high_pos.m_x + 1, v_high_pos.m_y);
				angle_1 = angle(v_high_pos,x_parallel_pos,start_pos);
				//create angle_2
				angle_2 = angle_1 + Math::pi;
			}
			else //usual case
			{//else
				steps = 1;
				it = adj_pos.begin();
				do
				{
					//create act_angle_1
					start_pos = *it;
					DPoint x_parallel_pos (v_high_pos.m_x + 1, v_high_pos.m_y);
					act_angle_1 = angle(v_high_pos,x_parallel_pos,start_pos);
					//create act_angle_2
					first_angle = true;

					for(next_pos_ptr = adj_pos.begin();next_pos_ptr.valid();++next_pos_ptr)
					{
						next_angle = angle(v_high_pos,start_pos,*next_pos_ptr);

						if(start_pos != *next_pos_ptr && (first_angle || next_angle <
							min_next_angle))
						{
							min_next_angle = next_angle;
							first_angle = false;
						}
					}
					act_angle_2 = act_angle_1 + min_next_angle;
					if((it == adj_pos.begin())||((act_angle_2-act_angle_1)>(angle_2-angle_1)))
					{
						angle_1 = act_angle_1;
						angle_2 = act_angle_2;
					}
					if(it != adj_pos.rbegin())
						it = adj_pos.cyclicSucc(it);
					steps++;
				}
				while((steps <= MAX) && (it != adj_pos.rbegin()));

				if(angle_1 == angle_2)
					angle_2 = angle_1 + Math::pi;
			}//else

			//import angle_1 and angle_2 to the dedicated suns at level level
			sun_node = (*A_mult_ptr[level+1])[v_high].get_lower_level_node();
			(*A_mult_ptr[level])[sun_node].set_angle_1(angle_1);
			(*A_mult_ptr[level])[sun_node].set_angle_2(angle_2);
	}//forall

	//import the angle values from the values of the dedicated sun nodes
	forall_nodes(v,*G_mult_ptr[level])
	{
		ded_sun = (*A_mult_ptr[level])[v].get_dedicated_sun_node();
		(*A_mult_ptr[level])[v].set_angle_1((*A_mult_ptr[level])[ded_sun].get_angle_1());
		(*A_mult_ptr[level])[v].set_angle_2((*A_mult_ptr[level])[ded_sun].get_angle_2());
	}
}

void Multilevel::set_initial_positions_of_pm_nodes(
	int level,
	int init_placement_way,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	List<node>& pm_nodes)
{
	double moon_dist, sun_dist, lambda;
	node v_adj, sun_node;
	edge e;
	DPoint sun_pos, moon_pos, new_pos, adj_sun_pos;
	List<DPoint> L;
	ListIterator<double> lambdaIterator;

	forall_listiterators(node,v_ptr,pm_nodes)
	{//forall
		L.clear();
		sun_node = (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_node();
		sun_pos =  (*A_mult_ptr[level])[sun_node].get_position();
		sun_dist = (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_distance();

		if(init_placement_way == FMMMLayout::ipmAdvanced)
		{//if
			forall_adj_edges(e,*v_ptr)
			{
				if(e->source() != *v_ptr)
					v_adj = e->source();
				else
					v_adj = e->target();
				if( (!(*E_mult_ptr[level])[e].is_moon_edge()) &&
					( (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_node() ==
					(*A_mult_ptr[level])[v_adj].get_dedicated_sun_node() ) &&
					( (*A_mult_ptr[level])[v_adj].get_type() != 1 ) &&
					( (*A_mult_ptr[level])[v_adj].is_placed() ) )
				{
					new_pos = calculate_position(sun_pos,(*A_mult_ptr[level])[v_adj].
						get_position(),sun_dist,(*E_mult_ptr[level])
						[e].get_length());
					L.pushBack(new_pos);
				}
			}
		}//if
		forall_listiterators(node, moon_node_ptr,*(*A_mult_ptr[level])[*v_ptr].
			get_dedicated_moon_node_List_ptr())
		{
			moon_pos = (*A_mult_ptr[level])[*moon_node_ptr].get_position();
			moon_dist =  (*A_mult_ptr[level])[*moon_node_ptr].get_dedicated_sun_distance();
			lambda = sun_dist/moon_dist;
			new_pos = get_waggled_inbetween_position(sun_pos,moon_pos,lambda);
			L.pushBack(new_pos);
		}

		if (!(*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()->empty())
		{
			lambdaIterator = (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()->begin();

			forall_listiterators(node,adj_sun_ptr,*(*A_mult_ptr[level])[*v_ptr].
				get_neighbour_sun_node_List_ptr())
			{
				lambda = *lambdaIterator;
				adj_sun_pos = (*A_mult_ptr[level])[*adj_sun_ptr].get_position();
				new_pos = get_waggled_inbetween_position(sun_pos,adj_sun_pos,lambda);
				L.pushBack(new_pos);
				if(lambdaIterator != (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()
					->rbegin())
					lambdaIterator = (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()
					->cyclicSucc(lambdaIterator);
			}
		}

		(*A_mult_ptr[level])[*v_ptr].set_position(get_barycenter_position(L));
		(*A_mult_ptr[level])[*v_ptr].place();
	}//forall
}

inline DPoint Multilevel::create_random_pos(DPoint center,double radius,double angle_1,
	double angle_2)
{
	const int BILLION = 1000000000;
	DPoint new_point;
	double rnd = double(randomNumber(1,BILLION)+1)/(BILLION+2);//rand number in (0,1)
	double rnd_angle = angle_1 +(angle_2-angle_1)*rnd;
	double dx = cos(rnd_angle) * radius;
	double dy = sin(rnd_angle) * radius;
	new_point.m_x = center.m_x + dx ;
	new_point.m_y = center.m_y + dy;
	return new_point;
}

inline DPoint Multilevel::get_waggled_inbetween_position(DPoint s, DPoint t, double lambda)
{
	const double WAGGLEFACTOR = 0.05;
	const int BILLION = 1000000000;
	DPoint inbetween_point;
	inbetween_point.m_x = s.m_x + lambda*(t.m_x - s.m_x);
	inbetween_point.m_y = s.m_y + lambda*(t.m_y - s.m_y);
	double radius = WAGGLEFACTOR * (t-s).norm();
	double rnd = double(randomNumber(1,BILLION)+1)/(BILLION+2);//rand number in (0,1)
	double rand_radius =  radius * rnd;
	return create_random_pos(inbetween_point,rand_radius,0,6.2831853);
}

inline DPoint Multilevel::get_barycenter_position(List<DPoint>& L)
{
	DPoint sum (0,0);
	DPoint barycenter;

	forall_listiterators(DPoint, act_point_ptr,L)
		sum = sum + (*act_point_ptr);
	barycenter.m_x = sum.m_x/L.size();
	barycenter.m_y = sum.m_y/L.size();
	return barycenter;
}

inline DPoint Multilevel::calculate_position(DPoint P, DPoint Q, double dist_P, double dist_Q)
{
	double dist_PQ = (P-Q).norm();
	double lambda = (dist_P + (dist_PQ - dist_P - dist_Q)/2)/dist_PQ;
	return get_waggled_inbetween_position(P,Q,lambda);
}

void Multilevel::delete_multilevel_representations(
	Array<Graph*> &G_mult_ptr,
	Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
	Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
	int max_level)
{
	for(int i=1; i<= max_level; i++)
	{
		delete G_mult_ptr[i];
		delete A_mult_ptr[i];
		delete E_mult_ptr[i];
	}
}

double Multilevel::angle(DPoint& P, DPoint& Q, DPoint& R)
{
	double dx1 = Q.m_x - P.m_x;
	double dy1 = Q.m_y - P.m_y;
	double dx2 = R.m_x - P.m_x;
	double dy2 = R.m_y - P.m_y;
	double fi;//the angle

	if ((dx1 == 0 && dy1 == 0) || (dx2 == 0 && dy2 == 0))
		cout<<"Multilevel::angle()"<<endl;

	double norm  = (dx1*dx1+dy1*dy1)*(dx2*dx2+dy2*dy2);
	double cosfi = (dx1*dx2+dy1*dy2) / sqrt(norm);

	if (cosfi >=  1.0 ) fi = 0;
	if (cosfi <= -1.0 ) fi = Math::pi;
	else
	{
		fi = acos(cosfi);
		if (dx1*dy2 < dy1*dx2) fi = -fi;
		if (fi < 0) fi += 2*Math::pi;
	}
	return fi;
}

}//namespace ogdf


text:
<!DOCTYPE html>

   <title>

    8.10: The Printing Press as an Agent of Change—Explained ◦ Winning Slowly
</title>
   <meta
      name="description"
      content=""
   />

   <meta charset="UTF-8" />
   <meta name="viewport" content="width=device-width,initial-scale=1" />
   <link rel="author" href="humans.txt" />
<meta name="twitter:card" content="summary" />
<meta name="twitter:site" content="@winningslowly" />
<meta name="twitter:creator" content="@winningslowly" />

   <meta property="og:url" content="https://winningslowly.org/8.10/" />
   <meta name="article:author" content="https://chriskrycho.com" />
   <meta name="article:author" content="http://stephencarradini.com" />

   <meta property="article:section" content="Season 8: The Winning Slowly Epistemology Book (and Film) Club" />

   <meta property="og:title" content=" 8.10: The Printing Press as an Agent of Change—Explained ◦ Winning Slowly" />
   <meta name="twitter:title" content=" 8.10: The Printing Press as an Agent of Change—Explained ◦ Winning Slowly" />

   <meta property="og:description" content="Digging into Elizabeth Eisenstein's magisterial and seminal work on how print changed culture." />
   <meta name="twitter:description" content="Digging into Elizabeth Eisenstein's magisterial and seminal work on how print changed culture." />

   <meta property="og:type" content="article" />

   <meta property="article:published_time" content="2020-06-03T08:3000-0600" />

      <meta property="article:modified_time" content="2020-06-03T08:3000-0600" />

      <meta property="article:tag" content=technology />
      <meta property="article:tag" content=reading />
      <meta property="article:tag" content=science />

      <meta property="og:image" content="https://cdn.winningslowly.org/file/winningslowly/images/printing-press.jpg" />
      <meta name="twitter:image" content="https://cdn.winningslowly.org/file/winningslowly/images/printing-press.jpg" />

   <link href="/style.min.css" type="text/css" rel="stylesheet" />
   <link
      href="//netdna.bootstrapcdn.com/font-awesome/4.0.3/css/font-awesome.css"
      rel="stylesheet"
   />
   <link
      href="/feed.xml"
      type="application/rss+xml"
      rel="alternate"
      title="Winning Slowly RSS Feed"
   />

   <link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
   <link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
   <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
   <link rel="manifest" href="/site.webmanifest">
   <link rel="mask-icon" href="/safari-pinned-tab.svg" color="#2369af">
   <meta name="msapplication-TileColor" content="#2369af">
   <meta name="theme-color" content="#2369af">

                  Season 0

                  Season 1

                  Season 2

                  Season 3

                  Season 4

                  Season 5

                  Season 6

                  Season 7

                  Season 8

                  Bonus

                  Standalone Episodes

            Winning
            Slowly

            Taking the long view on
            technology, religion, ethics, and art.

         Episode 8.10
         The Printing Press as an Agent of Change—Explained

Digging into Elizabeth Eisenstein's magisterial and seminal work on how print changed culture.

June 03, 2020

         Tagged:
            reading,
            science,
            technology

         <audio class="Audio-player" title="The Printing Press as an Agent of Change—Explained
" controls="controls" preload="metadata">
            <source src=https://www.podtrac.com/pts/redirect.mp3/cdn.winningslowly.org/file/winningslowly/8.10.mp3 />
         </audio>

            (download directly)

The Printing Press as an Agent of Change, Elizabeth Eisenstein

Show Notes

We almost entirely ended up talking about the contents of this book specifically! And we weren't joking about how dense it is:

these pages are serious business

We did mention a couple other episodes of the show:

8.08: Jurassic Park—Explained

on friction

7.09: Frictioneers

Upcoming books

July (8.12 and 8.13): Dark Matters: On the Surveillance of Blackness, Simone Brown

August (8.14 and 8.15): The Real World of Technology, Ursula Franklin

September (8.16 and 8.17): (probably) Technopoly, Neil Postman

Music

"Alpha Orionis" by Juffbass

"Winning Slowly Theme" by Chris Krycho

Sponsors

Many thanks to the people who help us make this show possible by their financial support! This month's sponsors:

Daniel Ellcey

Douglas Campos

Jake Grant

Marnix Klooster

Spencer Smith

If you'd like to support the show, you can make a pledge at Patreon or give directly via Square Cash.

Respond

We love to hear your thoughts. Hit us up via Twitter, Facebook, or email!

About

The Hosts

      Chris Krycho is a
      software engineer,
      podcaster,
      writer, and
      occasional composer. He lives with his family in Colorado.

      Stephen Carradini is a
      digital media scholar and professor,
      writer,
      editor, and
      songwriter. He lives with his family in Arizona.

Privacy

      We collect zero data about your use of this website. We use Podtrac to gather very limited aggregate statistics about our listenership—the total number of downloads per episode, and the countries of our listenership. That's it, and it always will be.

License

      ©2013–2021 Stephen Carradini and Chris Krycho.

      Design by Chris Krycho, using Tiempos Headline and Tiempos Text, by Klim Type Foundry.

      Source code available on GitHub.

      All content licensed under a Creative Commons Attribution 4.0 International License.
      (Translation: please don't just copy and paste; please do copy and modify for any use, giving credit where due.)
      Read more on our licenses.


text:
#include "prolog_ppl7.h"
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#include "ppl7.h"
#ifdef WIN32
#pragma message( "*** Kompiliere Resourcen, das kann eine Weile dauern..." )
#endif

namespace ppl7 {

#include "../resource/res.h"

static Resource *pplResource=NULL;

static void PPLExitResource()
{
	if (pplResource) delete pplResource;
	pplResource=NULL;
}

Resource *GetPPLResource()
{
	if (!pplResource) {
		Resource *r;
		r=new Resource;
		r->useMemory(PPL7_RESOURCES,sizeof(PPL7_RESOURCES));
		pplResource=r;
		atexit(PPLExitResource);
	}
	return pplResource;
}

}	// EOF namespace ppl7