• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 210
  • Last Modified:

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



0
Dimkov
Asked:
Dimkov
1 Solution
 
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
 
ozoCommented:
It is not known whether an efficient algorithm exists
http://en.wikipedia.org/wiki/Graph_isomorphism
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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
 
Vee_ModCommented:
Closed, 500 points refunded.
Vee_Mod
Community Support Moderator
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now