constrained graph matching

Hi, I am working on skeleton based object matching and have encountered on the fallowing problem in C/C++/C#:

I need to produce a program which matches two graphs.

Input: 2 graphs in any form I want, and any constraints I need

Output: index of how similar the graphs are.

The code must be resistant in missing nodes (ex. couple of nodes are missing from one of the graph).

Since I will be comparing graphs created from proteins, I expect them to be huge and I am hoping to find an algorithm that indexes the graphs for easier matching

I will be thankful for any links, advices, and code  or libraries that I can use



LVL 3
DimkovAsked:
Who is Participating?
 
Vee_ModConnect With a Mentor Commented:
Closed, 500 points refunded.
Vee_Mod
Community Support Moderator
0
 
ripahoratiuCommented:
You need exact matching/no matching or exact matching/somehow matching? Oriented or not?
i.e.
If you have a graph matching as subgraph of the other than what?
If the graph are matching except a link, or except a node and its links then what?
0
 
DimkovAuthor Commented:
somehow matching - and it can be oriented or not

If you have a graph matching as subgraph of the other than what? - it will influence the matching index
If the graph are matching except a link, or except a node and its links then what? - it will influence the matching index

I am at the beginning and it is up to me how to solve the problem.... so if you have any ideas it will be great  
0
Cloud Class® Course: CompTIA Healthcare IT Tech

This course will help prep you to earn the CompTIA Healthcare IT Technician certification showing that you have the knowledge and skills needed to succeed in installing, managing, and troubleshooting IT systems in medical and clinical settings.

 
ozoCommented:
It is not known whether an efficient algorithm exists
http://en.wikipedia.org/wiki/Graph_isomorphism
0
 
ozoCommented:
here is a heuristic approximation method
http://ftp.cs.nyu.edu/shasha/papers/agm.html
0
 
DimkovAuthor Commented:
One of the ideas I have is to crate minimum spanning tree out of the graphs, and then try algorithm for matching threes which should be more simple... but I don't know any of those algorithms... do you know any working algorithms for matching trees?
0
 
ozoCommented:
Tree isomorphism is relatively easy
http://math.ucsd.edu/~sbuss/ResearchWeb/treeisomorphism/paper.pdf
but there may be an exponential number of ways to create a minimum spanning tree
0
 
DimkovAuthor Commented:
"there may be an exponential number of ways to create a minimum spanning tree"
- cant I decide to make the three starting from the top left node (for ex.)  every time?
In this way the starting node will always be the same which will bring only to one way to create a spanning tree.

I will read the papers you posted carefully, and If I have some questions I will post again.
Thanks for the links
0
 
ozoCommented:
Do the nodes of your graph have "top" and "left" attributes?  
Do you want those attributes to influence the matching in some way?
0
 
DimkovAuthor Commented:
I solved the problem by creating cost functions for every link.
Then I created heuretic fitness function to predict the match
and used A* search
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.