Data Accessors

Data accessors are a novel technique [48], which allows one to implement an algorithm for attributed graphs such that the implementation does not depend on a specific organization of the attributes. Roughly speaking, an attributed graph consists of a (directed or undirected) graph and an arbitrary number of node and edge attributes. For example, the nodes of a graph are often assigned attributes such as names, flags, and coordinates, and likewise, the edges are assigned attributes such as lengths, costs, and capacities. More formally, an attribute a of a set S has a certain type T and assigns a value of T to every element of S (in other words, a may be viewed as a function a:S-> T). An attributed set A=(S,a_1,...,a_m) consists of a set S and attributes a_1,...,a_m. An attributed graph is a (directed or undirected) graph G=(V,E) such that the node set V and the edge set E are attributed. Basically, LEDA provides two features to define attributes for graphs:

• Classes GRAPH and UGRAPH (sects. Parameterized Graphs and  Parameterized Ugraphs) are templates with two arguments, vtype and etype, which are reserved for a node and an edge attribute, respectively. To attach several attributes to nodes and edges, vtype and etype must be instantiated by structs whose members are the attributes.
• A node array (sect. Node Arrays) or node map (sect. Node Maps) represents a node attribute, and analogously, edge arrays (sect. Edge Arrays) and edge maps (sect. Edge Maps), represent edge attributes. Several attributes can be attached to nodes and edges by instantiating several arrays or maps.

Data accessors provide a uniform interface to access attributes, and the concrete organization of the attributes is hidden behind this interface. Hence, if an implementation of an algorithm does not access attributes directly, but solely in terms of data accessors, it may be applied to any organization of the attributes (in contrast, the algorithms in sect. Graph Algorithms require an organization of all attributes as node and edge arrays). Every data accessor class DA comes with a function template get:

    T get(DA da, Iter it);

This function returns the value of the attribute managed by the data accessor da for the node or edge marked by the iterator it. Moreover, most data accessor classes also come with a function template set:

    void set(DA da, Iter it, T value);

This function overwrites the value of the attribute managed by the data accessor da for the node or edge marked by the iterator it by value. The data accessor classes that do not provide a function template set realize attributes in such a way that a function set does not make sense or is even impossible. The constant accessor in sect. Constant Accessors is a concrete example: it realizes an attribute that is constant over the whole attributed set and over the whole time of the program. Hence, it does not make sense to provide a function set. Moreover, since the constant accessor class organizes its attribute in a non-materialized fashion, an overwriting function set is even impossible. Example: The following trivial algorithm may serve as an example to demonstrate the usage of data accessors and their interplay with various iterator types. The first, nested loop accesses all edges once. More specifically, the outer loop iterates over all nodes of the graph, and the inner loop iterates over all edges leaving the current node of the outer loop. Hence, for each edge, the value of the attribute managed by the data accessor da is overwritten by t. In the second loop, a linear edge iterator is used to check whether the first loop has set all values correctly.

  template <class T, class DA>
  void set_and_check (graph& G, DA da, T t)
  {
    for (NodeIt nit(G); nit.valid(); ++nit)
      for (OutAdjIt oait(nit); oait.valid(); ++oait)
        set (da, eit, t);
    for (EdgeIt eit(G); eit.valid(); ++eit)
      if (get(da,it) != t) cout << "Error!" << endl;
  }

To demonstrate the application of function set_and_check, we first consider the case that G is an object of the class GRAPH derived from graph (sect. Graphs), that the template argument vtype is instantiated by a struct type attributes, and that the int-member my_attr of attributes shall be processed by set_and_check with value 1. Then DA can be instantiated as a node_member_da:

    node_member_da<attributes,int> da (&attributes::my_attr);
    set_and_check (G, da, 1);

Now we consider the case that the attribute to be processed is stored in an edge_array<int> named my_attr_array:

    node_array_da<int> da (my_attr_array);
    set_and_check (G, da, 1);

Hence, all differences between these two cases are factored out into a single declaration statement.