Thanks Petr for the reply. Let me do implementation and see how how goes.
Enjoy your vacation. Rest fine Khris On Jul 4, 2012, at 8:25 PM, Petr Savicky [via R] wrote: > 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. > > ______________________________________________ > [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-tp4633521p4635416.html > To unsubscribe from Binary Quadratic Opt?, click here. > NAML -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4635457.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.
