An instance parser of the data type gml_graph is a parser for graph in GML format . It is possible to extend the parser by user defined rules. This parser is used by the readgml of class graph . The following is a small example graph (a triangle) in GML format.
# This is a comment.
graph [ # Lists start with '['.
directed 1 # This is a directed graph (0 for undirected).
# The following is an object of type string.
# It will be ignored unless you specify a rule for graph.text.
text "This is a string object."
node [ id 1 ] # This defines a node with id 1.
node [ id 2 ]
node [ id 3 ]
edge [ # This defines an edge leading from node 1 to node 2.
] # Lists end with ']'.
An input in GML format is a list of GML objects. Each object consists of a key word and a value. A value may have one out of four possible types, an integer (type gmlint ), a double (type gmldouble ), a string (type gmlstring ), or a list of GML objects (type gmllist ). Since a value can be a list of objects, we get a tree structure on the input. We can describe a class C of objects being in the same list and having the same key word by the so-called path. The path is the list of key words leading to an object in the class C .
In principle, every data structure can be expressed in GML format. This parser specializes on graphs. A graph is represented by an object with key word graph and type gmllist . The nodes of the graph are objects with path graph.node and type gmllist . Each node has a unique identifier, which is represented by an object of type gmlint with path graph.node.id . An edge is an object of type gmllist with the path graph.edge . Each edge has a source and a target. These are objects of type gmlint with path graph.edge.source and graph.edge.target , respectively. The integer values of source and target refer to node identifiers. There are some global graph attributes, too. An object of type gmlint with path graph.directed determines whether the graph is undirected (value 0) or directed (every other integer). The type of node parameters and edge parameters in parameterized graph (see manual page GRAPH) can be given by objects of type gmlstring with path graph.nodeType and graph.edgeType , respectively. Parameters of nodes and edges are represented by objects of type gmlstring with path graph.node.parameter and graph.edge.parameter , respectively.
No list has to be in a specific order, e.g., you can freely mix node and edge objects in the graph list. If there are several objects in a class where just one object is required like graph.node.id , only the last such object is taken into account.
Objects in classes with no predefined rules are simply ignored. This means that an application A might add specific objects to a graph description in GML format and this description is still readable for another application B which simply does not care about the objects which are specific for A .
This parser supports reading user defined objects by providing a mechanism for dealing with those objects by means of callback functions. You can specify a rule for, e.g., objects with path graph.node.weight and type gmldouble like in the following code fragment.
bool get_node_weight(const gml_object* gobj, graph* G, node v)
double w = gobj->get_double();
do something with w, the graph and the corresponding node v
return true; or false if the operation failed
parser.append("graph"); parser.append("node"); parser.append("weight");
// or short parser.add_node_rule(get_node_weight,gml_double,"weight");
bool parsing_ok = parser.parse(filename);
You can add rules for the graph, for nodes, and for edges. The difference between them is the type. The type of node rules is as in the example above bool (*gml_node_rule)(const gml_object*, graph*, node), the type for edge rules is bool (*gml_edge_rule)(const gml_object*, graph*, edge), and the type for graph rules is bool (*gml_graph_rule)(const gml_object*, graph*). A GML object is represented by an instance of class gml_object. You can get its value by using double gml_object::get_double(), int gml_object::get_int() or char* gml_object::get_string(). If one of your rules returns false during parsing, then parsing fails and the graph is cleared.
#include < LEDA/graph/gml_graph.h >
|gml_graph||parser(graph& G)||creates an instance parser of type gml_graph and initializes it for graph G.|
|gml_graph||parser(graph& G, const char* filename)|
|creates an instance parser of type gml_graph and reads graph G from the file filename.|
|gml_graph||parser(graph& G, istream& ins)|
|creates an instance parser of type gml_graph and reads graph G from the input stream ins.|
|bool||parser.parse(const char* filename)|
|parses the input taken from the file filename using the current set of rules. The graph specified in the constructor is set up accordingly. This operations returns false and clears the graph, if syntax or parse errors occur. Otherwise true is returned.|
|parses the input taken from the input stream ins.|
|parses the input taken from string s.|
3.2 Path Manipulation
|void||parser.reset_path()||resets the current path to the empty path.|
|void||parser.append(const char* key)|
|appends key to the current path.|
|void||parser.goback()||removes the last key word from the current path. If the current path is empty this operation has no effect.|
3.3 User Defined Rules
|void||parser.add_graph_rule_for_cur_path(gml_graph_rule f, gml_value_type t)|
|adds graph rule f for value type t and for the current path.|
|void||parser.add_node_rule_for_cur_path(gml_node_rule f, gml_value_type t)|
|adds node rule f for value type t and for the current path.|
|void||parser.add_edge_rule_for_cur_path(gml_edge_rule f, gml_value_type t)|
|adds edge rule f for value type t and for the current path.|
|void||parser.add_graph_rule(gml_graph_rule f, gml_value_type t, char* key=0)|
|adds graph rule f for value type t and path graph.key to parser, if key is specified. Otherwise, f is added for the current path.|
|void||parser.add_node_rule(gml_node_rule f, gml_value_type t, char* key=0)|
|adds node rule f for path graph.node.key (or the current path, if no key is specified) and value type t to parser.|
|void||parser.add_edge_rule(gml_edge_rule f, gml_value_type t, char* key=0)|
|adds edge rule f for path graph.edge.key (or the current path, if no key is specified) and value type t to parser.|
|adds graph rule f to parser. During parsing f is called whenever an object o with path graph and type gmllist is encountered. f is called before objects in the list of o are parsed.|
|adds node rule f for path graph.node and value type gmllist to parser. f is called before objects in the corresponding list are parsed.|
|adds edge rule f for path graph.edge and value type gmllist to parser. f is called before objects in the corresponding list are parsed.|
|adds graph rule f to parser. During parsing f is called whenever an object o with path graph and type gmllist is encountered. f is called after all objects in the list of o are parsed.|
|adds node rule f to parser for path graph.node and value type gmllist . f is called after all objects in the corresponding list are parsed.|
|adds edge rule f to parser for path graph.edge and value type gmllist . f is called after all objects in the corresponding list are parsed.|
The data type gml_graph is realized using lists and maps. It inherits from gml_parser which uses gml_object, gml_objecttree, and gml_pattern. gml_pattern uses dictionaries.