next up previous contents
Next: Graph Methods Up: Graph Previous: Subgraphs

Input Graph Language

 It is possible to store and retrieve LINK graphs from disk along with certain associated attributes using the Graph::saveToFile(...) method and the parseGraph(...) function. Although the input graph language allows for the saving of attributes, it reduces to the format produced by the Graph::display(...) method if no attributes need to be saved. The system currently supports the saving and loading of int, float, double, and String (char*) attributes. Future modifications to the parser may allow the storage of general type information, allowing the programmer to add support a specific complex or pointer typed attributes. In the meantime, programmers who want to group all attribute information into a single class attribute to save calls to setAttribute(...) and getAttribute(...) are encouraged to write transformation routines which extract individual attribute fields and make them independent primitive attributes prior to storage on disk (and vice versa). Stored graphs are loaded into LINK using a parser which uses the grammar listed in Appendix A. Several examples of graph input files are also included in Appendix A.3. As stated previously, attributes of GraphObjects can be stored in the graph input file. The parser will recognize and build attributes of the following types, which conform to the C language standard with stated exceptions: The graph input file format itself begins with an optional preamble which identifies the graph type and declares all attributes which should be associated with the graph and its Vertex and Edge objects. If the preamble is missing, the graph type is assumed to be the most specific type matching the edge set. For example, DBinGraph (directed binary graph) is more specific than DHyperGraph (directed hypergraph) or BinGraph (binary graph where each edge may be either directed or undirected). A DBinGraph is a DHyperGraph and a BinGraph at the same time. See Section [*] for a discussion. The parenthesized attribute declarations list consists of 0 or more attribute declarations of the following format (the names used here are not the actual names of nonterminals in the input language grammar):
<attr_name> ( <attr_value> )
The <attr_name> is a C language identifier (not a string constant). The <attr_value> may be any of the constants listed above (int, float, double, string constant), unless the given <attr_name> is one of the reserved words listed below, in which case the type must conform to the following table:
 
Figure 2.6: Undirected Binary Multigraph
reserved attribute name required type of constant
graph_name <string constant>
name <string constant>
location (<numeric constant>,<numeric constant>)
vcolor <int constant>
ecolor <int constant>
direction <int constant>
weight <int constant>
open <int constant>

These attributes are reserved since they are fairly standard and are assumed to be the stated type by the underlying system. New reserved attributes may be added by adding reserved words to /src/interface/scanner.l. The parser need not be changed unless the new reserved attribute must be of a type which is not currently supported. If the <attr_name> is not reserved, then the type of the <attr_value> determines the type of Attribute object which will be created and associated with the graph. After the preamble, there is a square-bracket enclosed list of vertex names with optional associated attributes. Each vertex specification consists of an identifier, integer constant, or string constant naming the vertex and a square bracket enclosed list of attributes of the same format as that discussed above. The only difference is that it is not permitted to declare new attributes outside of the preamble. Any unrecognized attribute name outside of the preamble will be flagged as an undeclared attribute and the parse will be aborted. The final section of the graph input file identifies the Edges. Undirected edges are specified with curly-brace enclosed lists of identifiers, integer constants, or string constants identifying vertices. There is no delimiter other than white space separating the vertex names in this list. If any edge contains a vertex name which did not appear in the Vertices section, that vertex is reported to be undeclared and the parse fails. Support for further attribute types can be obtained by studying and specializing the AttributeElementOps<T> class in Attribute.h (for correct output) and the graph language grammar listed in Appendix A, which is automatically generated from parser.y in the /src/interface directory. In order to allow arbitrary structure or pointer types to be stored and reloaded successfully, the graph input language would have to be augmented with more type recognizing power. Recall from Section [*] that a Subgraph is actually maintained as an Attribute of a special vertex. The parser is designed so that it is possible to save and reload graphs with layers of subgraphs. However, this mechanism is not complete and bugs remain. An example of the process of saving a LINK graph is depicted in Figure [*].
  
Figure 2.7: Saving a LINK Graph
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

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

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

Now give an example with different types

  
Figure 2.8: Loading a LINK Graph from Disk
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

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

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


  
Figure 2.9: Copying a Graph without its Attributes


next up previous contents
Next: Graph Methods Up: Graph Previous: Subgraphs
RHS Linux User
1/26/1998