GraphGrep1.0, 1.1

Rosalba Giugno
Universita' di Catania
Dipartimento di Matematica e Informatica
giugno@dmi.unict.it

Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu

Date 1/1/2002.

 Installation    Usage    Glide    References

Demo

Installation

GraphGrep1.0 is implemented in ANSI C and in a high performance interpreted language called K. It has been ported on Unix, and  Windows  (Cygwin) platforms.
Follow these instructions to install and test GraphGrep1.0.

• Download  K from kx.com .      The license is good for a limited duration, but is renewable.
• Install K                                                     (follow the instructions from kx.com). 
• Download GraphGrep1.0
• gunzip -c graphgrep1.0.tar.gz  | tar xf -             (will create a directory called GraphGrep1.0).
• make                                                          (will build the executables, graphbuild and graphgrep).

GraphGrep1.1 is implemented only in ANSI C. It has been ported on Unix, and  Windows  (Cygwin) platforms.
Follow these instructions to install and test GraphGrep1.0.

• Download GraphGrep1.1
• gunzip -c graphgrep1.1.tar.gz  | tar xf -             (will create a directory called GraphGrep1.1).
• make                                                          (will build the executables, graphbuild and graphgrep).

To run the examples go to the GraphGrep1.0 or GraphGrep1.1 directory and do the following:

1. Run "graphbuild ex1/dbsmile.dat". This will  create a directory called graphgrepdata under your working directory with the abstract representation of the graphs.

2. Search for subgraphs:

• run "graphgrep -m ex1/mquery.dat"; 

• inspect output in ex1/mquery.dat.out;
  

•  run "graphgrep -x ex1/xquery2.dat ";

•  inspect output in ex1/xquery2.dat.out. 
  

• run "graphgrep -x ex1/xquery.dat"; 

• inspect output in ex1/xquery.dat..output.


Note: mquery.dat is represented as a list of node labels and edges; xquery2.dat and xquery.dat are expressed in Glide language. Use the command line option -x  if the query is in Glide language, otherwise use -m. The wildcards can be used only in the Glide language. 


3. Replace an existing graph 

• find the GraphGrep identification number (id) associated with the graph that you want replace in the file "graphgrepdata/indexgraph.dat" (id is the integer in the first column);

• run "graphgrep -f  1"; 

• edit the file graph1.dat, inserting or deleting nodes and edges;

•  run "graphgrep -r 1". 

For bugs and questions about GraphGrep please contact giugno@dmi.unict.it and shasha@cs.nyu.edu

Home

Usage

  To use GraphGrep1.0, 1.1 you have to: (1) create a dataset file; (2) preprocess the collection of graphs; and (3) run a query. The output of "graphgrep" contains all the occurrences of the query in the collection of graphs.

• File formats
  
  • dataset file 
    The file consists of a collection of graph specifications.  The first line of each graph must begin with the character '#' and contains the label of the graph; it can be a number or a string. The next line contains the number of nodes in the graph. Subsequent  lines contain the nodes'  labels, one label per line. The first label is the label of node 0, the next one is the label of node 1, etc. Next is the number of edges  in the graph, followed by a list of edges consisting of node id pairs. Each line contains only one edge. GraphGrep assumes that all edges are symmetric and no double edges are given. An example of dataset file is given in here.
  
  
  • query file  (two alternatives)
    1. The first one has the same format of the dataset file; only one graph per file is allowed (see an example here) ,
    2. The second is the Glide format: one query per file  (see an example here).
       
  • output file
    If the query does not contain wildcards the output is given in a file called "query_file_name.out". For example, if the query file name is query.dat the output is given in query.dat.out. If the query contains wildcards the output is given in a file called "query_file_name.output". 
    Each row of the output file is a subgraph matching the query. The rows contain an identification of the graph  and a list of nodes. Two consecutive nodes are connected by an edge. A list with the gap positions (where two consecutive nodes are not connected by an edge) are given at the end of the file (see example here ). 
    
• Database creation
  In order to build a GraphGrep database, run "graphbuild dataset_file_name". This is a preprocessing step that creates an abstract representation of the data. 
  Note: GraphGrep internal files are stored in a directory called graphgrepdata under your working directory.
  
• Query Execution

  • searching for substructures on the database
    The command is "graphgrep [-m, -x ] query_file_name" 

    • Use -m if the format of the query  is the list of labels and edges (see above, query format 1).
    • Use -x if the query is expressed in Glide  language (see above, query  format 2).
      

  • replace a graph
    To replace a graph (you can delete or insert edges and nodes in existing graphs) use "graphgrep -r  id ".  id is an integer  identification given by GraphGrep for that graph. The list of the id numbers and  the associated graph labels are given in graphgrepdata/indexgraph.dat (on a Unix machine you may use "grep graph_label graphgrepdata/indexgraph.dat" to get the graph id)
    

   

Home

Glide

Glide (Graph LInear DEscription)  is a language designed to express graphs. Glide represents  a graph with a linear notation. The main idea  is to represent a graph as a set of branches where each node is presented only once.  The expressions in Glide, called regular graph expressions, allow the description of portions of graphs.  There are powerful  languages that work only with specific applications. Glide is designed to be as general as possible without compromising efficiency. 

Let us formulate the Glide regular graph expressions  using examples. First consider the graph in Fig. 1.

1. A node is represented by  its label followed by the special character '/'  
   

	a/
	b/

2. An edge is represented by two consecutive node representations; a path of length n  is represented by n+1 consecutive node representations.

	a/b/
	h/c/
	a/h/c/f/

3. Branches are  grouped using nested parentheses  '('  and ' )'.

	a/(h/c/)b/
	i/(b/a/(l/)h/c/)d/

4. Cycles are broken by cutting an edge and labeling it with an integer. 

    

   1. The labels of the nodes  of the cut edge are followed by  '%', an integer  and '/'.

   c%1/ f/  i%1/

   2. The labels of the nodes of  the cut edge are followed by a list of '%'and integers. In this case the same node is a vertex of several cut edges.

   a%1/h/c%1%2/d/h/i%2/

Note: by node label we mean the value  used  in a matching algorithm to establish the equivalency between two nodes.

Glide uses  wildcards for approximate searches. The wildcards are used to match  single nodes or paths. Wildcards must be always followed by '/' . 
The wildcards used by Glide  and their semantics are given below.

Wildcard	Semantic (matching with)	Example
.	any (single) node	a/./c/
*	zero or more nodes	a/*/c/
?	zero or one node	a/?/c/
+	one or more nodes	a/+/c/

Glide manipulates any combination of wildcards. A recursive semantics is provided (see examples).

Glide expression	Semantic
a/./././b/	any path of length 4 beginning with a node 'a 'and ending with a node 'b'
a/+/./b/	any path of length at least 3 beginning with a node 'a' and ending with a node 'b'
a/?/./	any path of length at least 2 and at most 3 starting with a node 'a'
././a/	any path of length 2 beginning with a node 'a '
a%1/(*/b/)./c/d%1/	any path where 'a' and 'c' are connected through a node, and a path between a and b exists.

The graph expressions (E's) in Glide are generated by the following grammar, where digit is a positive integer and label is a string.

E  <--  'label/'  | 'label{%digit}/'  | './'  |  '*/'  |  '?/' | '+/' 

E  <--  EE | '('E')'  

Graph	Incorrect graph expression	Correct graph expression
	a/((b/i/c%1)/h/c%1/)	a/(b/i/c%1/)h/c%1/

Some details on Glide.

Home

References

R. Giugno, D. Shasha, GraphGrep: A Fast and Universal Method for Querying Graphs.
Proceeding of the International Conference in Pattern recognition (ICPR), Quebec, Canada, August 2002. pdf
 

D. Shasha, J.T-L Wang, R. Giugno, Algorithmics and Applications of Tree and Graph Searching
Proceeding of the ACM Symposium on Principles of Database Systems (PODS), Madison, Wisconsin, June 2002. pdf