Binding Data to Graph Elements

Important

This section can be easily skipped when using the IGraph-based graph structure implementation of yFiles for Silverlight Viewer. See also the section called “Using yFiles Layout Functionality” and Chapter 8, Using yFiles for Silverlight Algorithms Functionality.

The concept of data accessors comprises two aspects which are commonly used in different scenarios. To bind supplemental data to graph elements that should be read-only, an implementation of interface IDataProvider suffices. We will call these implementations "data providers" subsequently. A data accessor with full read/write behavior, though, additionally implements interface IDataAcceptor. The yFiles library knows these implementations as "maps," and has two dedicated interfaces already defined, INodeMap and IEdgeMap. Both extend interface IDataMap which is a combination of interfaces IDataProvider and IDataAcceptor.

Applying the two semantics it is, e.g., possible to restrict certain callees to "immutable" data, while others are allowed to make changes.

Note

Observe that both interface INodeMap and IEdgeMap show identical signatures on their respective methods, using object instead of either yWorks.yFiles.Algorithms.Node or yWorks.yFiles.Algorithms.Edge as the parameter type for their key. Actual implementations should nevertheless ensure that the keys provided have correct type.

Figure 12.7, “The concept of data accessors” gives a brief overview of the classes involved in the basic concepts of maps and data providers.

Figure 12.7. The concept of data accessors

The concept of data accessors.

Maps and Data Providers

Common to all data accessor implementations which are offered by the yFiles library is that they cover all elements of a set, i.e., a node map provides values for all nodes from a graph (however, these may all be default values when there hasn't been anything stored yet). Example 12.13, “Storing and retrieving data associated with a node” shows how node maps are used to store and retrieve arbitrary data.

Example 12.13. Storing and retrieving data associated with a node

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.
// 'labelNodeMap' is of type yWorks.yFiles.Algorithms.INodeMap.
// 'counterNodeMap' is of type yWorks.yFiles.Algorithms.INodeMap.

// Bind a label to the first node of the node set.
// The bound data actually is of type string.
labelNodeMap.Set(graph.FirstNode, "I am the first node!");

// Increase the value stored in 'counterNodeMap' for the last node.
// The bound data is an int.
counterNodeMap.SetInt(graph.LastNode, 
                      counterNodeMap.GetInt(graph.LastNode) + 1);

// Print out the label of the first node.
Console.Write("The name of the first node is: ");
Console.WriteLine(labelNodeMap.Get(graph.FirstNode));

Table 12.2, “Comparing map implementations” lists the differences of some data accessor implementations.

Table 12.2. Comparing map implementations

  Domain Memory Performance Note
Default maps Multi-purpose o + Need cleanup.
Index-based maps Single-purpose ++ ++ Require the underlying container to remain unaltered.
HashMap backed maps Multi-purpose + o Work well for sparse data.

Default Map Implementations

Although writing customized implementations for interfaces INodeMap or IEdgeMap is easy, the most frequently used way to get these is conveniently provided by class Graph. Example 12.14, “Creating default node maps” shows one of the two methods that both return default implementations of these interfaces which can be used for most purposes and data types.

The maps returned by these methods hold exactly one value for a given key, i.e., no matter how many calls to any of the setter methods are issued for a given key, only the last value set will be held. Also, the type of the key given with a setter method is restricted to the respective type of graph elements, i.e., restricted to Node or Edge. The type of the value though, is not restricted to be same over the range of all nodes, for example. In fact, it would be perfectly legal to set a double value with one node, and boolean values with every other. This, however, is strongly discouraged, since it definitely leads to problems when the values will be retrieved.

Default map implementations can be created at any time, even when the graph is empty. From the moment of creation on, they will cover all graph elements from the respective set, as well as all respective elements created by the graph thereafter. However, these maps cannot cover elements that are hidden at the time of creation.

Note that these default implementations have to be properly disposed of after usage to release the allocated resources. To this end, class Graph has appropriate methods for either kind of default implementations.

Example 12.14. Creating default node maps

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Obtain a new INodeMap default implementation from the graph.
INodeMap nodeMap = graph.CreateNodeMap();

// Set values for some of the nodes.
nodeMap.SetDouble(graph.FirstNode, 3.14);
nodeMap.SetDouble(graph.LastNode, 42.0);

// Print the values stored in the node map.
foreach (Node n in graph.Nodes) {
  Console.WriteLine("Node " + n + ": " + nodeMap.GetDouble(n));
}

// Finally release the resources previously allocated by the createNodeMap() 
// method.
graph.DisposeNodeMap(nodeMap);

Creating Customized Data Accessors

In addition to using the default map implementations provided by class Graph, there are further ways to create either maps or data providers. For example, data providers can be implemented so that the actual data is only implicitly defined, i.e., it is calculated on the fly when the value is asked for. This way, it is possible to "store" large amounts of data without having any memory be allocated. Example 12.15, “Using class DataProviderAdapter to create customized data providers” demonstrates how to use class DataProviderAdapter to define a custom IDataProvider implementation.

Example 12.15. Using class DataProviderAdapter to create customized data providers

// Define an IDataProvider implementation that for each node in the graph 
// returns an int that is the square of the node's index.
sealed class MyDataProvider : DataProviderAdapter
{
  public override int GetInt(object dataHolder) {
    if (!(dataHolder is Node)) {
      throw new System.ArgumentException("Key has wrong type.");
    }
    Node node = dataHolder as Node;
    return (node.Index * node.Index);
  }
}

// Define an IDataProvider implementation that for each edge in the graph 
// returns a distance value that is the difference of the values returned by 
// the given IDataProvider for the source and target node.
sealed class MyOtherDataProvider : DataProviderAdapter
{
  private readonly IDataProvider dp;

  public MyOtherDataProvider(IDataProvider squareDp) {
    dp = squareDp;
  }

  public override int GetInt(object dataHolder) {
    if (!(dataHolder is Edge)) {
      throw new System.ArgumentException("Key has wrong type.");
    }
    Edge edge = dataHolder as Edge;
    return (dp.GetInt(edge.Target) - dp.GetInt(edge.Source));
  }
}

public class DataProviderUsage
{
  private Graph graph;

  public void MyMethod() {
    IDataProvider edgeLengthProvider =
      new MyOtherDataProvider(new MyDataProvider());

    // Display the values "stored" (i.e., calculated on the fly) for each edge.
    foreach (Edge e in graph.Edges) {
      Console.WriteLine("Edge " + e + ": " + edgeLengthProvider.GetInt(e));
    }
  }
}

Class DataProviders offers a set of static methods to conveniently create several specialized data provider implementations for either nodes or edges. For instance, there are methods to create data providers from constant values, from given arrays, or from existing data providers.

Class Maps provides a set of static methods to conveniently create several specialized map implementations:

  • The CreateNodeMap and CreateEdgeMap methods that take IMap implementations and return either an INodeMap or an IEdgeMap view of the given instances. This allows for HashMap or TreeMap implementations to be used in conjunction with the yFiles graph implementation.
  • The various CreateIndexNodeMap and CreateIndexEdgeMap methods return map implementations that are fast and at the same time use little memory.

HashMap-Backed Map Implementations

HashMap implementations are true multi-purpose data holders, there is no restriction to the type of the keys nor the type of the values. Particularly, the keys are not restricted to graph elements. Compared to the default implementations of interface INodeMap and IEdgeMap provided by class Graph they are generally a bit slower. However, their memory usage is proportional to the amount of the data that is actually associated with the entities.

Tip

Map implementations backed by an instance of type HashMap are especially suited for sparsely distributed data, i.e., only few entities of a domain have non-null data associated with them.

Index-Based Map Implementations

Index-based map implementations are very fast and use only little memory, their drawback, however, is that once instantiated their values are restricted to the type given at creation time. More important though, all index-based containers require the respective set of graph elements to remain unaltered, i.e., there are no operations allowed that change the sequence of the graph elements in any way.

Example 12.16. Using yFiles convenience classes to create edge maps

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Create an edge map that holds a boolean value for each edge from 
// the edge set of the graph.
IEdgeMap map = Maps.CreateIndexEdgeMap(new bool[graph.E]);

// Store some data into the edge map.
// (For each edge the map will contain the boolean value indicating whether 
// the edge points from a node with a lower index to a node with 
// a higher index.)
foreach (Node n in graph.Nodes) {
  foreach (Edge e in n.Edges) {
    map.SetBool(e, e.Source.Index < e.Target.Index);
  }
}

Notes

Successfully using a data accessor requires a kind of "agreement" on the type the data accessor holds. More precisely, storing the value for a key and retrieving the value thereafter has to be done using setter and getter methods of matching type. The result when using setter/getter methods with non-matching types highly depends on the specific data accessor implementation. Example 12.17, “Successfully using data accessors” demonstrates the proper usage of a data accessor.

This rule furthermore implies that a self-made data accessor has to provide the proper getter (and/or setter) methods when it is used as a parameter to an algorithm.

Example 12.17. Successfully using data accessors

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Get a default INodeMap implementation from the graph.
INodeMap nm = graph.CreateNodeMap();

// Store values for some chosen nodes.
nm.SetBool(graph.FirstNode, true);
nm.SetBool(graph.LastNode, true);

// Retrieve the stored values.
// WRONG. WRONG. WRONG.
// Boolean values cannot be retrieved as ints.
int firstValue = nm.GetInt(graph.FirstNode);
int lastValue = nm.GetInt(graph.LastNode);

// Retrieve the stored values.
// RIGHT.
bool first = nm.GetBool(graph.FirstNode);
bool last = nm.GetBool(graph.LastNode);