Implementation of gSpan algorithm in networkx?

[Nam Le Thanh]

Hello, I'd like to ask if there's any available source of implementation of gSpan (using Python or using Networkx).

The key idea of the method is to represent graph by DFS tree, then DFS code. There are many DFS tree available for a certain graph, but a minimum DFS code (minDFS) is unique, and 2 graphs G1 and G2 is isomorphic iff minDFS(G1) = minDFS(G2).

gSpan is a well-known algorithm, and is still considered a strong algorithm until today, and people compare their performance against it.

NetworkX already has DFS method, but I'm having a hard time realizing the min DFS code and the frequent mining part...

Details can be found in the paper attached, and the links below:

[1] Yan, Xifeng, and Jiawei Han. "gspan: Graph-based substructure pattern mining." In Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on, pp. 721-724. IEEE, 2002.

http://www.cs.ucsb.edu/~xyan/software/gSpan.htm

[Don Mohsenuss]

Same question from my part !
I home that this code can help you temporary ...
https://github.com/rkwitt/gboost/blob/master/src-gspan/gspan.cpp

[Nam Le Thanh]

Thank you, for the C implementation I already got the (prebuilt binary) file from the author. Another C version seems not to return the same result....

All of my works are in Python so I'm prefer Python implementation of this algo to combine the flow...

Best,