Hi, Petr, > > Hi Khris: > > If i understand the problem correctly, you have a list of (x,y) coordinates, > where > some sensor is located, but you do not know, which sensor is there. The > database > contains data for each sensor identified in some way, but you do not know the > mapping between sensor identifiers from the database and the (x,y) > coordinates. > Is this correct?
Yes. > > > So I modelled the problem as inexact match between 2 Graphs. Since the best > > package on Graphs i.e. iGraph does not have any function for Graph matching > > I think, the problem is close to > > http://en.wikipedia.org/wiki/Graph_isomorphism > > You have estimates of the distances between the sensors using identifiers > from the database. So, you know, which pairs of sensors are close. This is > one graph. The other graph is the graph of closeness between the known (x,y) > coordinates. You want to find a mapping between the vertices of these two > graphs, which preserves edges. Yes, I agree the problem is more into Graph theoretic domain to be more precise inexact graph matching whose generalization is the Graph Isomorphism problem. The problem is more general than Graph Isomorphism. Let me define the problem more formally. We have 2 weighted undirected graphs. In one graph I know the distance of every vertex from every other vertex whereas in another graph I know only which vertices are close to a given vertex. So I know the neighboring vertices given a vertex. So the distance matrix of other Graph is incompletely known. So the question is can I find the best alignment between the 2 graphs. Ex:- G1 is know the complete distance matrix. For G2, if there are four vertices let's say (v1, v2, v3 v4) the I know edge weight (v1,v2) and (v1,v3) but have no information of edge weight(v1,v4). Similarly I know about (v2,v3) but no information about edge weights (v2,v4) or (v3,v4). So I was thinking of not to model it as general inexact Graph matching problem for then the complexity n^4. It seems the best way to model the solution is to consider only edges with are at distance of 1 unit i.e. closest edge from every vertex and not every edge from the given vertex. This will bring down the complexity from n^4 to 6*6*n^2 assuming every vertex has atmost 6 neighboring vertex. Quadratic complexity seems manageable. Ofcourse now the solution become lot more sensitive to the errors in Graph G2. Assuming best case if I have no errors in G2 i.e. for every vertex I know correctly it's closest neighbored in the rectangular grid then optimizing distance between G1 and G2 should give me best correct alignment. This seems to be the best approach under current circumstance. As far as implementation goes I think I still have to use optimization package since there are not any readily and freely available function for inexact graph matching. Petr how do you feel about it. Appreciate your feedback. Regards Khris. > > > I converted the Inexact graph matching problem to Binary Quadratic Opt > > Problem. Since there is no specialized package for Binary Quadratic Opt, > > based on your input I converted it into Binary Linear Opt problem. > > The problem of graph isomorphism is hard in general, but if one of the > graphs is a rectangular grid, which does not have too many automorphisms, > the problem is not too hard. Try, for example, the following approach. > > Look for small groups of the sensors, which form connected subgraphs, which > have the form of small pieces of the rectangular grid. If you have such > a small subgraph, look for nodes, which can be add to the subgraph to make > it a larger piece of the grid. > > To start, the algorithm can choose any sensor, say S_0. Find all its > neighbours. > There should be at most 4 neighbours (in an ideal grid). Call the group of > these neighbours S_1. Then, find sensors, which are neighbours to at least > two members of S_1. Call them group S_2. The connections between S_0, S_1 > and S_2 should form a pattern like > > 2 - 1 - 2 > | | | > 1 - 0 - 1 > | | | > 2 - 1 - 2 > > The digits 0, 1, 2 distinguish elements of S_0, S_1, S_2. Continue this in > order to enlarge this recognised pattern. > > If the grid is not ideal, the process may require to maintain several > candidate connected patterns and choose those, which can be extended > with further sensors and discard those, which cannot. > > Another approach is as follows. Choose a random mapping between the > sensors and (x,y). Define a measure of the quality of the mapping. > For example, the number of matching edges minus the number of non-matching > edges. Then, use local search to maximize the quality. For example, in each > step, exchange two sensors in a way, which increases the quality. > > Do you think that some of these approaches is applicable to your situation? > > Petr. > > ______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. > > > If you reply to this email, your message will be added to the discussion > below: > http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634822.html > To unsubscribe from Binary Quadratic Opt?, click here. > NAML -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4635123.html Sent from the R help mailing list archive at Nabble.com. [[alternative HTML version deleted]] ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
