CEMR

CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination

Compile

Under the root directory of the project, execute the following commands to compile the source code.

mkdir build
cd build
cmake ..
make -j

Run

Options:
-h,   the help message
-d,   the filename of the data graph
-q,   the filename of the query graph
-n,   specify the number of matches to find

Examples:
./MatchOneQuery -d ../test/test_data/data_graph/hprd.graph -q ../test/test_data/query_graph/query_dense_4_1.graph -n 100000

Input File Format

Data graph file format is a text format to store an undirected graph.

• The first line of the file should be "t #vertices #edges #labels"
• Following lines of "v vertex-ID vertex-label vertex-degree" indicate the vertices in the graph.
• The vertices should be written in the file in ascending order of their IDs, and a vertex ID should be in [0, #vertices - 1].
• Following lines of "e vertex-ID1 vertex-ID2" after the vertices indicate the undirected edges in the graph.

For example:

Line "t 3112 12519 71" means the start of a data graph with #vertices=3112, #edges=12519 and #labels=71.
Line "v 0 0 2" means there is a vertex with ID=0 and label=1 in the graph, and its degree=2.
Line "e 0 1745" means there is an undirected edge between vertices with IDs 0 and 1745.

Query graph file format is a text format to store undirected graphs.

• The first line of a graph should be "t #vertices #edges"
• Following lines of "v vertex-ID vertex-label vertex-degree" indicate the query vertices in the graph.
• The query vertices should be written in the file in ascending order of their IDs, and a vertex ID should be in [0, #vertices - 1].
• Following lines of "e vertex-ID1 vertex-ID2 edge-label" after the vertices indicate the undirected edges in the graph.

For example:

Line "t 4 4" means the start of a query graph with #vertices=4 and #edges=4.
Line "v 0 20 3" means there is a query vertex with ID=0, label=20 and degree=3 in the query graph.
Line "e 0 1 0" means there is an undirected edge between query vertices with IDs 0 and 1, where edge label is 0 (The edge label is not used in our project, so we set it to 0 by default).

For Directed and Edge-labeled Graph Format

CEMR also supports directed and edge-labeled graphs. To enable its ability for such graphs, please enable the DIRECTED_EDGE_LABELED macro definition in ./include/Config.h.`