public static GeometryGraph CopyGraph(GeometryGraph graph)
        {
            if (graph == null) return null;
            var copy = new GeometryGraph();

            Dictionary<Node,Node> nodeCopy=new Dictionary<Node, Node>(graph.Nodes.Count);

            foreach (Node node in graph.Nodes) {
                var c = new Node();
                copy.Nodes.Add(c);
                nodeCopy[node] = c;
                c.BoundaryCurve = node.BoundaryCurve.Clone();
            }

            foreach (Edge edge in graph.Edges) {
                var source = edge.Source;
                var target = edge.Target;
                var copySource = nodeCopy[source];
                var copyTarget = nodeCopy[target];
                Edge edgeCopy=new Edge(copySource,copyTarget);
                copy.Edges.Add(edgeCopy);
                StraightLineEdges.RouteEdge(edgeCopy,0);
            }

            return copy;
        }

 private Node GetOrCreateNode(Port port, Dictionary<ICurve, Node> nodeDictionary) {
     var curve = GetPortCurve(port);
     Node node;
     if (!nodeDictionary.TryGetValue(curve, out node))
         nodeDictionary[curve] = node = new Node(curve);
     return node;
 }

        /// <summary>
        /// Executes the algorithm.
        /// </summary>
        protected override void  RunInternal()
        {
            Result = new double[pivotArray.Length][];

            Node[] nodes = new Node[graph.Nodes.Count];
            graph.Nodes.CopyTo(nodes, 0);
            double[] min = new double[graph.Nodes.Count];
            for (int i = 0; i < min.Length; i++)
            {
                min[i] = Double.PositiveInfinity;
            }
            Node pivot = nodes[0];
            pivotArray[0] = 0;
            for (int i = 0; ; i++) {
                var ssd = new SingleSourceDistances(graph, pivot, directed);
                ssd.Run();
                Result[i] = ssd.Result;
                if (i + 1 < pivotArray.Length)
                {//looking for the next pivot
                    int argmax = 0;
                    for (int j = 0; j < Result[i].Length; j++)
                    {
                        min[j] = Math.Min(min[j], Result[i][j]);
                        if (min[j] > min[argmax])
                            argmax = j;
                    }
                    pivot = nodes[argmax];
                    pivotArray[i + 1] = argmax;
                }
                else
                    break;
            }

        }

        public void SimpleDeepTranslationTest()
        {
            var graph = new GeometryGraph();
            var a = new Node(CurveFactory.CreateRectangle(30, 20, new Point()));
            var b = new Node(CurveFactory.CreateRectangle(30, 20, new Point(100, 0)));
            var e = new Edge(a, b);
            graph.Nodes.Add(a);
            graph.Nodes.Add(b);
            graph.Edges.Add(e);
            var c = CreateCluster(new Node[] { a, b }, 10);
            c.CalculateBoundsFromChildren(0);
            var originalClusterBounds = c.BoundingBox;
            RouteEdges(graph, 10);
            var edgeBounds = e.BoundingBox;

            Assert.AreEqual(c.BoundingBox.Width, 150, "Cluster has incorrect width");
            Assert.AreEqual(c.BoundingBox.Height, 40, "Cluster has incorrect width");

            var delta = new Point(10, 20);
            c.DeepTranslation(delta, true);
            Rectangle translatedClusterBounds = c.BoundingBox;

            Assert.IsTrue(ApproximateComparer.Close((translatedClusterBounds.LeftBottom - originalClusterBounds.LeftBottom), delta), "edge was not translated");

            c.CalculateBoundsFromChildren(0);

            Assert.IsTrue(ApproximateComparer.Close(translatedClusterBounds, c.BoundingBox), "translated bounds do not equal computed bounds of translated cluster");
            Assert.IsTrue(ApproximateComparer.Close((e.BoundingBox.LeftBottom - edgeBounds.LeftBottom), delta), "edge was not translated");
        }

 public HorizontalSeparationConstraint(Node u, Node v, double separation, bool equality)
 {
     this.equality = equality;
     this.u = u;
     this.v = v;
     this.separation = separation;
 }

        internal static GeometryGraph CreateAndLayoutGraph()
        {
            double w = 30;
            double h = 20;
            GeometryGraph graph = new GeometryGraph();
            Node a = new Node( new Ellipse(w, h, new P()),"a");
            Node b = new Node( CurveFactory.CreateRectangle(w, h, new P()),"b");
            Node c = new Node( CurveFactory.CreateRectangle(w, h, new P()),"c");
            Node d = new Node(CurveFactory.CreateRectangle(w, h, new P()), "d");

            graph.Nodes.Add(a);
            graph.Nodes.Add(b);
            graph.Nodes.Add(c);
            graph.Nodes.Add(d);
            Edge e = new Edge(a, b) { Length = 10 };
            graph.Edges.Add(e);
            graph.Edges.Add(new Edge(b, c) { Length = 3 });
            graph.Edges.Add(new Edge(b, d) { Length = 4 });

            //graph.Save("c:\\tmp\\saved.msagl");
            var settings = new Microsoft.Msagl.Layout.MDS.MdsLayoutSettings();
            LayoutHelpers.CalculateLayout(graph, settings, null);

            return graph;
        }

 /// <summary>
 /// Validate two nodes not overlapping with each other
 /// </summary>        
 internal static void ValidateNoNodeOverlapping(Node node, Node node2)
 {
     if (node == node2 || node is Cluster || node2 is Cluster)
     {
         return;
     }
     Assert.IsFalse(node.BoundingBox.Intersects(node2.BoundingBox), string.Format("Node (ID: {0}, BoundingBox: {1}) overlaps with Node (ID: {2}, BoundingBox: {3})", node.UserData, node.BoundingBox.ToString(), node2.UserData, node2.BoundingBox.ToString()));            
 }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="pushedNodes">nodes that are being pushed</param>
        /// <param name="separation"></param>
        /// <param name="pushingNodes"></param>
        public BumperPusher(IEnumerable<Node> pushedNodes, double separation, Node[] pushingNodes) {
            this.separation = separation;
            rtree = new RTree<Node>(RectangleNode<Node>.CreateRectangleNodeOnEnumeration(
                pushedNodes.Select(n => new RectangleNode<Node>(n, GetPaddedBoxOfNode(n)))));

            //LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(rtree.GetAllLeaves().Select(n=>new DebugCurve(n.BoundaryCurve)));
            this.pushingNodes = pushingNodes;
        }

  void Visit(Node u)
 {
     visited.Add(u);
     low[u] = depth[u] = visited.Count;
     foreach (var e in u.OutEdges.Concat(u.InEdges))
     {
         Visit(u, e);
     }
 }

 /// <summary>
 /// positions location nodes
 /// </summary>
 /// <param name="locationNodes">the nodes represent the labels and originally are positioned at locations</param>
 /// <param name="locationRadius">the minimum gap between a location and its label</param>
 /// <param name="removeCrossings">If set to true will remove intersections between line segments (location, locationLabel). 
 /// The result will be better but the calculation will take more time.
 /// </param>
 public static GeometryGraph PositionLabels(Node[] locationNodes, double locationRadius, bool routeEdges, double labelSeparation)
 {
     #if MYDEBUG
     Microsoft.Msagl.GraphViewerGdi.DisplayGeometryGraph.SetShowFunctions();
     #endif
     var labeler = new LocationLabeler(locationNodes, locationRadius, routeEdges, labelSeparation);
     labeler.Work();
     return labeler.graph;
 }

 public ShortestPartRouterForLg(Node source, Node target, Func<Node, LgNodeInfo> geomNodeToLgNode) {
     this.source = source;
     this.target = target;
     this.geomNodeToLgNode = geomNodeToLgNode;
     queue.Enqueue(source, 0);
     pathDirection = target.Center - source.Center;
     costToTarget = double.PositiveInfinity;
     EdgeIsInterestingFunc = MonotonicityFunc;
 }

        static void CreateShapeIfNeeeded(Node n, Dictionary<Node, Shape> nodesToShapes) {
            if (nodesToShapes.ContainsKey(n)) return;
            nodesToShapes[n] = new RelativeShape(() => n.BoundaryCurve)
#if DEBUG
        {
                        UserData = n.ToString()
        }
#endif       
                ;
        }

 IEnumerable<Node> PushByNodeAndReportPushedAsFixed(Node pushingNode) {
     var ret = new List<Node>();
     var pushingNodeBox = GetPaddedBoxOfNode(pushingNode);
     foreach (var rectNode in rtree.GetAllLeavesIntersectingRectangle(pushingNodeBox)) {
         if (fixedNodes.Contains(rectNode.UserData)) continue;
         if (PushNodeAndUpdateRTree(pushingNode, rectNode))
             ret.Add(rectNode.UserData);
     }
     return ret;
 }

        public void IsDescendantOf_BasicTest()
        {
            Cluster cluster = new Cluster();
            Node node = new Node();
            Node node2 = new Node();
            cluster.AddChild(node);

            Assert.IsTrue(node.IsDescendantOf(cluster), "Node is a descendant of cluster but IsDescendantOf returns false.");
            Assert.IsFalse(node2.IsDescendantOf(cluster), "Node2 is not a descendant of cluster but IsDescendantOf returns true.");
            Assert.IsFalse(cluster.IsDescendantOf(cluster), "A cluster should not be considered a descendant of itself.");
        }

 static void ProcessAncestorDescendantCouple(Cluster ancestor, Node node, Dictionary<Node, Shape> nodesToShapes) {
     Cluster parent=Parent(node);
     do {
         foreach (var n in Children(parent))
             CreateShapeIfNeeeded(n, nodesToShapes);
         if (parent == ancestor)
             break;
         parent = Parent(parent);                
     } while (true);
     CreateShapeIfNeeeded(parent, nodesToShapes);
 }

        GeometryGraph CreateGeometryGraph(PreGraph preGraph) {
            var graph = new GeometryGraph();
            var nodeDictionary = new Dictionary<ICurve, Node>();
            foreach (var curve in preGraph.nodeBoundaries) {
                var node = new Node(curve);
                nodeDictionary[curve] = node;
                graph.Nodes.Add(node);
            }
            foreach (var eg in preGraph.edgeGeometries)
                AddEdgeGeometryToGraph(eg, graph, nodeDictionary);

            return graph;
        }

        public static GeometryGraph CreateComplex()
        {
            GeometryGraph graph = new GeometryGraph();
            var nodeInD = new Node();
            graph.Nodes.Add(nodeInD);
            var nodePrecursor = new Node();
            graph.Nodes.Add(nodePrecursor);
            var nodeEarlyMeiosis = new Node();
            graph.Nodes.Add(nodeEarlyMeiosis);
            var nodeMeiosis = new Node();
            graph.Nodes.Add(nodeMeiosis);



            return graph;
        }

 /// <summary>
 /// Place node at the centroid of its neighbours and its initial position
 /// </summary>
 /// <param name="u">node to center</param>
 private static void CenterNode(Node u)
 {
     var c = u.Center;
     int count = 1;
     foreach (var e in u.InEdges)
     {
         c += e.Source.Center;
         ++count;
     }
     foreach (var e in u.OutEdges)
     {
         c += e.Target.Center;
         ++count;
     }
     Random r = new Random();
     c += new Point(r.NextDouble(), r.NextDouble());
     u.Center = c / count;
 }

        /// <summary>
        /// Creates a shape with a RelativeFloatingPort for the node center, attaches it to the shape and all edges
        /// </summary>
        /// <param name="node"></param>
        /// <returns>Shape obstacle for the node with simple port</returns>
        static Shape CreateShapeWithCenterPort(Node node)
        {
            // Debug.Assert(ApproximateComparer.Close(node.BoundaryCurve.BoundingBox, node.BoundingBox), "node's curve doesn't fit its bounds!");
            var shape = new RelativeShape(() => node.BoundaryCurve);
            var port = new RelativeFloatingPort(() => node.BoundaryCurve, () => node.Center);
            shape.Ports.Insert(port);
            foreach (var e in node.InEdges)
                FixPortAtTarget(shape, port, e);
            foreach (var e in node.OutEdges)
                FixPortAtSource(shape, port, e);
            foreach (var e in node.SelfEdges) {
               FixPortAtSource(shape, port, e);
               FixPortAtTarget(shape, port, e);
            }
#if DEBUG
           // shape.UserData = node.ToString();
#endif
            return shape;
        }

        public void IsDescendantOf_ManyParents()
        {
            Cluster grandMother = new Cluster();
            Cluster grandFather = new Cluster();
            Cluster parent = new Cluster();
            Cluster uncle = new Cluster();
            grandMother.AddChild(parent);
            grandMother.AddChild(uncle);
            grandFather.AddChild(parent);
            grandFather.AddChild(uncle);

            Node child = new Node();
            parent.AddChild(child);

            Assert.IsTrue(child.IsDescendantOf(parent), "The child node should be considered a descendant of its parent.");
            Assert.IsTrue(child.IsDescendantOf(grandMother), "The child node should be considered a descendant of its grandmother.");
            Assert.IsTrue(child.IsDescendantOf(grandFather), "The child node should be considered a descendant of its grandfather.");
            Assert.IsFalse(child.IsDescendantOf(uncle), "The child node should not be considered a descendant of its uncle.");
        }