A Brief Study of the Independent Set Problem

Prologue

I normally prefer to share posts of a more practical nature, but in celebration of a hard-fought semester fraught with theory, research, and not a whole lot of actual development in the curriculum, I've decided to share some of what I learned even if it isn't directly applicable to the kind of day-to-day development most of us face on the job.

One of my most vicious classes last semester was combinatorial algorithms, a course focusing on algorithm design and analysis with particular attention to time complexity. Needless to say, computers and programming didn't factor into the curriculum at all. This was strictly a math class. Our big assignment for the semester was to pick an existing problem in the math domain, describe it in detail, and analyze a variety of the known approaches to solving it.

I chose the independent set family of problems, and the professor - considered one of the most brutal on campus - wrote me to congratulate me on a flawless paper. So I figured it must not have been too shabby, and I'll pass it on to the masses! Now, let's talk about independent sets!

Introduction: What is an Independent Set?

If you already know about graphs, and what an independent set is, you can skip ahead, but a little bit of background knowledge is needed to understand what an independent set is. Fair warning, it would be quite helpful to know a little bit about graphs, time complexity, and dynamic programming (or at least recursion). But I'll do my best to make this digestible with a minimum of prerequisite knowledge.

The very least you need to know is that a graph is made of vertices and edges, so that the edges connect the vertices together, like connect-the-dots. You can have a graph with any number of vertices, connected to each other in any number of ways by any number of edges. We call the group of vertices together a set of vertices, and the group of edges is also a set. Any group of items that belongs to a set (but might not include all of the items in that set) is called a subset.

So, if we have a graph, let's call it G, composed of vertex set V and edge set E, an independent set within that graph is a subset of the vertices in G where none of the vertices in the subset are connected by any edge. In other words, an independent set of vertices in a graph is a subset of the graph's vertices with no two vertices adjacent.

Two important types of independent set we will talk about below include the maximal independent set and the maximum independent set (they are sometimes, but not always, different from each other). We will also discuss what a graph’s independence number is. For the most part, we're only concerned with maximum independent sets and independence numbers, but I want to talk about maximal independent sets because that will help us to understand just what a maximum independent set is.

A maximal independent set in G is a type of independent set. In a maximal independent set, if you add any vertex from the total vertex set V, that wasn't already in the subset, that would force an adjacency into the subset. Remember, if we have two adjacent nodes in our graph, it's not independent. So a maximal independent set is a subset of the vertices in G that can't have any more of G's vertices added without stopping the subset from being independent.

There are two things I find worth noting about maximal independent sets. First, a given graph might have any number of maximal independent sets. Second, each maximal independent set might have a different total cardinality (number of vertices in the subset). In other words, a single graph might contain multiple maximal independent sets, each of varying size. The largest possible one of these is called the maximum independent set. This is the largest independent set found in a given G.

Note also that a graph can have multiple maximum independent sets, but in this case, all of the maximum independent sets will have the same cardinality.

Finally, whether there is only one maximum independent set, or there are many, we refer to the cardinality of maximum independent sets as the independence number of the graph to which they belong.

We'll use these terms and concepts more below to discuss a variety of problems relating to independent sets, most importantly to my research, the maximum independent set problem and the independent set decision problem

Details: Problem Formulation and Motivation

As we noted above, the maximum independent set problem takes a graph as input, G = (V, E). The goal is to find a subset of V comprising one maximum independent set on G, which might just be one of several maximum independent sets in G. The solution can then be used to obtain the answer to the independence number problem, which takes the same input (a graph) but seeks, instead of a maximum independent set, the independence number of the graph (the number of vertices in the maximum independent set). All we have to do to get the independence number once we have the maximum independent set is return the cardinality of the maximum independent set, and we're done. Along the same lines, the solution to the maximum independent set problem also comes packaged with the solution to the independent set decision problem, which is looking for a simple Boolean value: true if the graph’s independence number is greater than or equal to some given number, k, and false otherwise.

In other words, we can formally define the independent set decision problem as taking a graph, G = (V, E) and an integer k, and returning a Boolean value, true if k is less than or equal to G’s independence number, or false if k is greater than that independence number. In the simplest terms, we have a number, and we want to know if there is an independent set in some graph that is as big as our number.

Input: a graph G = (V, E), and an integer k

Output: a Boolean true or false value

Believe it or not, these versions of the same problem – maximum independent set, independence number problem, and independent set decision – each has a specific real world application. The maximum independent set and independence number problems in particular have a wide variety of practical uses. The maximum independent set, for instance, is a problem that materializes in visual pattern recognition, molecular biology, and certain scheduling applications; and the independence number problem has applications in molecular stability prediction and network configuration optimization.

Astute readers will notice that I've omitted the very specific subject of the independent set decision problem, which (to refresh our memories) seeks only a Boolean value and no other data. This member of the independent set family of problems is not considered to have any practical "real world" application. That said, it plays a crucial role in the realm of theoretical research. It is considered necessary in order to apply the theory of NP-completeness to problems related to independent sets. That's a topic for a whole other kind of blog post.

Though the topic of NP-Completeness can get pretty hairy, the dominating factor of the time complexity of solving the decision version of this problem is the same as for the independence number problem or the maximum independent set problem. As mentioned above, the decision version of the problem uses the same underlying algorithm as the independence number problem, and simply examines the resulting data to a different end. In short, to get the solution to the decision problem, we reduce the independence number solution to a Boolean value. The independence number problem itself is the same as the maximum independent set problem, with the output reduced to a single value representing the cardinality of a maximum independent set in G. But we're getting a bit beside the point here.

Since the domains of practical applications defer in large part to the maximum independent set and independence number versions of this problem, this is where the vast majority of interesting research on the topic of independent sets has been done. The complexity of the algorithms to solve all three problems is dominated overwhelmingly by the operations performed in the original maximum independent set problem. The transformations we have to make to produce solutions to the other versions of the problem are pretty trivial (counting cardinality, or comparing a given k value to the independence number to determine a Boolean value). For that reason, we'll focus on the research surrounding the maximum independent set problem.

The Brute Force Approach – Slow but Simple

Now let's talk about how we actually solve this problem. The brute force approach to the maximum independent set problem is very simple in principle. In short, all we need to do is iterate over all possible subsets in G, and then for each subset, check all vertices v in V for pair-wise adjacency. The time complexity of checking each possible subset is O(2ⁿ), yielding an exponential time complexity, and the checking of all vertices yields an additional (relatively insignificant) polynomial factor to the complexity, referred to in this case as poly(n), where n is, of course, the number of vertices in G. We consider the polynomial factor insignificant because the complexity of any polynomial factor will never dominate the exponential factor of O(2ⁿ), and so becomes irrelevant for large graphs.

In summary, for each vertex subset S in V, we check all vertices in S for adjacencies. If an adjacency exists, this subset can be thrown out because the adjacency violates the defintion of an independent set. As we iterate over subsets, we simply measure each and track which is the largest. For maximum independent set, we return the independent set that ends up providing the largest number of vertices over all iterations (this being the largest, read maximum independent set). This ends up taking a total of O(2ⁿpoly(n)) time. For the independence number problem, instead of returning the largest independent set, we return only the cardinality of the largest independent set, which we can trivially store while iterating over subsets. Finally, in the case of the independent set decision problem, we simply compare the independence number gained via the above brute force algorithm, trivially compare it against our given k, and return the appropriate Boolean value, yielding a worst case that is still O(2ⁿpoly(n)) time.

Serious Business: Strategy and Analysis of an Improved Algorithm

Before we get too excited, it's only fair to say right up front that we are not going to beat exponential time complexity with any known algorithm for solving this problem. That said, a fair amount of research has been done on it, yielding impressive improvements to the base of exponentiation. This, in turn has led to vastly improved run times in real world applications that rely on solutions to the independent set family of problems. (We're going to start getting very technical here.)

Following Jeff Erickson’s guide to the optimization of the independence number algorithm, we see that there are a series of steps that can be taken in turn to improve the performance of our algorithm. As a first step toward understanding the complicated means of optimization, Erickson provides a recursive formulation of an algorithm for obtaining the independence number on a graph, G (shown below). Next, he shows that the worst case scenario for that recursive algorithm can be split into subcases, some of which are redundant recursive calls that do not need to be performed in duplicity. Eliminating these duplicate cases, obviously, improves run time complexity. Finally, he shows that this improvement can be repeated on the resultant worst case, splitting that into further subcases, some of which are also redundant; and so on and so forth, continually improving the run time complexity in seemingly small, but ultimately meaningful, increments. To begin, observe Erickson’s most elementary version of the algorithm in its recursive form:

MaximumIndSetSize(G):
if G = { empty set }
return 0
else
v = any node in G
withv = 1 + MaximumIndSetSize( G \ N(v) )
withoutv = MaximumIndSetSize( G \ {v} )
return max { withv, withoutv }

To clarify the notation here, N(v) refers to the neighborhood of v, meaning the set that includes v and all of its adjacent neighbors, but no other vertices. The backslash symbol refers to set-wise exclusion or "subtraction." For example:
{ a, b, c } \ { b } yields { a, c }.

As you can see at a glance, the number of recursive calls at each iteration is doubled! This yields the same exponential growth of time complexity we saw in the brute force approach. What’s worse, we see that in the worst case, G \ N(v) = G \ {v}, meaning that v has no neighbors! This means that in both recursive calls at each iteration, our vertex subset is only being reduced by size 1. The result is the recurrence equation T(n) = 2T(n – 1) + poly(n), yielding a time complexity of O(2ⁿpoly(n)). T(x) here represents the time required to solve a problem of size x.

At this stage, though no clear improvement has yet been made, we already have the information we need to make our first improvement to the algorithm. As noted above, in the worst case, G \ N(v) = G \ {v}, meaning that v has no neighbors. However, if v has no neighbors, then it is guaranteed to be included in every maximal independent set, including maximum independent sets, because a node that never has neighbors is always independent! As a result, one of the recursive calls, the one assigning the value withoutv, becomes superfluous, because no maximum independent set can exclude v if it never has neighbors in any subset. At the same time (but on the other hand), if v does have at least one neighbor, then G \ N(v) will have at most (n – 2) vertices. That's quite a brain-full, so let me explain it another way, with concrete examples.

Let's say G has 10 nodes total. So n is 10. Then, if our random node v has at least 1 neighbor, then the neighborhood of v is size 2 or greater. Since N(v) is 2 or greater, then G \ N(v) is 10, minus some number 2 or greater. This line of reasoning yields a new recursive formula with a dramatically improved run time complexity:

T(n) ≤ O(poly(n)) + max{T(n - 1), [T(n - 1) + T(n - 2)]}

The run time complexity on this improved version of the recursive algorithm is reduced to T(n) ≤ O(1.61803398875ⁿ) after just one subcase division! That might not seem like much of an improvement, but in a little bit we're going to see some concrete examples of just how big an improvement this can make at execution time. In the meantime, following this line of logic and making further observations, we can immediately improve on our new worst case by splitting that into subcases – some of which are, again, redundant and superfluous.

Note that our new worst case is the case in which both T(n – 1) and T(n – 2) must be calculated. In other words, this is the case in which our recursive calls are doubled, and in which the graphs we pass along are of relatively large size (only 1 or 2 vertices smaller than the graph from which they were derived). In this specific case, v has exactly 1 neighbor; let's call this neighbor w. Specifically because v has exactly 1 neighbor, we will find that either v or w will appear in every maximal independent subset of our original G. Think about it: if w is in a maximal independent set, v simply can't be, because they're neighbors, and two neighbors can't both be in the same independent set. Conversely, if w is not in a maximal independent set, v will be, because its only neighbor is not in the set, which frees v up to join without fear of standing by an adjacent neighbor. Taking this line of reasoning yet another step further, we see that given a maximal independent set containing w, we can remove w and instead include v. Therefore, we can conclude that some maximal independent set will include vertex v (whether this maximal independent set ends up being maximum or not).

Note also that if we know there is a strict pair-wise relationship between v and w (due to the given fact that v has 1 adjacent neighbor), we never have to evaluate the recursive case in which the call MaximumIndSetSize(G \ {v}) needs to be made. Our case evaluating T(n – 1) + T(n – 2) becomes only T(n – 2). Furthermore, expanding on our idea from the last worst-case scenario subcase split, we will see that if the degree of v is 2 or more, then N(v) will contain at least 3 vertices, and therefore G \ N(v) will have at most (n – 3) vertices. In such a case, the max{...} function of our recursive algorithm is expanded:

T(n) ≤ O(poly(n)) + max{
T(n - 1),
T(n - 2),
T(n - 1) + T(n - 3)
}

This second improvement yields a time complexity of T(n) ≤ O(1.46557123188ⁿ), a smaller but still valuable improvement. On the other hand, note that the complexity of the algorithm is growing rapidly here. Not the time complexity, but the algorithmic complexity, as well as the difficulty we find in determining where to make future optimizations. At each step we take toward a faster algorithm, things are getting much more complicated. At this point, the complexity of the algorithm and the steps required to make further improvements go beyond the scope of what I can talk about in a blog post (even one as ridiculously long and complicated as this). However, Erickson does go on to show that further clever observations can be made continuously, yielding even better time complexities. Two further observations of worst-case splitting and problem structure yield time complexities T(n) ≤ O(1.44224957031ⁿ) and T(n) ≤ O(1.3802775691ⁿ), respectively. According to Erickson, the best published time complexities for this problem are solutions quoted by Fomin, who achieved T(n) ≤ O(1.2210ⁿ, and Bourgeois, who managed to achieve an impressive T(n) ≤ O(1.2125ⁿ).

Considering we're still ultimately stuck with exponential time, it may seem like a lot of work needs to be done for miniscule returns. After all, 1.221 and 1.2125 are almost the same number, right? On the other hand, certain practical applications demand tremendous effort, and therefore any ounce of efficiency that an improved algorithm can provide becomes valuable. Larson includes as an example in his writings a reference to the prediction of molecular stability in the tetrahedral C100 isomer. For this example, the time complexity T(n) of determining the independence number of this molecule is T(100). Therefore, working out the arithmetic, we see the run time for this example reduced as follows (ignoring poly(n):

Algorithm	Time Complexity	≈	Run Time
Brute Force	O(2100)	≈	1.26765e30
Best method described by Erickson	O(1.3802775691100)	≈	9.923e13
Fomin et al	O(1.221100)	≈	4.69425e8
State-of-the-art described by Robson	O(1.1889100)	≈	3.26989e7

With these concrete numbers to reference, we can see clearly that the jump from the brute force method to even a slightly optimized solution is more than worth the effort. The first jump alone results in an improvement to run time of many orders of magnitude! After that, we admittedly begin to see diminishing returns for the effort taken to develop improved algorithms. For instance, I personally doubt that the extra effort by Bourgeois to beat Fomin by a mere 0.0085 on the exponentiation base was of debatable value as anything more than a stepping stone. In my personal opinion, the return on invested effort put in to develop Robson’s final state-of-the-art solution (discussed below) was not worth it for such a small gain from Fomin's algorithm. At least, not in the case of the C100 stability prediction problem. That said, 100 may be considered a small quantity of vertices in some problem domains, such as large network configuration optimization or scheduling problems. In those cases, it may actually be worth it to go to the trouble of researching and developing the absolute best state-of-the-art in terms of fast, efficient algorithms.

Robson's Incredible State of the Art, Conclusions

Research has yielded relatively fast algorithms for solving the independent set family of problems. Some, notably by Bourgeois, are capable of a time complexity as low as a flabbergasting T(n) ≤ O(1.0854ⁿ) time complexity using strategies of case analysis and reduction rules. However, it's worth noting that algorithms that are as fast as these come with severe limitations. For example, the Bourgeois algorithm is limited to graphs with average vertex degree 3. That is a serious limitation! The fastest published algorithm for solving the independent set family of problems for generic graphs (with unbounded number of degrees), by Bourgeois, runs in only T(n) ≤ O(1.2125ⁿ).

The absolute state of the art for solving the independent set family of problems is actually a computer-generated algorithm. The algorithm is described in an unpublished technical report by Robson, and is claimed to boast a time complexity of only O(1.1889ⁿ). However, the trade-off at this level of acceleration is mind-boggling algorithmic complexity. Just the high level description of the algorithm, excluding the rest of the accompanying report, fills fully 15 pages, and thus excludes discussion of the algorithm in any depth from the scope of most academic papers, let along blogs. I'm not an expect on algorithmic analysis at quite that level, but I'd wager such an algorithm would even be excluded from use in applications at that point, due to its sheer complexity.

As algorithms grow in efficiency, but also in complexity, it gets tough to make universal recommendations on which to use – or, in the case of the algorithms described above, how deep through the iterations of optimization a project team should go to try and improve the performance of their algorithm. The context of the project would have to come into factor.

For projects dealing with small graphs, it wouldn't be worth the effort to interpret and implement something like Robson's solution. Something like the example described by Erickson and outlined above would probably be good enough. For projects dealing with graphs of moderate size and predictably small average vertex degrees throughout, but needing accelerated solutions, something like the algorithm developed by Bourgeois would provide a superior middle ground.

Thanks for reading!
- Steven Kitzes

Theory, Practice, and Balance

When I landed my first software gig almost four years ago, I was a self-taught programmer. Not to say that I didn't have help along the way; I had loads of tutoring and mentoring from friends. Point being, it was my own motivation that kept me going, and my own intuition that determined the direction my learning process would take. I had no formal training, schooling or guidance to keep me on track or ensure that I'd learn any particular skill set or theory in any kind of organized way.

Especially in the beginning, before I was ever employed as a developer, my goal was to get to a point where my learning could become a self-sufficient process. For example, an early task I assigned myself was to learn enough about a programming language to get "hello, world" on the screen so I'd have something to build on from there. I explored IDEs and debuggers so I could figure out what was breaking in my rudimentary programs. I dove into docs, grabbed third party libraries to help, and set up RTEs. I don't think many in the community would argue that these aren't useful skills, if not important, maybe even essential skills. But essential or not with respect to any kind of career path, I was learning them haphazardly based on immediate need.

By the time I started at my first job, I had made it to the point where I could jump onto a project and start delivering serviceable work within a few days, but my code wasn't what you might call optimal. It became quickly evident that there were a lot of gaps in my knowledge, skills, and experience that were holding me back. I understood, more or less, how to solve simple problems with code, how to compile and debug; I even stuck to some common best practices in program design from what I had picked up along the way. But I sure didn't know anything about math, theory, or architecture. Set theory, data structures, state machines, binary trees, Boolean algebra, recursion; even stats, calc, the supposedly basic stuff, linear algebra; let alone dynamic programming, approximation, or any of the other heavy theory you'll stagger through in upper division computer science coursework. At the time, I just knew how to code, even if the code came out slightly more organized than a trash can filled with spaghetti, and hey - for that first job, it was enough.

I know from experience that this is a common attitude for some self-taught programmers. "Hey, it compiles, and it works for most cases, what do you want?" Well, depending who you want to work for and what you want to do with your life, there's plenty there to want, especially as the low-hanging fruit of the software development world is phased out of the career curriculum almost entirely in place of more challenging architectural and mathematically challenging problems.

Now that I'm in the thick of an academic Computer Science program to fill some of the early gaps in my knowledge, I'm inundated in the polar opposite of a practicality-focused paradigm. This semester, for example, I'm taking classes in discrete math, formal proofs, and logic; set and language theory and automata; and operating system theory. So far, over a month into the semester, not a single line of code has been requested or demonstrated by any of my professors. In all honesty, hyperbole and exaggeration aside, a computer has not even been mentioned in the classroom. Where is the code? The practice? The application? Over a year into the curriculum and no one has so much as mentioned a debugger, spoken a word on environments, given a nod to APIs or anything of the sort. They are completely ignoring the fact that one day, presumably, we'll need to actually apply all this math and theory to something. They are training us all to be mathematicians and PhD candidates.

Both of the above situations - the plight of the inexperienced CompSci grad, and the crude hacking style of the common self-taught developer - probably sound familiar to anyone who has spent significant time on the job as a professional developer. Even with my limited experience and time in the field, I've met both. Employers have complaints about these two types of entry level job candidates, and I think they are valid points to make. No one wants to hire a kid who can technically write a program, but can't for the life of him do a good job of it because he has never considered testing, or any kind of process, or software engineering principles, or the fact that someone - maybe even him- or herself - is going to have to maintain that code one day. On the other hand, it's rarely a good idea to hire a math whiz with a CompSci degree who has, ironically, no clue how to open Excel, let alone IDEs. I have had professors who prototype in notepad.exe and teach three-generation-old UI libraries because it's what they know best and they're too lazy to keep up on the tech and it's too easy to give the excuse that hey, sometimes you have to maintain legacy code. True as that may be, and though it may be a separate issue, it's part of the larger problem. At any rate, what does it tell you about the practical skills of the resultant graduates?

I hear complaints from employers that CompSci grads too often come out of school knowing such-and-such theorem and So-and-So's Law but with no idea how to use any of it in the workplace; and that self-taught programmers with drive to succeed have taught themselves how to compile and debug but haven't the slightest clue how to improve their algorithms - or, heaven forbid, toss in a comment here and there. So, what do we do about it?

I understand that opinions are a dime a dozen and my commentary is a drop in the bucket of sentiment on this topic, but I have lately felt the need to share it anyway, because these issues have impacted me both as a member of the workforce, and as a self- and university-taught developer. It seems, frankly, outrageous that more effort isn't being put into a combined emphasis on real-world application and theory. Students have to be given some kind of bigger picture with hands-on experience, so that they can connect the theory to the application. A few schools do seem to be getting it; I have one friend who graduated from a technical college with boatloads of practical experience, in addition to a detailed understanding of the math and theory on which best practices and problem solving are founded. But this guy is a painfully rare exception. I, for example, would never have learned how to set up my machine and get myself jump-started on a project without my own extracurricular work, industry experience, and attention from concerned personal contacts. Not to say that students shouldn't be doing any extracurricular work, but leaving the critical element of hands-on experience out of the schooling process by policy is counterproductive to the ultimate goal of schooling: which is preparing students for the real world.

As for the self-taught developer and self-driven learner, the onus is on the community to give a sense of importance to the concepts underlying best practices and solutions to complex computing problems. When someone green behind the ears comes onto a forum to ask a question, instead of dismissing it as stupid, or shunning them with a condescending LMGTFY GTFO, or telling them to just do their project in an easier language, it is up to those with more experience to guide them to better solutions and opportunities for self-education. Otherwise, who do we have to blame when our co-workers are writing hacked up code that we have to fix for them?

Thanks for reading!
- Steven Kitzes

Android SDK Setup Pitfalls in Windows 7 without Eclipse

I'm delving into Android development for the first time and ran into some trouble during the SDK setup on my Windows 7 machines. I wanted to use an IDE other than Eclipse, which complicated things somewhat. For example, if you're not using the Eclipse-ADT (Android Development Tools) bundle, you'll be keeping a lot more cozy with the command line. But I followed the provided platform-specific documentation as closely as possible and still ran into snags that cost me a lot of time. Hopefully by piecing together a write-up of my experience I can cement the process in my mind and consolidate some of this information to save others time during their setup.

Resources, Downloads, Installation

First, if you are new to Android development, I recommend visiting and bookmarking the Android developer home page. From there you can (sorta) easily navigate to all the resources and information you need to get started. If the installation of the SDK goes smoothly (which I hope to help facilitate with this post), you can follow their tutorial and probably get a "hello, world" Android app up and running inside an hour.

Start by installing the Android SDK (not the Eclipse-ADT bundle). Following the documentation for the SDK installer and resource download went smoothly for me. The only thing to mention is that there is some finagling you have to do to get all the licenses accepted in the SDK Manager if you want any of the options that aren't specified in the documentation (there are multiple methods of accepting certain licenses for some reason).

Using a Batch Supportive CLI

One thing they won't tell you in the docs that they should, is that the command line input they give you includes some batch file execution. When I was going through this process, I was using Git Bash. This was causing me all kinds of problems because the syntax you use to execute batch files in Git Bash or other third party shells is different from that you'd use at the Windows 7 command line. I kept getting android: command not found and I didn't understand why, because I had correctly added all my directories to the Windows PATH variable and everything. Even once I'd figured out that these were batch files and needed different syntax to be run, it took me a while to realize that the reason the execution was failing wasn't just because my syntax was wrong, but because the Git Bash just doesn't fully support batch file execution.

In short, the Android documentation assumes you're using a CLI that provides full support of Windows batch file execution.

Setting Up an Android Virtual Device and Emulation

Skip this if you only plan to test on physical Android devices. I wanted to test virtually so I had to set up the emulator. For the emulator to run on Windows 7, you can't give your virtual Android device too much memory or the emulator will crash. I was getting errors from emulator_arm.exe when trying to run my virtual Nexus 7. Reducing the allocated memory on the virtual device from 1024 to 512 allowed me to run the emulator with no trouble (though I'm not confident this provides a realistic testing environment down the road).

Also note that when loading the emulator, the virtual device's boot time may be quite long. I have a reasonably quick laptop with SSD, 8GB RAM, yadda yadda yadda, and it still took a couple of minutes to boot the emulator. Be patient, don't panic.

Windows Environment Variables, Including JAVA_HOME

Throughout this process, you may well find yourself working with Windows environment variables, including the PATH variable, at length. Be careful, you can do some pretty annoying damage to your system if you are careless in there. Follow directions carefully and correctly to make sure everything will work and you don't lose any important system information that may already have been added to any Windows environment variables.

This is a preemptive note for the next section, but important nonetheless. There is a command line application you'll need by Apache called Ant. It's a command line build tool for Java projects. When installing Ant, make sure you add that to your Windows PATH variable. Otherwise, when you try to run Ant you'll just get the classic 'ant' is not recognized as a an internal or external command error. Next, you need to make sure a Windows environment variable called JAVA_HOME is correctly pointing to the location of the JDK (Java Development Kit) on your system, because Ant uses the JDK. If the JAVA_HOME variable doesn't exist, just create it (I had to).

Installing an App onto an Android Device

At long last, I had the SDK all set up and I'd gotten the sample "hello, world" app built. To install an app onto a device (virtual or physical) for testing, the documentation first tells you to navigate to your project root directory and enter ant debug at the command line. They don't tell you what this does, why it's important, or most critically, that Apache Ant (which you can download and learn more about here), may not even be installed on your system, and is essential to the tutorial in the documentation. Now you know.

Finally

Now I'm running Android apps in emulation. My next step is to try running the "hello, world" app on a physical device, then I'm off to the races. Hope you found something here to help you along the way on your Android journey! And as always...

Thanks for reading!
- Steven Kitzes

The Story of My First Significant Java Project - Path Finding Using Frameworks and Data Structures

Last month I went back to school, and now I'm officially on the books as a CompSci Master's student. This week, I tackled my first big assignment, and it was a bit of a doozy.

By way of context, I'm coming into this Master's program with some real-world work experience. I previously worked at a video game company, and have also made a few small PC games of my own (most notably a couple of 2D "bullet hell" shooters, for which I developed my own modest game designs, physics engines and AI routines). As such, I already have some of what is being taught in this curriculum in my repertoire. But the assignment I'm writing about today comes from an accelerated hybrid course on data structures, path finding, database administration and integration of custom frameworks. It is one of several courses that are famous within the program as having been added to the curriculum explicitly for the purpose of weeding out the poor kids who aren't cut out to be developers.

The assignment itself required us to write a program that satisfied the following requirements:

• generate a navigation mesh based on topographical map and geological/natural resource data provided in a text file
• read in mouse clicks to define starting and destination waypoints on the map
• include a "robot" (rudimentary AI) with limited traversal capabilities (stamina, resources, strength for handling inclines in 3-space, etc) that will try to find a path from start to destination
• utilize (and modify if necessary) a custom graphics and time (framerate) management framework provided by the professor and written in Java to display everything in a window

So, there was a lot to do, and a lot to learn along the way. Just as one example, my work experience has revolved mostly around UI engineering, and though I'd created rudimentary AI algorithms for my bullet hell games, this was my first time working with anything like nav meshes and pathfinding. This was also my first time using Java. I've made a few dumpy practice programs to learn some of the basics, but on day one, even something as simple as reading and parsing a text file, or working with an array was a non-trivial task. And of course, because I had to balance this with my work from other classes and didn't want to neglect my non-academic projects, I ended up with only three days to do everything.

At the time of this writing, I'm not actually done with the project (hah!). But it isn't due for another week and a half, and the remainder of the work is housekeeping (hiding print calls behind DEBUG flags and cleaning up documentation, for example). In any case, I'm happy with what I've produced, and I'd love to talk about everything I learned along the way. But there too much of it, so I'll fixate on my proudest achievement, the "simple path" pathfinding algorithm that I used in this iteration of the project, which will serve as a stepping stone to more complex iterations that will end up using the A* algorithm, remote database interactivity, and multiple simultaneous AI "players"!

In class, we have already learned about Dykstra's algorithm and the A* algorithm for path finding. These are both very good (much better, anyway) algorithms for path finding than the "simple path" algorithm I came up with. However, given the limited time to complete this task and the requirements set forth by the professor (he actually demanded a "simple path" solution for the first assignment as a stepping stone), I'm very happy with how quickly I generated a solution.

Simply put, I begin with a while loop. This loop will iterate until the robot runs out of stamina, the goal has been reached, or the robot has worked itself into a corner (backtracking is not allowed). Inside the loop, I first establish the current location of the robot (the nav mesh node it currently sits on). Then, I build an adjacency list for that node; in other words, a list of every node that the robot can navigate to from the current node. (A candidate node will only be added to the adjacency list if all of the conditions for travel between it and the current node are met; the candidate must not have been visited already, it must be close enough in 3D space (not too much of a slope), the robot must have enough stamina left to reach the candidate node, and there must actually be a node there.)

At this point, I can already kill the program if the adjacency list size is zero; if the bot has no means to reach any node adjacent to its current node, it is trapped and the traversal is a failure. However, if there is at least one candidate node available for travel, I compare the distance between the goal and each candidate node in the adjacency list. I choose the navigable candidate that is closest to the goal, and move the bot there (adjusting its stamina values along the way, based on terrain difficulty and discovered resources).

After each movement of the robot, I check if it has reached the goal. If so, that's a successful traversal! If not, I check if the robot's stamina has been exhausted. If so, that's a failed traversal, and if not, I can continue with another iteration of the while loop until and exit condition is met.

Not too shabby!

I would have loved to post some of my code, but due to my professor's concerns regarding plagiarism (which I find to be valid) I will have to refrain for now. But, as always...

Thanks for reading!
- Steven Kitzes

Understanding Java from a C++ Background

A short note of thanks before I begin. Some friends showed me a lot of shortcomings in the way I was thinking about this problem. That led to a huge, sweeping revision of this article. Hopefully it is more correct, coherrent and usable now.

I was born and raised in a world of C++, which treats class objects and primitives the same way. You can pass any variable around between functions either by value, or by reference. My dependency on this paradigm never became more apparent to me than when I finally made the switch to another language: Java.

C++

In C++, you can instantiate a class object, let's call it MrObject. You can then also create a pointer to it. Let's call that MrPointer. If you then decide you want access to MrObject's data in another function, there are a lot of ways you can do this. You can:

Pass a reference to MrObject into the function using the '&' operator, giving you direct access to the original instance of MrObject himself.

void MrFunction(MrObjectClass &MrObjectRef) {...}

Within MrFunction, you can use MrObjectRef just the same as if it were MrObject himself, because this is literally just creating another alias for the same exact object in memory.

You can also:

Pass by value, creating a new instance of a MrObjectClass inside MrFunction that is a duplicate of MrObject.

void MrFunction(MrObjectClass MrObjectDupe) {...}

When you pass MrObject into this function by value like this, a new class object called MrObjectDupe is created within the function. The original MrObject stays where he is, and is isolated from anything that is going on within MrFunction.

Things get a little more tricky when you create pointers to MrObject and try passing those into functions. For example, let's say you make a pointer to MrObject, like so:

MrObjectClass * MrPointer = &MrObject;

If you're not fluent in C++, what we are doing here is not creating a new MrObject. The asterisk (*) tells us that we are creating a pointer to an object of type MrObjectClass. The name of the pointer is MrPointer. The assignment here (=), combined with the ampersand (&), tells us that the specific object in memory that MrPointer points to is the one named MrObject (which must be declared elsewhere, but can, if you wanna be fancy, be defined through MrPointer via the new keyword, for example).

Now, if you want to pass MrPointer into a function, C++ also allows you to pass that either by value, or by reference. In other words, you can:

Pass a pointer by value; create a new pointer with the same value as the pointer you passed into the function. In other words, a new pointer, but one that points to the same address as the pointer that was passed into the function.

void MrFunction(MrObjectClass * MrPointerDupe) {...}

The asterisk must still be included so that C++ knows MrPointerDupe is a pointer. The side effect of this is that we can access MrObject through this duplicated pointer, but if we point MrPointerDupe at a new address (to a different object of MrObjectClass, or a new one, or to null), then the original MrPointer will remain unaffected, still pointing at (and modifying, if dereferenced) our original MrObject.

Alternatively, you can:

Pass a pointer by reference; in other words, we are not creating a new pointer to MrObject, we are using the same original MrPointer; we are just creating a new alias for MrPointer to be used within MrFunction.

void MrFunction(MrObjectClass * &MrPointerAlias) {...}

The asterisk in this case tells us that we are declaring a pointer to an object of type MrObjectClass, and the ampersand tells us that the pointer we are creating is not a new pointer, but just an alias (another name) for the existing pointer that is getting passed in to MrFunction.

Java

The nature of Java variables may not seem clear at first, coming from a C or C++ background. In Java, every variable you declare is a reference (except for primitives like int or boolean). Even primitive types such as int have Java class equivalents that give you reference type variables for handling primitive types (such as Java's Integer class).

Why is this so important? Just taking one important example, in C++, you might be used to creating a new instance of a class object, then being able to copy it into another second class object, like so:

// C++ code to create a new instance of MrObjectClass called MrObject.
MrObjectClass MrObject();

// C++ code to create a second, separate instance of MrObjectClass called
// MrDuplicate, by copying MrObject. Note that this results in two
// distinct class objects in memory.
MrObjectClass MrDuplicate = MrObject;

By contrast, in Java, when you instantiate a class object like so:

MrObjectClass MrObject = new MrObjectClass();

you are not creating a class object called MrObject. You are implicitly creating a reference to an object of type MrObjectClass, and that reference is called MrObject. In the following Java snippet, the two declarations result in only one distinct class object instance, which has two reference variables referring or "pointing" to it. (Though these variables are not pointers, I found it useful to think about them as such in the beginning, as a sort of "training wheels" approach to getting going in Java. However, of course you should try to build an understanding of Java's implicit referential nature as early as possible.)

// Java instantiation of a reference called MrObject to a nameless object
// of type MrObjectClass
MrObjectClass MrObject = new MrObjectClass();

// Java instantiation of a second reference called MrDuplicate, which
// actually refers or "points to" the same nameless object as MrObject
// refers to, resulting in only a single nameless MrObjectClass object
MrObjectClass MrDuplicate = MrObject;

It's very important to understand this so that you will understand what happens the first time you attempt to duplicate a class object, then modify your new variable only to see the changes reflected in your first variable as well! In other words, in Java, you cannot create a MrObject that you have "direct" C-style access to. Also, perhaps most importantly, it's critical to remember that reassigning MrObject or MrDuplicate does not overwrite any data! MrObject and MrDuplicate are references, and reassigning them simply points them to new memory locations. This can, in turn, potentially leave data unreferenced, in which case Java automatically cleans it up (but this unpredictable, sometimes seemingly sporadic process, often called garbage collection is another topic for another day).

Another reason this concept is so important to grasp early on in a programmer's exposure to Java, is because Java does not support pass-by-reference! In other words, even if you get used to the fact that everything in Java is a reference, you then have to accept that all functions in Java are pass-by-value! In other words, if I pass my MrObject reference from the example above into a function, the result is that within that function I cannot directly manipulate the original MrObject, ever!

What's happening within the function is we are creating a new reference variable whose value (referred or "pointed" address) is the same as MrObject's, because that is what's passed by value. Using the new reference inside the function, we can access our referred, nameless class object's public members. But if I try to reassign my reference variable from within my function, only the duplicated reference variable within the function will refer to the new destination address (nameless class object instance) I designate (including, possibly, null); the original MrObject reference outside the function will still point to (and protect from garbage collection) the original address (nameless class object) it originally referred to in the first place.

Are there ways to simulate pass-by-reference for those instances where you really want that behavior? Sort of (storing reference variables in an array or container class and passing the array or container itself into functions by value to preserve the original pointer-like variables within is the closest I can come up with so far, though these can feel like clumsy substitutes for true pass-by-reference). But when possible, it's better to just be aware of Java's idiosyncrasies and think in a Java-like way; its lack of pass-by-reference, and its requirement that all non-primitive class object variables are references; and to design around these features to the extent possible.

Thanks for reading!
-- Steven Kitzes