LayeredDigraphLayout + Virtualization

Hello,

I changed the “Virtualizing” sample from TreeLayout to LayeredDiagramLayout - but the result doesn’t seem to be correct. All nodes are positioned one on top of the other (with slight variations of Y coordinate). So,

  1. Is it enough to change TreeLayout* classes to LayeredDiagramLayout* counterparts? It doesn’t seem to be the case. For example, FindRoots method is absent in LayeredDiagramLayout. Plus it doesn’t work, so i am sure i am missing something


    2) Is there a sample of virtualized LayeredDigramLayout?
  1. Well, I think that is basically what needs to be done. But clearly there are no “roots” in LayeredDigraphLayout, so there are bound to be real differences too.

  2. I can ask around, but I do not recall anyone at Northwoods Software doing this. Still doing step (1) shouldn’t be too hard if you do not need the layout’s custom routing. But you probably do need that.

So, i just double-checked: simple replacement doesn’t work because layouting fails to properly arrange nodes. I changed the number of nodes to 99 because too many of them are displayed at the same time:

Ah, what’s missing are overrides of several LayeredDigraphLayout methods: NodeMinLayerSpace, NodeMinColumnSpace, and LinkStraightenWeight, which normally depend on LayoutVertex.Node being null to mean that it’s a dummy vertex, not a vertex corresponding to a real Node. But since there’s aren’t any real Nodes, …

Note that the following code does NOT do the routing that LayeredDigraphLayout normally does when it is operating on real Links. I’m not sure there’s an easy solution for that.

[code]

<FrameworkElement.Resources>

<go:NodePanel Sizing=“Fixed”
go:Part.SelectionAdorned=“True”
go:Node.Location="{Binding Path=Data.Location, Mode=TwoWay}"
go:Node.LocationSpot=“Center”>
<go:NodeShape go:NodePanel.Figure=“RoundedRectangle”
Width="{Binding Path=Data.Width}"
Height="{Binding Path=Data.Height}"
Fill="{Binding Path=Data.Color}" Stroke=“Black” StrokeThickness=“1” />

</go:NodePanel>

<DataTemplate x:Key="LinkTemplate">
  <go:LinkPanel>
    <go:Link.Route>
      <go:Route FromSpot="MiddleRight" ToSpot="MiddleLeft" />
    </go:Link.Route>
    <go:LinkShape Stroke="Black" />
  </go:LinkPanel>
</DataTemplate>

</FrameworkElement.Resources>

[/code] [code]/* Copyright © Northwoods Software Corporation, 2008-2014. All Rights Reserved. */

// This sample demonstrates one way to implement virtualization of the Nodes and Links
// needed for displaying a very large model.
// It depends on the locations and sizes of the Nodes being known in the model
// before the Nodes are actually created.
// Thus using a standard diagram layout is incompatible with this assumption,
// because a normal layout will need to consider the actual sizes of the Nodes
// in order to assign reasonable Locations for those Nodes, but the Nodes have to
// exist already to do so.

// You need to customize the VirtualizingPartManager.ComputeNodeBounds method to
// account for the actual Node DataTemplates used in your application.

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Windows;
using System.Windows.Controls;
using Northwoods.GoXam;
using Northwoods.GoXam.Layout;
using Northwoods.GoXam.Model;

namespace VirtualizingLD {
public partial class VirtualizingLD : UserControl {
public VirtualizingLD() {
InitializeComponent();

  // automatically load all of the data AFTER this UserControl has
  // been displayed in the visual tree of the demo app
  myDiagram.Loaded += (s, e) => {
    myDiagram.Dispatcher.BeginInvoke((Action)(() => { LoadData(); }));
  };
}

// Create some sample data.
private void LoadData() {
  var model = new GraphLinksModel<NodeData, String, String, LinkData>();
  var nodes = GenerateNodes();
  model.NodesSource = nodes;
  var links = GenerateLinks(nodes);
  model.LinksSource = links;
  model.Modifiable = true;

  var vpm = (VirtualizingPartManager)myDiagram.PartManager;
  // in production usage you'll probably want to remove these status updates,
  // which slows down scrolling and zooming
  vpm.Status = () => {
    myStatus.Text = "created " + vpm.NodesCount.ToString() + "/" + nodes.Count.ToString() + " nodes," +
      "  " + vpm.LinksCount.ToString() + "/" + links.Count.ToString() + " links."
      + "  " + myDiagram.Panel.DiagramBounds.ToString();
  };

  // NOTE: regular DiagramLayouts (such as LayeredDigraphLayout) will not work with this virtualizing scheme!
  // You need to make sure VirtualizingPartManager.ComputeNodeBounds returns good values
  // for every NodeData object.

  // just in case you set model.Modifiable = true, this makes sure the viewport is updated after every transaction:
  model.Changed += (s, e) => {
    if (e.Change == ModelChange.CommittedTransaction || e.Change == ModelChange.FinishedUndo || e.Change == ModelChange.FinishedRedo) {
      vpm.UpdateViewport(myDiagram.Panel.ViewportBounds, myDiagram.Panel.ViewportBounds);
    }
  };

  // do the initial layout *before* assigning to the Diagram.Model --
  // this avoids creating all of the Nodes and Links and then throwing away everything
  // outside of the viewport
  Layout(model);

  // initialize the Diagram with the model and its data
  myDiagram.Model = model;

  // remove the "Loading..." status indicator
  var loading = myDiagram.PartsModel.FindNodeByKey("Loading");
  if (loading != null) myDiagram.PartsModel.RemoveNode(loading);
}

Random rand = new Random();

// Takes the random collection of nodes and creates a random graph with them.
private ObservableCollection<LinkData> GenerateLinks(ObservableCollection<NodeData> nodes) {
  var linkSource = new ObservableCollection<LinkData>();
  if (nodes.Count < 2) return linkSource;
  for (int i = 0; i < nodes.Count-1; i++) {
    NodeData from = nodes[i];
    int numto = 1+rand.Next(3)/2;
    for (int j = 0; j < numto; j++) {
      int idx = i+5+rand.Next(10);
      if (idx >= nodes.Count) idx = i+rand.Next(nodes.Count-i);
      NodeData to = nodes[idx];
      linkSource.Add(new LinkData() { From = from.Key, To = to.Key });
    }
  }
  return linkSource;
}

// Creates a collection of randomly colored nodes.
// Respects the maximum and minimum number of nodes.
private ObservableCollection<NodeData> GenerateNodes() {
  var nodeSource = new ObservableCollection<NodeData>();
  int minNodes = 300;
  int maxNodes = 500;
  int numberOfNodes = rand.Next(minNodes, maxNodes + 1);

  for (int i = 0; i < numberOfNodes; i++) {
    nodeSource.Add(new NodeData() {
      Key = "Node" + i.ToString(),
      Color = String.Format("#{0:X}{1:X}{2:X}", 120+rand.Next(100), 120+rand.Next(100), 120+rand.Next(100))
    });
  }
  return nodeSource;
}

// Perform nested layouts of Groups first, then do top-level Diagram.Layout
private void Layout(ILinksModel model) {
  ISubGraphLinksModel sgmodel = model as ISubGraphLinksModel;
  foreach (NodeData d in model.NodesSource) {
    if (sgmodel != null && sgmodel.GetIsGroupForNode(d) && sgmodel.GetGroupForNode(d) == null) {
      LayoutSubGraph(d, sgmodel);
    }
  }
  VirtualizingLayeredDigraphLayout layout = myDiagram.Layout as VirtualizingLayeredDigraphLayout;
  if (layout != null) {
    layout.Model = model;
    layout.DoLayout(null, null);  // no Nodes or Links exist!
  }
  // now need to position all NodeData inside subgraphs accurately
  foreach (NodeData d in model.NodesSource) {
    if (sgmodel != null && sgmodel.GetIsGroupForNode(d) && sgmodel.GetGroupForNode(d) == null) {
      CommitSubGraph(d, d.Location, sgmodel);
    }
  }
}

// We cannot get the Group.Layout property value without first creating the Group,
// which virtualization is trying to avoid.  So you will need to customize this method
// to return a new VirtualizingLayeredDigraphLayout with the properties that you want for the
// given NodeData represented by a Group.
private VirtualizingLayeredDigraphLayout GetLayoutForGroup(NodeData sg) {
  return new VirtualizingLayeredDigraphLayout() {
  };
}

private void LayoutSubGraph(NodeData sg, ISubGraphLinksModel model) {
  // recurse into nested groups first
  foreach (NodeData m in model.GetMemberNodesForGroup(sg)) {
    if (model.GetIsGroupForNode(m)) {
      LayoutSubGraph(m, model);
    }
  }
  // now do this group's layout
  VirtualizingLayeredDigraphLayout layout = GetLayoutForGroup(sg);
  if (layout != null) {
    layout.Model = model;
    layout.SubGraph = sg;
    layout.DoLayout(null, null);  // no Nodes or Links exist!
    // and record the resulting size of the group in the data
    Rect gb = Rect.Empty;
    foreach (NodeData m in model.GetMemberNodesForGroup(sg)) {
      if (m.IsSubGraph) {
        m.Location = new Point(m.Location.X + VirtualizingPartManager.GroupHeaderWidth,
                               m.Location.Y + VirtualizingPartManager.GroupHeaderHeight);
      }
      Rect b = VirtualizingPartManager.ComputeNodeBounds(m);
      if (gb.IsEmpty) {
        gb = b;
      } else {
        gb.Union(b);
      }
    }
    if (gb.IsEmpty) gb = new Rect(0, 0, 100, 20);
    gb.X -= VirtualizingPartManager.GroupPadding;
    gb.Y -= VirtualizingPartManager.GroupPadding;
    gb.Width += 2*VirtualizingPartManager.GroupPadding;
    gb.Height += 2*VirtualizingPartManager.GroupPadding;
    // this specifies the size and location of the subgraph (i.e. GroupPanel), not the whole Group:
    sg.Width = gb.Width;
    sg.Height = gb.Height;
    sg.Location = new Point(gb.X + gb.Width/2, gb.Y + gb.Height/2);
  }
}

private void CommitSubGraph(NodeData sg, Point offset, ISubGraphLinksModel model) {
  offset.X += VirtualizingPartManager.GroupPadding;
  offset.Y += VirtualizingPartManager.GroupPadding;
  foreach (NodeData m in model.GetMemberNodesForGroup(sg)) {
    m.Location = new Point(m.Location.X+offset.X-sg.Width/2, m.Location.Y+offset.Y-sg.Height/2);
    if (model.GetIsGroupForNode(m)) {
      CommitSubGraph(m, m.Location, model);
    }
  }
}

private void CollapseExpandButton_Click(object sender, RoutedEventArgs e) {
  // the Button is in the visual tree of a Node
  Button button = (Button)sender;
  Group sg = Part.FindAncestor<Group>(button);
  if (sg != null) {
    NodeData subgraphdata = (NodeData)sg.Data;
    if (!subgraphdata.IsSubGraph) return;
    // always make changes within a transaction
    myDiagram.StartTransaction("CollapseExpand");
    if (sg.IsExpandedSubGraph) {
      subgraphdata.NormalWidth = subgraphdata.Width;
      subgraphdata.NormalHeight = subgraphdata.Height;
      subgraphdata.Width = 10;
      subgraphdata.Height = 10;
    } else {
      subgraphdata.Width = subgraphdata.NormalWidth;
      subgraphdata.Height = subgraphdata.NormalHeight;
    }
    // toggle whether this node is expanded or collapsed
    sg.IsExpandedSubGraph = !sg.IsExpandedSubGraph;
    myDiagram.CommitTransaction("CollapseExpand");
  }
}

}

// This assumes that we can determine the Bounds, in model coordinates, for each data object,
// without having to apply the DataTemplate to create the FrameworkElements in the visual tree.
// You will need to implement the ComputeNodeBounds method for your application.
// In this sample the Location is computed by a VirtualLayeredDigraphLayout
// and the Width and Height are assumed to come from the NodeData class.
public class VirtualizingPartManager : PartManager {

// The viewport has changed -- create new nodes and links that should now be visible
public void UpdateViewport(Rect oldview, Rect newview) {
  this.ViewportBounds = newview;

  Diagram diagram = this.Diagram;
  IDiagramModel model = diagram.Model;
  if (!this.OffscreenQueued) {
    // don't immediately remove nodes and links that have scrolled out of the viewport
    this.OffscreenQueued = true;
    diagram.Dispatcher.BeginInvoke((Action)RemoveOffscreen);
  }
  // maybe create Nodes
  foreach (Object data in model.NodesSource) {
    var node = AddNodeForData(data, model);
    if (node != null && this.SelectedOffscreenNodeData.Contains(data)) {
      this.SelectedOffscreenNodeData.Remove((NodeData)data);
      node.IsSelected = true;
    }
  }
  ILinksModel lmodel = model as ILinksModel;
  if (lmodel != null) {
    // maybe create Links
    foreach (Object data in lmodel.LinksSource) {
      AddLinkForData(data, lmodel);
    }
  }

  // You might want to delete this statement, for efficiency:
  if (this.Status != null) this.Status();
}

public Rect ViewportBounds { get; set; }

// Customize when the PartManager creates Nodes -- when in the viewport or
// when connecting with a link that is in the viewport
protected override bool FilterNodeForData(object nodedata, IDiagramModel model) {
  NodeData data = nodedata as NodeData;
  if (data == null) return true;
  // don't create Node with unknown Location
  if (Double.IsNaN(data.Location.X) || Double.IsNaN(data.Location.Y)) return false;
  // see if the Node would be in the viewport
  Rect thisb = ComputeNodeBounds(data);
  if (Intersects(this.ViewportBounds, thisb)) return true;
  // or if the Node is connected to with a Link that is in the viewport
  foreach (Object otherdata in model.GetConnectedNodesForNode(nodedata)) {
    Rect linkb = thisb;
    linkb.Union(ComputeNodeBounds(otherdata as NodeData));
    if (Intersects(this.ViewportBounds, linkb)) return true;
  }
  return false;
}

public const double GroupPadding = 10;  // what would be GroupPanel.Padding
public const double GroupHeaderWidth = 0;  // on left side of what would be the GroupPanel
public const double GroupHeaderHeight = 18;  // above what would be the GroupPanel

// Account for actual node size, because it would normally be unknown
// until after the Node was actually created and measured.
public static Rect ComputeNodeBounds(NodeData data) {
  // Remember to take the relative Location into account.
  // This assumes the LocationSpot is at the Center of the whole node.
  if (data.IsSubGraph) {
    return new Rect(data.Location.X - data.Width/2 - VirtualizingPartManager.GroupHeaderWidth,
                    data.Location.Y - data.Height/2 - VirtualizingPartManager.GroupHeaderHeight,
                    data.Width + VirtualizingPartManager.GroupHeaderWidth,
                    data.Height + VirtualizingPartManager.GroupHeaderHeight);
  } else {
    return new Rect(data.Location.X - data.Width/2, data.Location.Y - data.Height/2, data.Width, data.Height);
  }
}

// Customize when the PartManager creates Links
protected override bool FilterLinkForData(object linkdata, IDiagramModel model) {
  LinkData data = linkdata as LinkData;
  if (data == null) return true;
  return IsOnscreen(data, model);
}

private bool IsOnscreen(LinkData data, IDiagramModel model) {
  if (data == null) return false;
  NodeData from = model.FindNodeByKey(data.From) as NodeData;
  if (from == null) return false;
  NodeData to = model.FindNodeByKey(data.To) as NodeData;
  if (to == null) return false;
  Rect b = ComputeNodeBounds(from);
  b.Union(ComputeNodeBounds(to));
  return Intersects(this.ViewportBounds, b);
}

// Customize when the PartManager creates Links if the model is not an ILinksModel
protected override bool FilterLinkForData(object fromnodedata, object tonodedata, IDiagramModel model) {
  Rect b = ComputeNodeBounds(fromnodedata as NodeData);
  b.Union(ComputeNodeBounds(tonodedata as NodeData));
  return Intersects(this.ViewportBounds, b);
}

private bool OffscreenQueued { get; set; }
private HashSet<NodeData> SelectedOffscreenNodeData = new HashSet<NodeData>();

// To reduce memory usage, remove existing Nodes and Links that are no longer within the viewport
private void RemoveOffscreen() {
  this.OffscreenQueued = false;

  IDiagramModel model = this.Diagram.Model;
  var offscreennodes = new List<Node>();
  foreach (Node n in this.Diagram.Nodes) {
    if (!FilterNodeForData(n.Data, model)) offscreennodes.Add(n);
  }
  foreach (Node n in offscreennodes) {
    if (n.IsSelected) {
      this.SelectedOffscreenNodeData.Add((NodeData)n.Data);
    }
    RemoveNodeForData(n.Data, model);
  }

  var offscreenlinks = new List<Link>();
  foreach (Link l in this.Diagram.Links) {
    LinkData data = l.Data as LinkData;
    if (data == null) continue;
    if (!IsOnscreen(data, model)) offscreenlinks.Add(l);
  }
  foreach (Link l in offscreenlinks) {
    RemoveLinkForData(l.Data, model);
  }

  // You might want to delete this statement, for efficiency:
  if (this.Status != null) this.Status();
}

// this property is just for informational feedback -- you can delete this:
public Action Status { get; set; }

// Compute intersection of Rects, handling Infinity and NaN properly.
private static bool Intersects(Rect a, Rect b) {
  double tw = a.Width;
  double rw = b.Width;
  double tx = a.X;
  double rx = b.X;
  if (!Double.IsPositiveInfinity(tw) && !Double.IsPositiveInfinity(rw)) {
    tw += tx;
    rw += rx;
    if (Double.IsNaN(rw) || Double.IsNaN(tw) || tx > rw || rx > tw) return false;
  }

  double th = a.Height;
  double rh = b.Height;
  double ty = a.Y;
  double ry = b.Y;
  if (!Double.IsPositiveInfinity(th) && !Double.IsPositiveInfinity(rh)) {
    th += ty;
    rh += ry;
    if (Double.IsNaN(rh) || Double.IsNaN(th) || ty > rh || ry > th) return false;
  }
  return true;
}

}

// This customized DiagramPanel calls VirtualizingPartManager.UpdateViewport when needed
public class VirtualizingDiagramPanel : DiagramPanel {
// replace this functionality to take into account non-existent Nodes
protected override Rect ComputeDiagramBounds() {
Rect db = Rect.Empty;
foreach (NodeData data in this.Diagram.Model.NodesSource) {
Rect b = VirtualizingPartManager.ComputeNodeBounds(data);
if (db.IsEmpty) {
db = b;
} else {
db.Union(b);
}
}
if (db.IsEmpty) db = new Rect(0, 0, 0, 0);
Thickness pad = this.Padding;
db.X -= pad.Left;
db.Width += pad.Left + pad.Right;
db.Y -= pad.Top;
db.Height += pad.Top + pad.Bottom;
return db;
}

// whenever the viewport changes, maybe create or remove some Nodes and Links
protected override void OnViewportBoundsChanged(RoutedPropertyChangedEventArgs<Rect> e) {
  var vpm = this.Diagram.PartManager as VirtualizingPartManager;
  if (vpm != null) vpm.UpdateViewport(e.OldValue, e.NewValue);
  base.OnViewportBoundsChanged(e);
}

}

// Virtualizing LayeredDigraphLayout classes

// Here we try to ignore all methods and properties that deal with Nodes or Links.
// Instead we use Vertex and Edge classes that know about the model data.
// This layout implementation assumes the use of a GraphLinksModel (i.e. an ILinksModel).
public class VirtualizingLayeredDigraphLayout : LayeredDigraphLayout {

public ILinksModel Model { get; set; }

public NodeData SubGraph { get; set; }  // the containing group's data

public override LayeredDigraphNetwork CreateNetwork() {
  return new VirtualizingLayeredDigraphNetwork();
}

// ignore the arguments, because they assume the existence of Nodes and Links
public override LayeredDigraphNetwork MakeNetwork(IEnumerable<Node> nodes, IEnumerable<Link> links) {
  var net = (VirtualizingLayeredDigraphNetwork)CreateNetwork();
  if (this.Model != null) {
    if (this.SubGraph != null) {  // just add members of the given group
      net.AddSubGraph(this.SubGraph, this.Model as ISubGraphLinksModel);
    } else {  // add all top-level nodes and links
      net.AddTopLevelGraph(this.Model);
    }
  }
  return net;
}

protected override double NodeMinLayerSpace(LayeredDigraphVertex v, bool topleft) {
  var vv = v as VirtualizingLayeredDigraphVertex;
  if (vv != null && vv.Data == null) return 0;
  Rect r = v.Bounds;
  Point p = v.Focus;
  if (this.Direction == 90 || this.Direction == 270) {
    if (topleft)
      return p.Y+10;
    else
      return r.Height-p.Y+10;
  } else {
    if (topleft)
      return p.X+10;
    else
      return r.Width-p.X+10;
  }
}

protected override int NodeMinColumnSpace(LayeredDigraphVertex v, bool topleft) {
  var vv = v as VirtualizingLayeredDigraphVertex;
  if (vv != null && vv.Data == null) return 0;
  Rect r = v.Bounds;
  Point p = v.Focus;
  if (this.Direction == 90 || this.Direction == 270) {
    if (topleft)
      return (int)(p.X/this.ColumnSpacing) + 1;
    else
      return (int)((r.Width-p.X)/this.ColumnSpacing) + 1;
  } else {
    if (topleft)
      return (int)(p.Y/this.ColumnSpacing) + 1;
    else
      return (int)((r.Height-p.Y)/this.ColumnSpacing) + 1;
  }
}

protected override double LinkStraightenWeight(LayeredDigraphEdge edge) {
  var fromVertex = edge.FromVertex as VirtualizingLayeredDigraphVertex ;
  var toVertex = edge.ToVertex as VirtualizingLayeredDigraphVertex;

  if ((fromVertex != null && fromVertex.Data == null) && (toVertex != null && toVertex.Data == null))
    return 8;

  if ((fromVertex != null && fromVertex.Data == null) || (toVertex != null && toVertex.Data == null))
    return 4;

  return 1;
}

}

// Use Virtualizing versions of Vertex and Edge.
public class VirtualizingLayeredDigraphNetwork : LayeredDigraphNetwork {
public override LayeredDigraphVertex CreateVertex() {
return new VirtualizingLayeredDigraphVertex();
}

public override LayeredDigraphEdge CreateEdge() {
  return new VirtualizingLayeredDigraphEdge();
}

private Dictionary<NodeData, VirtualizingLayeredDigraphVertex> NodeDataMap = new Dictionary<NodeData, VirtualizingLayeredDigraphVertex>();
private Dictionary<LinkData, VirtualizingLayeredDigraphEdge> LinkDataMap = new Dictionary<LinkData, VirtualizingLayeredDigraphEdge>();

// a replacement for LayeredDigraphNetwork.AddNodesAndLinks using top-level model data instead of Nodes or Links
public void AddTopLevelGraph(ILinksModel model) {
  if (model == null) return;
  NodeDataMap.Clear();
  LinkDataMap.Clear();
  ISubGraphLinksModel sgmodel = model as ISubGraphLinksModel;
  var nodes = model.NodesSource as IEnumerable<NodeData>;
  foreach (NodeData d in nodes) {
    if (sgmodel == null || sgmodel.GetGroupForNode(d) == null) {
      AddNodeData(d, model);
    }
  }
  var links = model.LinksSource as IEnumerable<LinkData>;
  foreach (LinkData d in links) {
    if (sgmodel == null || sgmodel.GetGroupForLink(d) == null) {
      AddLinkData(d, model);
    }
  }
}

// a replacement for LayeredDigraphNetwork.AddNodesAndLinks using a group's members' model data instead of Nodes or Links
public void AddSubGraph(NodeData sg, ISubGraphLinksModel model) {
  if (sg == null || model == null) return;
  NodeDataMap.Clear();
  LinkDataMap.Clear();
  foreach (NodeData d in model.GetMemberNodesForGroup(sg)) {
    AddNodeData(d, model);
  }
  foreach (LinkData d in model.GetMemberLinksForGroup(sg)) {
    AddLinkData(d, model);
  }
}

public void AddNodeData(NodeData d, ILinksModel model) {
  if (NodeDataMap.ContainsKey(d)) return;
  // create and add VirtualizingLayeredDigraphVertex
  var v = (VirtualizingLayeredDigraphVertex)CreateVertex();
  v.Data = d;
  NodeDataMap.Add(d, v);
  AddVertex(v);
}

public void AddLinkData(LinkData d, ILinksModel model) {
  if (LinkDataMap.ContainsKey(d)) return;
  // find connected node data
  var from = (NodeData)model.FindNodeByKey(d.From);
  var to = (NodeData)model.FindNodeByKey(d.To);
  if (from == null || to == null || from == to) return;  // skip
  // now find corresponding vertexes
  VirtualizingLayeredDigraphVertex f;
  NodeDataMap.TryGetValue(from, out f);
  VirtualizingLayeredDigraphVertex t;
  NodeDataMap.TryGetValue(to, out t);
  if (f == null || t == null) return;  // skip
  // create and add VirtualizingLayeredDigraphEdge
  var e = (VirtualizingLayeredDigraphEdge)CreateEdge();
  e.Data = d;
  e.FromVertex = f;
  e.ToVertex = t;
  AddEdge(e);
}

}

// Associate with NodeData rather than with Node.
public class VirtualizingLayeredDigraphVertex : LayeredDigraphVertex {
public NodeData Data {
get { return _Data; }
set {
_Data = value;
if (_Data != null) {
// use bounds information from the NodeData rather than the Node.Bounds!
this.Focus = new Point(_Data.Width/2, _Data.Height/2);
this.Bounds = VirtualizingPartManager.ComputeNodeBounds(_Data);
}
}
}
private NodeData _Data = null;

public override void CommitPosition() {
  if (this.Data != null) {
    this.Data.Location = this.Center;  // set NodeData.Location instead of Node.Location!
  } else {
    base.CommitPosition();
  }
}

}

// Associate with LinkData rather than with Link.
// NOTE: This does not support custom routing of links that is normally done by LayeredDigraphLayout
public class VirtualizingLayeredDigraphEdge : LayeredDigraphEdge {
public LinkData Data { get; set; }
}

// Model data classes

public class NodeData : GraphLinksModelNodeData {
// assume this won’t change dynamically, so don’t need to call RaisePropertyChanged
public String Color { get; set; }

public double Width {
  get { return _Width; }
  set { if (_Width != value) { double old = _Width; _Width = value; RaisePropertyChanged("Width", old, value); } }
}
private double _Width = 100;
public double NormalWidth { get; set; }

public double Height {
  get { return _Height; }
  set { if (_Height != value) { double old = _Height; _Height = value; RaisePropertyChanged("Height", old, value); } }
}
private double _Height = 50;
public double NormalHeight { get; set; }

}

public class LinkData : GraphLinksModelLinkData<String, String> { }
}[/code]

thank you, that seems to work!