GML Parser for Graphs ( gml_graph )

Definition

An instance parser of the data type gml_graph is a parser for graphs in GML format [42]. It is possible to extend the parser by user defined rules. This parser is used by the read$\_$gml of class graph. The following is 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.
source 1
target 2
]
edge [
source 2
target 3
]
edge [
source 3
target 1
]
] # 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 gml$\_$int), a double (type gml$\_$double), a string (type gml$\_$string), or a list of GML objects (type gml$\_$list). 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 gml$\_$list. The nodes of the graph are objects with path graph.node and type gml$\_$list. Each node has a unique identifier, which is represented by an object of type gml$\_$int with path graph.node.id. An edge is an object of type gml$\_$list with the path graph.edge. Each edge has a source and a target. These are objects of type gml$\_$int 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 gml$\_$int 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 graphs (see manual page GRAPH) can be given by objects of type gml$\_$string with path graph.nodeType and graph.edgeType, respectively. Parameters of nodes and edges are represented by objects of type gml$\_$string 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 gml$\_$double 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
}
...
main()
{
char* filename;
...
graph G;
gml_graph parser(G);
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/gml _graph.h >

Creation

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.

Operations

3.1 Parsing

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.
bool	parser.parse(istream& ins)
		parses the input taken from the input stream ins.
bool	parser.parse_string(string s)
		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(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.
void	parser.add_new_graph_rule(gml_graph_rule f)
		adds graph rule f to parser. During parsing f is called whenever an object o with path graph and type gml$\_$list is encountered. f is called before objects in the list of o are parsed.
void	parser.add_new_node_rule(gml_node_rule f)
		adds node rule f for path graph.node and value type gml$\_$list to parser. f is called before objects in the corresponding list are parsed.
void	parser.add_new_edge_rule(gml_edge_rule f)
		adds edge rule f for path graph.edge and value type gml$\_$list to parser. f is called before objects in the corresponding list are parsed.
void	parser.add_graph_done_rule(gml_graph_rule f)
		adds graph rule f to parser. During parsing f is called whenever an object o with path graph and type gml$\_$list is encountered. f is called after all objects in the list of o are parsed.
void	parser.add_node_done_rule(gml_node_rule f)
		adds node rule f to parser for path graph.node and value type gml$\_$list. f is called after all objects in the corresponding list are parsed.
void	parser.add_edge_done_rule(gml_edge_rule f)
		adds edge rule f to parser for path graph.edge and value type gml$\_$list. f is called after all objects in the corresponding list are parsed.

Implementation

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.