This is a migrated thread and some comments may be shown as answers.

Slow drawing with many connections outgoing the same node

12 Answers 120 Views

Diagram

This is a migrated thread and some comments may be shown as answers.

Hassan asked on 12 Feb 2015, 03:53 PM

Hello,



when I populate the graph with so many connections outgoing from a specific node, it takes so so so much time!



Here is my graph source




class GraphSource : GraphSourceBase<Node, Link>
        {
            List<Cluster> clusters = new List<Cluster>();
            public GraphSource()
            {
                 Cluster c1 = new Cluster("Cluster1");
                Cluster c2 = new Cluster("Cluster2");
                Cluster c3 = new Cluster("Cluster3");
                Cluster c4 = new Cluster("Cluster4");
                Cluster c5 = new Cluster("Cluster5");
                Cluster c6 = new Cluster("Cluster6");
 
             
                ECU eCU1 = new ECU("ECU1");
                ECU eCU2= new ECU("ECU2");
                ECU eCU3 = new ECU("ECU3");
                ECU eCU4 = new ECU("ECU4");
                ECU eCU5 = new ECU("ECU5");
                ECU eCU6 = new ECU("ECU6");
                ECU eCU7 = new ECU("ECU7");
                ECU eCU8 = new ECU("ECU8");
                ECU eCU9 = new ECU("ECU9");
                ECU eCU10 = new ECU("ECU10");
                ECU eCU11 = new ECU("ECU11");
                ECU eCU12 = new ECU("ECU12");
                ECU eCU13 = new ECU("ECU13");
                ECU eCU14 = new ECU("ECU14");
                ECU eCU15 = new ECU("ECU15");
                ECU eCU16 = new ECU("ECU16");
                ECU eCU17 = new ECU("ECU17");
                ECU eCU18 = new ECU("ECU18");
                ECU eCU19 = new ECU("ECU19");
                ECU eCU20 = new ECU("ECU20");
 
                c1.AddECU(eCU1);
                c1.AddECU(eCU2);
                c1.AddECU(eCU3);
                c1.AddECU(eCU4);
                c1.AddECU(eCU5);
 
                c2.AddECU(eCU1);
                c2.AddECU(eCU6);
                c2.AddECU(eCU7);
                c2.AddECU(eCU8);
                c2.AddECU(eCU9);
                c2.AddECU(eCU10);
                c2.AddECU(eCU11);
                c2.AddECU(eCU12);
                c2.AddECU(eCU13);
 
                c3.AddECU(eCU13);
                c3.AddECU(eCU17);
                c3.AddECU(eCU18);
                c3.AddECU(eCU19);
 
                c4.AddECU(eCU11);
                c4.AddECU(eCU12);
                c4.AddECU(eCU13);
                c4.AddECU(eCU14);
 
                c5.AddECU(eCU15);
                c5.AddECU(eCU16);
                c5.AddECU(eCU17);
                c5.AddECU(eCU18);
 
                c6.AddECU(eCU19);
                c6.AddECU(eCU20);
 
                clusters.Add(c1);
                clusters.Add(c2);
                clusters.Add(c3);
                clusters.Add(c4);
                clusters.Add(c5);
                clusters.Add(c6);
            }
 
 
            public void PopulateGraph()
            {
                foreach (Cluster cluster in clusters)
                {
 
                    Node vNode = new Node() { Width=10,Height=10};
 
                    this.AddNode(vNode);
                    foreach (ECU eCU in cluster.GetECUs())
                    {
 
                        IEnumerable<Node> res = from Node nn in this.Items where eCU.Name.Equals(nn.Content) select nn;
 
                        if (res.Count() == 0)
                        {
                            Node eNode = new Node() { Content = eCU.Name };
                            this.AddNode(eNode);
                            this.AddLink(new Link(vNode, eNode));
                        }
                        else
                        {
                            this.AddLink(new Link(vNode, res.First()));
                        }
 
                    }
                }
 
            }
 
        }





Thanks in advance,

Hassan

12 Answers, 1 is accepted

answered on 16 Feb 2015, 11:49 AM

The binding of the Node properties (Visibility, Height, Width and Content) was the reason

<Style x:Key="NodeStyle" TargetType="telerik:RadDiagramShape">

<Setter Property="Visibility" Value="{Binding Visibility }" />

<Setter Property="Height" Value="{Binding Height}" />

<Setter Property="Width" Value="{Binding Width}" />

<Setter Property="ContentTemplate">

<Setter.Value>

<DataTemplate >

<TextBlock Text="{Binding Content}" />

</DataTemplate>

</Setter.Value>

</Setter>

</Style>

But how to achieve the same results without such binding?

answered on 16 Feb 2015, 01:23 PM

Hi Hassan,

What's the number of Connections and could you please try setting RouteConnections = False to check whether this improves the performance ? Also, is there any change in performance if you do not set the AStarRouter ? Is it possible for you to open a new support thread with an isolated project that we can investigate ? Possible you may have hit a corner case which we are not aware of. If sending a project is not an option we can also prepare a sample that can serve as a base for our discussions here or in new support thread.
Thank you in advance for your cooperation. We are looking forward to your reply since performance in Diagram is with priority for us.

Regards,
Petar Mladenov
Telerik

Check out the Telerik Platform - the only platform that combines a rich set of UI tools with powerful cloud services to develop web, hybrid and native mobile apps.

answered on 16 Feb 2015, 04:56 PM

One issue we had with the AStar implementation is there is no limit on the number of attempts to route a connection. In the Route function, there is a while loop that runs until it finds the optimal route but there are cases where it can never find it. This occurs regularly on diagrams where there is a large number of shapes and the distance between your source and target are large and/or there is a lot of other objects between the two. Containers also seem to cause problems as well.

Because the offending function is private, we had to bring out all the code into a new router type, LocalAStarRouter and add in a property called MaxItterations which set the maximum number of times to attempt to route before giving up. We used 500 as a default. We then added in a check inside the while loop inside the Route function which checked if we had past the number of attempts and if so, return the failurePath. I don't know if I'm allowed to paste the whole routine but here is a snippet of the modification:

public int MaxIterations { get; set; }

/// <summary>

/// Initializes a new instance of the <see cref="AStarRouter"/> class.

/// </summary>

/// <param name="diagram">The related diagram.</param>

public LocalAStarRouter(IGraphInternal diagram)

{

if (diagram == null)

{

throw new ArgumentNullException("diagram");

}

this.diagram = diagram;

this.cameFrom = new Dictionary<AStarNode, AStarNode>();

this.orderedOpenSet = new PriorityQueue<AStarNode, double>(OrderType.Ascending);

MaxIterations = 500;

}

private IList<Point> Route(Orientation startOrientation, Point startPoint, Point endPoint, Rect endWall, double gridSize)

{

var failurePath = new List<Point>() { startPoint, endPoint };

var iterations = 0;

this.cameFrom.Clear();

this.orderedOpenSet.Clear();

var startNode = this.stepGenerator.GenerateNode(startPoint);

var endNode = this.stepGenerator.GenerateNode(endPoint);

startNode.G = 0;

startNode.H = Heuristic(startNode, endNode);

startNode.F = startNode.G + startNode.H;

this.orderedOpenSet.Push(startNode, startNode.F);

//// If start and end are close to each other.

if (IsInSquare(startPoint, endPoint, gridSize))

{

return failurePath;

}

try

{

while (true)

{

var node = this.orderedOpenSet.Pop();

node.IsOpen = false;

if (iterations > MaxIterations) //Perform check to see if we have past the max attempts

return failurePath; //Return the failurePath which was already created

iterations += 1;

if (IsPathDivergent(node, startNode, gridSize))

{

return failurePath;

}

The rest of the code for the router is the unmodified.

Hope this helps,
Shawn