Using WPF to Visualize a Graph with Circular Dependencies

• Download source code (requires Visual Studio 2008 SP1) - 88.7 KB

Introduction

This article presents a WPF application that renders an object graph which the user can rearrange via drag-and-drop. The graph highlights all circular dependencies between its nodes. The application was built in Visual Studio 2008, and compiled against the .NET Framework v3.5 with Service Pack 1.

Background

Recently at work, I wrote some code that analyzed an object graph in order to determine the order in which its objects should be initialized. The requirement was to initialize the objects on which an object depends before initializing that object. In a scenario like that, the object graph cannot contain any circular dependencies (i.e., where an object indirectly depends on itself, such as object A depends on object B, and object B depends on object A).

After implementing that logic, I thought it would be interesting to create a user interface that showed an object graph and highlighted any circular dependencies it contained. This weekend, I had some free time, so I wrote the application described in this article which does exactly that.

What the program does

The simplest example of what this application does is shown in the following screenshot:

The object graph seen above has only four nodes and no circular dependencies. Each node in a graph can be moved by the user so that he or she can arrange the objects into whatever layout makes the most sense. After rearranging the graph seen previously, it can look like this:

Now, let’s take a look at a graph that contains a circular dependency:

The nodes and node connectors that are part of the circular dependency are highlighted in red. Notice how this graph has a button in the top right corner. Clicking on that button causes the graph to perform a 3D flip, and shows a detailed listing of all circular dependencies in the graph, as seen below:

There is a more complicated graph in the application that contains three circular dependencies:

Notice how the mouse cursor over the node connector on the left side has brought up a tooltip that explains which nodes are associated with that connector. In this example, the node connector links two nodes that both depend on each other. If we were to flip this graph over, the details view would list all three circular dependencies in the graph, like this:

Now that we’ve seen what this application does, let’s take a look at how it works.

Building a graph

The data shown by a graph could come from anywhere. In this application, the data for each graph comes from an XML file included in the source code. The following XML describes the simplest graph in the application (the first graph seen in the previous section of this article):

<?xml version="1.0" encoding="utf-8" ?>
<graph title="Simple Graph">
  <node id="A" x="50" y="50">
    <dependency id="B" />
  </node>
  <node id="B" x="50" y="150">
    <dependency id="C" />
    <dependency id="D" />
  </node>
  <node id="C" x="50" y="250">
    <dependency id="D" />
  </node>
  <node id="D" x="200" y="175" />
</graph>

This XML will be converted into an instance of the Graph class, which is seen in the following diagram:

As seen in the diagram above, the Graph class has a collection of Node objects and a collection of CircularDependency objects. Those types can be seen in the following diagram:

The CircularDependency class will come into play in the next section. The process of building an object graph only involves the Graph and Node classes. A Graph object is created by the GraphBuilder class. It reads an XML file and creates a Graph full of Nodes. That logic is seen below:

// In GraphBuilder.cs
static Graph BuildGraph(string xmlFileName)
{
    string path = string.Format(@"Graphs\{0}", xmlFileName);
    XDocument xdoc = XDocument.Load(path);

    // Create a graph.
    var graphElem = xdoc.Element("graph");
    string title = graphElem.Attribute("title").Value;
    var graph = new Graph(title);

    var nodeElems = graphElem.Elements("node").ToList();

    // Create all of the nodes and add them to the graph.
    foreach (XElement nodeElem in nodeElems)
    {
        string id = nodeElem.Attribute("id").Value;
        double x = (double)nodeElem.Attribute("x");
        double y = (double)nodeElem.Attribute("y");

        var node = new Node(id, x, y);
        graph.Nodes.Add(node);
    }

    // Associate each node with its dependencies.
    foreach (Node node in graph.Nodes)
    {
        var nodeElem = nodeElems.First(
            elem => elem.Attribute("id").Value == node.ID);

        var dependencyElems = nodeElem.Elements("dependency");
        foreach (XElement dependencyElem in dependencyElems)
        {
            string depID = dependencyElem.Attribute("id").Value;
            var dep = graph.Nodes.FirstOrDefault(n => n.ID == depID);
            if (dep != null)
                node.NodeDependencies.Add(dep);
        }
    }

    // Tell the graph to inspect itself for circular dependencies.
    graph.CheckForCircularDependencies();

    return graph;
}

The last part of the method seen above is a call to Graph’s CheckForCircularDependencies method. That method is the subject of the next section. Hold on, things are about to get interesting…

Detecting circular dependencies

The process of locating all circular dependencies in a graph is a cooperative effort between a Graph and all of its Nodes. The CheckForCircularDependencies method of the Graph class asks each node if it is part of circular dependencies. A node returns a CircularDependency object for each circle that it finds itself in. A node will continue to look for circular dependencies until it cannot find any more that include itself. Here is the Graph method that gets the processing underway:

// In Graph.cs
public void CheckForCircularDependencies()
{
    foreach (Node node in this.Nodes)
    {
        var circularDependencies = node.FindCircularDependencies();
        if (circularDependencies != null)
            this.ProcessCircularDependencies(circularDependencies);
    }
    this.CircularDependencies.Sort();
}

void ProcessCircularDependencies(List<CircularDependency> circularDependencies)
{
    foreach (CircularDependency circularDependency in circularDependencies)
    {
        if (circularDependency.Nodes.Count == 0)
            continue;

        if (this.CircularDependencies.Contains(circularDependency))
            continue;

        // Arrange the nodes into the order in which they were discovered.
        circularDependency.Nodes.Reverse();

        this.CircularDependencies.Add(circularDependency);

        // Inform each node that it is a member of the circular dependency.
        foreach (Node dependency in circularDependency.Nodes)
            dependency.CircularDependencies.Add(circularDependency);
    }
}

The real logic in this algorithm lies in Node’s FindCircularDependencies method. Let’s now turn our attention to that:

// In Node.cs
public List<CircularDependency> FindCircularDependencies()
{
    if (this.NodeDependencies.Count == 0)
        return null;

    var circularDependencies = new List<CircularDependency>();

    var stack = new Stack<NodeInfo>();
    stack.Push(new NodeInfo(this));

    NodeInfo current = null;
    while (stack.Count != 0)
    {
        current = stack.Peek().GetNextDependency();
        if (current != null)
        {
            if (current.Node == this)
            {
                var nodes = stack.Select(info => info.Node);
                circularDependencies.Add(new CircularDependency(nodes));
            }
            else
            {
                bool visited = stack.Any(info => info.Node == current.Node);
                if (!visited)
                    stack.Push(current);
            }
        }
        else
        {
            stack.Pop();
        }
    }
    return circularDependencies;
}

private class NodeInfo
{
    public NodeInfo(Node node)
    {
        this.Node = node;
        _index = 0;
    }

    public Node Node { get; private set; }

    public NodeInfo GetNextDependency()
    {
        if (_index < this.Node.NodeDependencies.Count)
        {
            var nextNode = this.Node.NodeDependencies[_index++];
            return new NodeInfo(nextNode);
        }
        return null;
    }

    int _index;
}

This logic only looks for a circular dependency that includes the node on which the FindCircularDependencies method was invoked. It makes use of the NodeInfo class to keep track of which dependencies to process next after processing all of a node's dependencies.

Rendering nodes

Building a graph of nodes and detecting circular dependencies is an interesting programming exercise, but the fun doesn’t stop there! An equally challenging and interesting problem to solve is rendering that graph to the screen. This section of the article explains how my app renders a graph of nodes and highlights circular dependencies.

A graph of nodes is displayed by the GraphView user control. It contains an ItemsControl whose ItemsSource is bound to the Nodes property of a Graph object. To enable coordinate-based positioning of the nodes, I could use a Canvas as the ItemsPanel. Instead, I chose to use my DragCanvas panel, so that the user can move the nodes around. The relevant XAML from GraphView is listed below:

<!-- In GraphView.xaml -->
<ItemsControl 
  Background="LightGray" 
  ItemsSource="{Binding Path=Nodes}"
  >
  <ItemsControl.ItemsPanel>
    <ItemsPanelTemplate>
      <jas:DragCanvas />
    </ItemsPanelTemplate>
  </ItemsControl.ItemsPanel>

  <ItemsControl.ItemTemplate>
    <DataTemplate>
      <Border Style="{StaticResource NodeBorderStyle}">
        <TextBlock Text="{Binding Path=ID}" />
      </Border>
    </DataTemplate>
  </ItemsControl.ItemTemplate>

  <ItemsControl.ItemContainerStyle>
    <Style TargetType="{x:Type ContentPresenter}">
      <Setter 
        Property="Canvas.Left" 
        Value="{Binding Path=LocationX, Mode=TwoWay}" 
        />
      <Setter 
        Property="Canvas.Top" 
        Value="{Binding Path=LocationY, Mode=TwoWay}" 
        />
    </Style>
  </ItemsControl.ItemContainerStyle>
</ItemsControl>

The nodes are positioned based on their LocationX and LocationY properties. Those properties are bound to by the ItemsContainerStyle. Those bindings link a node’s LocationX property to the Canvas.Left attached property on the ContentPresenter that displays the node, and likewise for the LocationY and Canvas.Top properties.

Notice that the ItemTemplate seen above contains a Border element whose Style property references a Style whose key is ‘NodeBorderStyle’. That Style contains a DataTrigger which highlights a node if it is in a circular dependency, as seen below:

<!-- In GraphView.xaml -->
<Style x:Key="NodeBorderStyle" TargetType="{x:Type Border}">
  <Setter Property="Background" Value="LightGreen" />
  <Setter Property="BorderBrush" Value="Gray" />
  <Setter Property="BorderThickness" Value="3" />
  <Setter Property="BorderBrush" Value="Gray" />
  <Setter Property="Height" Value="{Binding Path=NodeHeight}" />
  <Setter Property="Padding" Value="4" />
  <Setter Property="TextElement.FontWeight" Value="Normal" />
  <Setter Property="Width" Value="{Binding Path=NodeWidth}" />
  <Style.Triggers>
    <DataTrigger 
      Binding="{Binding Path=HasCircularDependency}" 
      Value="True"
      >
      <Setter Property="Background" Value="Red" />
      <Setter Property="BorderBrush" Value="Black" />
      <Setter Property="TextElement.FontWeight" Value="Bold" />
    </DataTrigger>
  </Style.Triggers>
</Style>

The node connectors are highlighted in a similar manner. Speaking of node connectors...

Rendering node connectors

A dependency between two nodes is depicted by drawing an arrow that points from the node that has a dependency to the node on which it depends. I made use of Charles Petzold’s excellent ArrowLine element to render an arrow. In my application, I subclassed ArrowLine to create NodeConnector. NodeConnector takes care of moving itself when its associated nodes are moved by the user. It also exposes the IsPartOfCircularDependency property used by a Style’s trigger in order to highlight the connector if it points to two nodes in the same circular dependency.

Here is the code from NodeConnector that initializes an instance and ensures that the connector is always pointing to its nodes:

// In NodeConnector.cs
public NodeConnector(Node startNode, Node endNode)
{
    _startNode = startNode;
    _endNode = endNode;

    this.SetIsPartOfCircularDependency();
    this.SetToolTip();
    this.UpdateLocations(false);

    _startObserver = new PropertyObserver<Node>(_startNode)
        .RegisterHandler(n => n.LocationX, n => this.UpdateLocations(true))
        .RegisterHandler(n => n.LocationY, n => this.UpdateLocations(true));

    _endObserver = new PropertyObserver<Node>(_endNode)
        .RegisterHandler(n => n.LocationX, n => this.UpdateLocations(true))
        .RegisterHandler(n => n.LocationY, n => this.UpdateLocations(true));
}

void UpdateLocations(bool animate)
{
    var start = ComputeLocation(_startNode, _endNode);
    var end = ComputeLocation(_endNode, _startNode);

    if (animate)
    {
        base.BeginAnimation(ArrowLine.X1Property, CreateAnimation(base.X1, start.X));
        base.BeginAnimation(ArrowLine.Y1Property, CreateAnimation(base.Y1, start.Y)); 
        base.BeginAnimation(ArrowLine.X2Property, CreateAnimation(base.X2, end.X)); 
        base.BeginAnimation(ArrowLine.Y2Property, CreateAnimation(base.Y2, end.Y));
    }
    else
    {
        base.X1 = start.X;
        base.Y1 = start.Y;
        base.X2 = end.X;
        base.Y2 = end.Y;
    }
}

static AnimationTimeline CreateAnimation(double from, double to)
{
    return new EasingDoubleAnimation
    {
        Duration = _Duration,
        Equation = EasingEquation.ElasticEaseOut,
        From = from,
        To = to
    };
}

The constructor creates two PropertyObservers, which is a class in my MVVM Foundation library. When the observers detect that either node’s LocationX or LocationY properties have changed, the UpdateLocations method is invoked. UpdateLocations is also invoked from the constructor, but the animate argument is false. This ensures that when a connector first appears, it immediately shows up at the proper location. When nodes move, however, the animate argument is true, causing the connector to gently bounce to its new position on the screen. The bounce effect is created by using an EasingDoubleAnimation, from my Thriple library, with its Equation property set to ElasticEaseOut.

The node connectors are rendered in the adorner layer. I created a custom adorner that renders all of a graph’s node connectors, called NodeConnectionAdorner. When that adorner’s Graph property is set, the adorner adds a node connector for each node dependency, as seen below:

// In NodeConnectionAdorner.cs
public Graph Graph
{
    get { return _graph; }
    set
    {
        if (value == _graph)
            return;

        _graph = value;

        if (_graph != null)
            this.ProcessGraph();
    }
}

void ProcessGraph()
{
    foreach (Node node in _graph.Nodes)
        foreach (Node dependency in node.NodeDependencies)
            this.AddConnector(node, dependency);
}

void AddConnector(Node startNode, Node endNode)
{
    var connector = new NodeConnector(startNode, endNode);

    _nodeConnectors.Add(connector);

    // Add the connector to the visual and logical tree so that
    // rendering and resource inheritance will work properly.
    base.AddVisualChild(connector);
    base.AddLogicalChild(connector);
}

An instance of NodeConnectionAdorner is applied to the ItemsControl that contains a graph’s nodes. This occurs in the NodeConnectionAdornerDecorator class, which is the parent element of the ItemsControl.

<!-- In GraphView.xaml -->
<local:NodeConnectionAdornerDecorator 
  Graph="{Binding Path=.}"
  >
  <ItemsControl ItemsSource="{Binding Path=Nodes}">
    <!-- We saw this ItemsControl previously... -->
  </ItemsControl>
</local:NodeConnectionAdornerDecorator>

As seen above, the decorator has a Graph dependency property which is bound to the inherited DataContext; which just so happens to be a Graph object. When the decorator element is loaded into the UI, it puts a NodeConnectionAdorner into the adorner layer and hands off the Graph to the adorner so that it can create node connectors. That code is shown below:

// In NodeConnectionAdornerDecorator.cs
void OnLoaded(object sender, RoutedEventArgs e)
{
    var layer = AdornerLayer.GetAdornerLayer(this);
    if (layer == null)
        return;

    _adorner = new NodeConnectionAdorner(this);
    layer.Add(_adorner);
    this.GiveGraphToAdorner();
}

void GiveGraphToAdorner()
{
    if (_adorner != null && this.Graph != null)
    {
        _adorner.Graph = this.Graph;
    }
}

There is a lot more going on in this app than what we’ve reviewed here, so if you are interested, be sure to download the source code from the top of this article and dig in!

External references

• Charles Petzold’s blog – where ArrowLine came from.
• MVVM Foundation – where PropertyObserver and ObservableObject came from.
• WPF.JoshSmith – where DragCanvas came from.
• Thriple – where EasingDoubleAnimation and ContentControl3D came from.

Revision history

• November 17, 2009 - Updated the article and source code to use a new and improved algorithm for detecting all circular dependencies in a graph. Also, the node connectors now bounce into place, instead of sluggishly sliding like they originally did.
• November 15, 2009 - Created article.