On Mon, Jul 02, 2012 at 06:11:37AM -0700, khris wrote: > 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.
Hi. I am on vacations with only occasional access to the internet. One way to solve your problem is to formulate it in a way, in which it can be solved by some existing solver. I do not know, whether this is possible. Look at self-organizing maps (Kohonen maps). They try to map points with unknown mutual relationships to a 2 dimensional grid. However, i am not sure, whether the input to this method is suitable for your problem. Another way is to write your own program. I sent some suggestions in this direction in a previous email. If you want, we can discuss this in more detail next week, when i am back from vacations. All the best, Petr. ______________________________________________ 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.
