next up previous contents
Next: ContainerNode Up: Algorithms Previous: Algorithm Specifications

GraphObject Attributes

  Although there is an Attribute class in the graph directory of LINK's file hierarchy, objects of this class are typically not instantiated by the programmer. The reason for this is that Attribute objects, though owned by a specific Graph object G, are accessible to any GraphObject (Vertex, Edge, or Subgraph) which belongs to G. The programmer's interface to the attribute mechanism consists of the following three templated functions. This is one of the very very instances of the use of non-member functions in LINK programming.
template  
int newAttribute(Graph*, String name, const Item&);
template  
int setAttribute(GraphObject*, String name, const Item&);
template  
int getAttribute(GraphObject*, String name, Item&);
An example illustrating the use of these functions is presented in Figure [*]. The newAttribute(...) function dynamically allocates an Attribute<Item> object and associates it with the passed Graph. The default value of the attribute is stored in this object and accessed with the setAttribute(...) function. The latter may take as its first argument not only a pointer to a Graph object, but also a pointer to any instance of the GraphObject hierarchy. Thus, even though the actual Attribute object is ``owned'' by the graph, any of its vertices and edges may access its default value.
  
Figure 2.2: Graph Attributes
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

\v...
 ...nd{verbatim}
\vspace*{-6mm}

\hrulefill\end{minipage}\end{flushleft}\end{figure}

In order to set differing attribute values for individual vertices and edges of a graph, the setAttribute(...) function is used. The call format is the same as in the other two. Recall that the Attribute object itself is owned by the Graph object. When a call to setAttribute(...) asks for some Vertex or Edge to replace the default value with a new value, a copy of the Attribute object is obtained, associated with the Vertex or Edge, and given the new value. Subsequent calls to getAttribute(...) for the affected Vertex or Edge return the local attribute value rather than the graph's default value. Note that this implies that even if an attribute is intended to apply only to a graph's vertices, it does exist in the graph and can be given values for the graphs edges also. For example, it is unnecessary to employ two separated attributes vertex_weight and edge_weight. One weight attribute is sufficient. The Attribute class imposes only one restriction on a data type A used as an attribute value: that the operator function ostream& operator<<(ostream&, const A&) be defined. Subject to this requirement, any data type may be used as a graph attribute. However, there are restrictions in the types of attributes that can be stored in a file with the graph (See Section [*]). Warning: Since the three attribute functions described above are templated functions, the actual parameters in the a function call must match the formal parameters exactly. Otherwise, a ``type unification failed'' will result (g++). The first argument of each function is an abstract base class pointer, so it may seem natural to pass in addresses of descendent objects. This must be avoided. Note that the calls in Figure [*] use explicit typecasts to match the function template.

 
next up previous contents
Next: ContainerNode Up: Algorithms Previous: Algorithm Specifications
RHS Linux User
1/26/1998