List<Edge> Bfs(Node root, Node target)
        {
            ((NodeData)(root.UserData)).TraverseParent = null;
            ((NodeData)(target.UserData)).TraverseParent = null;

            var queue = new Queue<Node>();
            var discovered = new HashSet<Node>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                Node current = queue.Dequeue();
                discovered.Add(current);

                if (current.Id == target.Id)
                    return GetPath(current);

                var nodeEdges = current.OutEdges;
                foreach (var edge in nodeEdges)
                {
                    var next = edge.TargetNode;
                    var c = ((EdgeData)(edge.UserData)).currFlow;
                    if (c > 0 && !discovered.Contains(next))
                    {
                        ((NodeData)(next.UserData)).TraverseParent = current;
                        queue.Enqueue(next);
                    }
                }
            }
            return null;
        }

 protected void MakeNodePrivate(Node node)
 {
     node.Attr.Shape = Shape.Box;
     node.Attr.LabelMargin = 3;
     node.Attr.FillColor = GameMasterNode.kPurple;
     node.Label.FontSize = 6;
 }

 public static Graph CreateDrawingGraph(GeometryGraph gg)
 {
     counter = 0;
     localMap = new Dictionary<GeometryNode,Node>();
     dg = new Graph(counter++.ToString()) { GeometryGraph = gg };
     foreach (GeometryNode n in gg.Nodes)
     {
         Node node = new Node(counter++.ToString());
         node.Attr.Shape = Shape.Ellipse;
         node.GeometryNode = n;
         dg.AddNode(node);
         localMap[n]=node;
     }
     Subgraph cluster = new Subgraph(counter++.ToString());
     cluster.GeometryNode = gg.RootCluster;
     dg.RootSubgraph = cluster;
     PopulateClusters(cluster, gg.RootCluster);
 
     foreach (GeometryEdge e in gg.Edges)
     {
         Edge edge = new Edge(localMap[e.Source], localMap[e.Target], ConnectionToGraph.Disconnected);
         edge.Attr.ArrowheadAtSource = e.ArrowheadAtSource ? ArrowStyle.Normal : ArrowStyle.None;
         edge.Attr.ArrowheadAtTarget = e.ArrowheadAtTarget ? ArrowStyle.Normal : ArrowStyle.None;
         edge.GeometryEdge = e;
         dg.AddPrecalculatedEdge(edge);
     }
     //PopulateClusterEdges(dg.RootSubgraph, gg.RootCluster);
     
     return dg;
 }

 public virtual void UpdateGraphNode(Node graphNode)
 {
     graphNode.Attr.LabelWidthToHeightRatio = 1;
     graphNode.Attr.Shape = Shape.Box;
     graphNode.Attr.FillColor = GameMasterNode.kGreen;
     graphNode.Attr.LabelMargin = 6;
 }

        public XNode(Node node, string category = null)
        {
            Node = node;
            _category = category;

            Border b = new Border();
            double size = node.Label.Text.Length * 9;
            b.Width = size + 12;
            b.Height = size * 2 / 3 + 4;
            _visualObject = b;

            Brush strokeBrush = CommonX.BrushFromMsaglColor(Node.Attr.Color);
            if (category != null)
            {
                Brush brush = Categories.GetBrush(_category);
                if (brush != null) strokeBrush = brush;
            }

            BoundaryPath = new Path {
                //Data = CreatePathFromNodeBoundary(),
                Stroke = strokeBrush,
                Fill = CommonX.BrushFromMsaglColor(Node.Attr.FillColor),
                StrokeThickness = Node.Attr.LineWidth
            };

            Node.Attr.LineWidthHasChanged += AttrLineWidthHasChanged;
            //Node.Attr.GeometryNode.LayoutChangeEvent += GeometryNodeBeforeLayoutChangeEvent;
        }

        void FordFulkersonAlgo(Node nodeSource, Node nodeTerminal)
        {
            label_flow.Text = "Przepływ = 0";
            invalidateFlow();

            var flow = 0f;
            var path = Bfs(nodeSource, nodeTerminal);
            List<AlgoState> steps = new List<AlgoState>(); AlgoState cas = new AlgoState();

            while (path != null && path.Count > 0)
            {
                label_flow.Text = "Przepływ = " + flow;
                var minCapacity = float.MaxValue;
                foreach (var edge in path)
                {
                    if (((EdgeData)(edge.UserData)).currFlow < minCapacity)
                        minCapacity = ((EdgeData)(edge.UserData)).currFlow;
                }

                AugmentPath(path, minCapacity);
                flow += minCapacity;

                clearColors();
                reloadLabels();
                foreach (Edge e in path)
                {
                    foreach (Edge e2 in graph.Edges)
                    {
                        if (e2.Source == e.Source && e2.Target == e.Target) e2.Attr.Color = Color.Red;
                        //dirty code written without understanding Graph class - fixme!
                    }
                }
                label_flow.Text = "Przepływ = " + flow;
                redraw();
                DialogResult dr = MessageBox.Show("Tak=kontynuuj, Nie=wstecz o jeden krok", "pauza", MessageBoxButtons.YesNo);
                if (dr == DialogResult.Yes) {
                    cas.g = graph; cas.p = path; steps.Add(cas); 
                    path = Bfs(nodeSource, nodeTerminal);
                }
                else if (dr == DialogResult.No)
                {
                    if (steps.Count < 1)
                    {
                        MessageBox.Show("Nie można sie cofnąć!");
                    }
                    else { 
                        cas = steps[steps.Count - 1];
                        steps.RemoveAt(steps.Count - 1);
                        graph = cas.g; path = cas.p;
                        label_flow.Text = "Przepływ = " + flow;
                        continue;
                    }
                }
            }

            clearColors();
            reloadLabels();
            MessageBox.Show("Maksymalny przepływ wynosi: "+flow.ToString());
        }

 /// <summary>
 /// Compute the size of the block
 /// </summary>
 /// <param name="node"></param>
 /// <returns></returns>
 public ICurve GetNodeBoundary(Node node)
 {
     const double radiusRatio = 0.3;
     var extent = Layout.CalculateExtent();
     double height = extent.Height;
     double width = extent.Width;
     return CurveFactory.CreateRectangleWithRoundedCorners(width, height, width * radiusRatio, height * radiusRatio, new P2());
 }

 public AutomatonViewModel()
 {
     graph = new Graph();
     graph.Attr.LayerDirection = LayerDirection.LR;
     dummy = new Node(" ");
     dummy.IsVisible = false;
     graph.AddNode(dummy);
     ResetAll();
 }

 private Image ImageOfNode(DrawingNode node) {
     Image image;
     if (node.Id == leavesId)
         image = leaves;
     else if (node.Id == creekId)
         image = creek;
     else if (node.Id == wId)
         image = waterfall;
     else
         image = tree;
     return image;
 }

        internal DNode(DGraph graph, DrawingNode drawingNode)
            : base(graph)
        {
            this.DrawingNode = drawingNode;
            _OutEdges = new List<DEdge>();
            _InEdges = new List<DEdge>();
            _SelfEdges = new List<DEdge>();
            PortsToDraw = new Set<Port>();

            if (drawingNode.Label != null)
                Label = new DTextLabel(this, drawingNode.Label);
        }

 static ICurve CreateLabelAndBoundary(Node node)
 {
     node.Attr.Shape = Shape.DrawFromGeometry;
     node.Attr.LabelMargin *= 2;
     double width;
     double height;
     StringMeasure.MeasureWithFont(node.Label.Text,
                                   new Font(node.Label.FontName, (float)node.Label.FontSize), out width, out height);
     node.Label.Width = width;
     node.Label.Height = height;
     int r = node.Attr.LabelMargin;
     return CurveFactory.CreateRectangleWithRoundedCorners(width + r * 2, height + r * 2, r, r, new Point());
 }

        internal DNode(DObject graph, DrawingNode drawingNode)
            : base(graph)
        {
            this.DrawingNode = drawingNode;
            _OutEdges = new List<DEdge>();
            _InEdges = new List<DEdge>();
            _SelfEdges = new List<DEdge>();
            PortsToDraw = new Set<Port>();

            if (drawingNode.Label != null && drawingNode.Label.GeometryLabel != null)
                Label = new DTextLabel(this, drawingNode.Label);

            if (!(this is DCluster))
                Canvas.SetZIndex(this, 10000);
        }

      /// <summary>
      /// a helper function to creat a node boundary curve 
      /// </summary>
      /// <param name="node">the node</param>
      /// <param name="width">the node width</param>
      /// <param name="height">the node height</param>
      /// <returns></returns>
    public  static ICurve GetNodeBoundaryCurve(Node node, double width, double height)
    {
      if (node == null)
        throw new InvalidOperationException();
      NodeAttr nodeAttr = node.Attr;

      switch (nodeAttr.Shape)
      {
        case Shape.Ellipse:
        case Shape.DoubleCircle:
          return CurveFactory.CreateEllipse(width, height, new P2(0, 0));
        case Shape.Circle:
          {
            double r = Math.Max(width / 2, height / 2);
            return CurveFactory.CreateEllipse(r, r, new P2(0, 0));
          }

        case Shape.Box:
              if (nodeAttr.XRadius != 0 || nodeAttr.YRadius != 0)
                  return CurveFactory.CreateRectangleWithRoundedCorners(width, height, nodeAttr.XRadius,
                                                                       nodeAttr.YRadius, new P2(0, 0));
              return CurveFactory.CreateRectangle(width, height, new P2(0, 0));


          case Shape.Diamond:
          return CurveFactory.CreateDiamond(
            width, height, new P2(0, 0));
              
          case Shape.House:
              return CurveFactory.CreateHouse(width, height, new P2());

          case Shape.InvHouse:
              return CurveFactory.CreateInvertedHouse(width, height, new P2());
          case Shape.Octagon:
              return CurveFactory.CreateOctagon(width, height, new P2());
#if DEBUG
          case Shape.TestShape:
              return CurveFactory.CreateTestShape(width, height);
#endif
      
        default:
          {
            //  Console.WriteLine("creating ellipse for shape {0}",nodeAttr.Shape);
            return new Ellipse(
              new P2(width / 2, 0), new P2(0, height / 2), new P2());
          }
      }
    }

        internal GraphmapsNode(Node node, LgNodeInfo lgNodeInfo, FrameworkElement frameworkElementOfNodeForLabelOfLabel,
            Func<Edge, GraphmapsEdge> funcFromDrawingEdgeToVEdge, Func<double> pathStrokeThicknessFunc)
        {
            PathStrokeThicknessFunc = pathStrokeThicknessFunc;
            LgNodeInfo = lgNodeInfo;
            Node = node;
            FrameworkElementOfNodeForLabel = frameworkElementOfNodeForLabelOfLabel;

            this.funcFromDrawingEdgeToVEdge = funcFromDrawingEdgeToVEdge;

            CreateNodeBoundaryPath();
            if (FrameworkElementOfNodeForLabel != null) {
                FrameworkElementOfNodeForLabel.Tag = this; //get a backpointer to the VNode 
                Common.PositionFrameworkElement(FrameworkElementOfNodeForLabel, node.GeometryNode.Center, 1);
                Panel.SetZIndex(FrameworkElementOfNodeForLabel, Panel.GetZIndex(BoundaryPath) + 1);
            }
            SetupSubgraphDrawing();
            Node.GeometryNode.BeforeLayoutChangeEvent += GeometryNodeBeforeLayoutChangeEvent;
            Node.Attr.VisualsChanged += (a, b) => Invalidate();         
           
        }

        internal VNode(Node node, FrameworkElement frameworkElementOfNodeForLabelOfLabel,
            Func<Edge, VEdge> funcFromDrawingEdgeToVEdge, Func<double> pathStrokeThicknessFunc) {
            PathStrokeThicknessFunc = pathStrokeThicknessFunc;
            Node = node;
            FrameworkElementOfNodeForLabel = frameworkElementOfNodeForLabelOfLabel;

            _funcFromDrawingEdgeToVEdge = funcFromDrawingEdgeToVEdge;

            CreateNodeBoundaryPath();
            if (FrameworkElementOfNodeForLabel != null) {
                FrameworkElementOfNodeForLabel.Tag = this; //get a backpointer to the VNode 
                Common.PositionFrameworkElement(FrameworkElementOfNodeForLabel, node.GeometryNode.Center, 1);
                Panel.SetZIndex(FrameworkElementOfNodeForLabel, Panel.GetZIndex(BoundaryPath) + 1);
            }
            SetupSubgraphDrawing();
            Node.Attr.VisualsChanged += (a, b) => Invalidate();
            Node.IsVisibleChanged += obj => {
                foreach (var frameworkElement in FrameworkElements) {
                    frameworkElement.Visibility = Node.IsVisible ? Visibility.Visible : Visibility.Hidden;
                }
            };
        }

        public bool DrawNode(Node node, object graphics)
        {
            Graphics g = (Graphics)graphics;

            var m = g.Transform;
            var saveM = g.Transform.Clone();
            //      g.SetClip(FillTheGraphicsPath(node.GeometryNode.BoundaryCurve));

            // This is supposed to flip the text around its center

            var c = (float)node.GeometryNode.Center.Y;
            using (var m2 = new System.Drawing.Drawing2D.Matrix(1, 0, 0, -1, 0, 2 * c))
            {
                m.Multiply(m2);
            }

            m.Translate(
                (float)node.GeometryNode.Center.X,
                (float)node.GeometryNode.Center.Y);

            g.Transform = m;

            var styleStack = GetStyleStack();
            var painter = new TextViewPainter(
                Layout, g,
                SystemColors.WindowText,
                SystemColors.Window,
                SystemFonts.DefaultFont, styleStack);
            var ptr = new TextPointer { Character = 0, Span = 0, Line = TextModel.StartPosition };
            painter.SetSelection(ptr, ptr);
            painter.PaintGdiPlus();
            g.Transform = saveM;
            g.ResetClip();

            saveM.Dispose();
       //     m.Dispose();
            return true;//returning false would enable the default rendering
        }

        bool DrawNode(DrawingNode node, object graphics) {
            Graphics g = (Graphics)graphics;
            Image image = ImageOfNode(node);

            //flip the image around its center
            using (System.Drawing.Drawing2D.Matrix m = g.Transform)
            {
                using (System.Drawing.Drawing2D.Matrix saveM = m.Clone())
                {

                    g.SetClip(FillTheGraphicsPath(node.GeometryNode.BoundaryCurve));
                    using (var m2 = new System.Drawing.Drawing2D.Matrix(1, 0, 0, -1, 0, 2 * (float)node.GeometryNode.Center.Y))
                        m.Multiply(m2);

                    g.Transform = m;
                    g.DrawImage(image, new PointF((float)(node.GeometryNode.Center.X - node.GeometryNode.Width / 2),
                        (float)(node.GeometryNode.Center.Y - node.GeometryNode.Height / 2)));
                    g.Transform = saveM;

                }
            }

            return true;//returning false would enable the default rendering
        }

        Node CreateDrawingNodeByUsingDialog() {
            RichTextBox richBox;
            var window = CreateNodeDialog(out richBox);
            window.ShowDialog();

            var r = new Random();
            var i = r.Next();

            var createdNode = new Node(i.ToString());
            var s = new TextRange(richBox.Document.ContentStart, richBox.Document.ContentEnd).Text;
            createdNode.LabelText = s.Trim('\r', '\n', ' ', '\t');
            return createdNode;
        }

        public void AddState(string id, bool isAccepting)
        {
            if (IsDuplicated(id))
                throw new ArgumentException("State ID is duplicated.");

            var state = new StateViewModel(id, isAccepting);
            states.Add(state);

            Node node = new Node(id);
            if (isAccepting)
                node.Attr.Shape = Shape.DoubleCircle;
            else
                node.Attr.Shape = Shape.Circle;
            graph.AddNode(node);

            if (InitialStateIndex == -1)
                InitialStateIndex = 0;
        }

        private void CreateTargetNode(Node a) {
            a.Attr.Shape = Microsoft.Msagl.Drawing.Shape.DoubleCircle;
            a.Attr.FillColor = Microsoft.Msagl.Drawing.Color.LightGray;

            a.Attr.LabelMargin = -4;
            a.UserData = this;
        }