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?

Solved

Posted on 2007-07-29

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

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

10 Comments

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?

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

http://en.wikipedia.org/wi

here is a heuristic approximation method

http://ftp.cs.nyu.edu/shasha/papers/agm.html

http://ftp.cs.nyu.edu/shas

http://math.ucsd.edu/~sbus

but 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

Do you want those attributes to influence the matching in some way?

Title | # Comments | Views | Activity |
---|---|---|---|

How to access the value of a hidden field in code behind using c# | 14 | 51 | |

custome paging in C# & oracle using inline queries. | 12 | 29 | |

Dialogbox API leak? | 18 | 36 | |

Is there any Easy way to copy CSV to SQL Server using C# | 3 | 32 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**22** Experts available now in Live!