Skip to content

Latest commit

 

History

History
37 lines (24 loc) · 1.55 KB

README.md

File metadata and controls

37 lines (24 loc) · 1.55 KB
Raw

#Preface

This is a simple implementation of the VF2 algorithm.

The VF2 algorithm is used for (sub)graph isomorphism task.

Actually, this code is written for a homework of the Graph Data Management course in Peking University. Since I don't have gold answers to the queries yet, the correctness of the code is not guaranteed. (I only manually checked a few results produced by this code, and it seems fine up to now)

Therefore, please don't use this code directly in product environment.

#Project Structure

  • doc: contains the VF2 paper
  • data: experiment data
  • src: source code

##data

  • mygraphdb.data: 10000 target graphs
  • Q4.my, ... , Q24.my: 1000 query graphs in each file. The difference between these files lies in that they have different number of edges (from 4 to 24).
  • readme.txt: description of these data

##src

  • wip.VF2.runner: main function
  • wip.VF2.graph: Graph, Node and Edge classes. These classes describe a graph.
  • wip.VF2.core: The VF2 class contains the main logic of VF2 algorithm. The State class is the state described in the paper, and it has some utility function to manipulate the a state. The Pair class is just a simple implementation of a (key, value) pair class.

#Usage The main function can be called by passing command line arguments:

  • -t: The path of the target graph file (mygraphdb.data).
  • -q: The path of the query graph file (e.g Q4.my).
  • -o: The path of the output file.

Also, you can hard write these paths in the source code of App.java. Simply change three variables: graphPath, queryPath, outPath.