search

KeRNeLith / QuikGraph

Generic Graph Data Structures and Algorithms for .NET
https://kernelith.github.io/QuikGraph/
Microsoft Public License
453 stars 65 forks source link

Graph isomorphism check #44

Open maruker opened 2 years ago

maruker commented 2 years ago

I am looking for a graph library in C# that can perform isomorphism checks but can't find anything.

I also couldn't find an implementation in QuikGraph. Did I miss something or is there no isomorphism algorithm?

KeRNeLith commented 2 years ago

Hello @maruker,

Unfortunately there is no isomorphism algorithm currently implemented in QuikGraph.

It can certainly be a nice improvement if such one is proposed by the library in the future.

Kemsekov commented 1 year ago

You can copy implementation of networkx tree isomorphism vf2 isomorphism

and see how other people implemented is_isomorphic in general here

Of course graph isomorphism is NP problem so there is no known polynomial time algorithm for this problem, but there is a lot of approximations and case-specific solutions.

Most of them can be found implemented in networkx python library.