Algorithms

Note: A reader pointed out that Union-Find is a very efficient way to accomplish this task. Start there if you have the same problem! Last week, Paul Rubin wrote an excellent post on Extracting a Connected Graph from an existing graph. Lately I’ve been performing related functions on data from OpenStreetMap, though without access to a solver. In my case I’m taking in arbitrary network data and splitting it into disconnected sub-networks. I thought it might be a good case study to show an algorithmic way doing this and some of the performance issues I ran into. ...

In response to this post, Ben Bitdiddle inquires: I understand the concept of using a companion set to remove duplicates from a list while preserving the order of its elements. But what should I do if these elements are composed of smaller pieces? For instance, say I am generating combinations of numbers in which order is unimportant. How do I make a set recognize that [1,2,3] is the same as [3,2,1] in this case? ...

This is based on a lightning talk I gave at the LA PyLadies October Hackathon. I’m actually not going to go into anything much resembling algorithmic complexity here. What I’d like to do is present a common performance anti-pattern that I see from novice programmers about once every year or so. If I can prevent one person from committing this error, this post will have achieved its goal. I’d also like to show how an intuitive understanding of time required by operations in relation to the size of data they operate on can be helpful. ...

I recently stumbled across an implementation of the affine scaling interior point method for solving linear programs that I’d coded up in R once upon a time. I’m posting it here in case anyone else finds it useful. There’s not a whole lot of thought given to efficiency or numerical stability, just a demonstration of the basic algorithm. Still, sometimes that’s exactly what one wants. solve.affine <- function(A, rc, x, tolerance=10^-7, R=0.999) { # Affine scaling method while (T) { X_diag <- diag(x) # Compute (A * X_diag^2 * A^t)-1 using Cholesky factorization. # This is responsible for scaling the original problem matrix. q <- A %*% X_diag**2 %*% t(A) q_inv <- chol2inv(chol(q)) # lambda = q * A * X_diag^2 * c lambda <- q_inv %*% A %*% X_diag^2 %*% rc # c - A^t * lambda is used repeatedly foo <- rc - t(A) %*% lambda # We converge as s goes to zero s <- sqrt(sum((X_diag %*% foo)^2)) # Compute new x x <- (x + R * X_diag^2 %*% foo / s)[,] # If s is within our tolerance, stop. if (abs(s) < tolerance) break } x } This function accepts a matrix A which contains all technological coefficients for an LP, a vector rc containing its reduced costs, and an initial point x interior to the LP’s feasible region. Optional arguments to the function include a tolerance, for detecting when the method is within an acceptable distance from the optimal point, and a value for R, which must be strictly between 0 and 1 and controls scaling. ...