A question was asked in last Sunday's Boston Globe, in its 'Etiquette at work' section, on how to avoid appearance of cliques. The person who asked the question has formed a group (clique) at her office that eats lunch together on a day every week. Her manager joins the group once in a while without invitation and the questioner was asking how to resolve this situation. Clearly, cliques are important part of our social life but what does that have to do with computer science?
There was a very interesting article in the MSDN's October issue by Dr. McCafferey. It's the first of a series of articles explaining what a clique is and the importance of finding the maximum clique in a graph and the algorithm to solve the problem. So what is a clique in a graph? Clique is a subset of a graph where every node is connected with every other node. Following paragraph is directly quoted from the
MSDN issue -
Maximum clique problem is encountered in wide range of applications, including social network communication analysis, computer network analysis, computer vision and many others. For graphs of even moderate size, it turns out that the maximum clique problem is one of the most challenging and intersting problems in computer science. The techniques used to solve the maximum clique problem - which include tabu search, greedy search, plateau search, real-time parameter adaptation and dynamic solution history - can be used in many other problem scenarios. In short, code that solves the maximum clique problem can be directly userful to you, and the advanced techniques employed in the alogrithm can be helpful for solving other difficult programming problems. In the following figure the set of nodes 0, 1, 3, 4 form the maximum clique.
While working towards solving this problem, I found myself reflecting on my school years.
When I grew up in India, I disliked mathematics like every one else. Most students were true haters but others loved it only because it provided an opportunity to score perfectly in a test. Achieving the perfect score wasn't that harder in spite of our dislike, because every teacher and parent instilled this notion that good score in Mathematics is the yardstick of your intelligence. No matter you liked math or not, or scored perfectly or not, I seriously doubt if any student was interested in knowing why mathematics was needed at all. Any one who dared to raise the question, would typically have to face the silent treatment from the teacher.
Through out the school years, from the day I learnt to count numbers to the days of triple integration in engineering school, I must have asked this question to myself countless number of times. However, by the time I graduated, I was grudgingly admitting to myself that mathematics used to be and would forever be the foundation stone of so many fields of science. Despite my dislike, I thought I won't escape mathematics due to my engineering profession, but then, personal computers took over the world, India's software industry boomed and all every student could think of, was becoming a software professional. It provided a level playing field for all, engineers and non-engineers alike. Any one with decent analytical skills could become a programmer. Engineers too became software programmers en mass and marvelled at the thought of not having to do anything with mathematics any more.
Really? Would software profession be that exciting or sexy if you take away search alogrithms by Google, content distribution algorithms by Akamai or algorithms developed for ultra fast equity trading by nerds on wall street? Take away this exciting stuff and what remains is the mundane 'go to', 'if then' statements or uber present 'do while' or 'for when' statements. So, whether we like it or not, mathematics is the foundation required to solve challenging problems .
The reason for the post though, is to post Java code I wrote to solve maximum clique problem for the following graph. Readers are encouraged to see if the code works on other graphs. I didn't want to look at the solution presented by Dr. McCafferey (which by the way is going to be C# code) before I tried it myself. Creating the data set (storing graph information like nodes and segments) is a challenge in itself. I have taken a short cut by creating a static array of strings to represent segments of the graph. My co-worker Tyler Perry worked on a c++ solution to this problem while I worked on the Java solution. If you like to see more of such posts click on +1 button at the bottom or use share widget on the right to share it with others. My code was tested on the following graph.
There was a very interesting article in the MSDN's October issue by Dr. McCafferey. It's the first of a series of articles explaining what a clique is and the importance of finding the maximum clique in a graph and the algorithm to solve the problem. So what is a clique in a graph? Clique is a subset of a graph where every node is connected with every other node. Following paragraph is directly quoted from the
MSDN issue -
Maximum clique problem is encountered in wide range of applications, including social network communication analysis, computer network analysis, computer vision and many others. For graphs of even moderate size, it turns out that the maximum clique problem is one of the most challenging and intersting problems in computer science. The techniques used to solve the maximum clique problem - which include tabu search, greedy search, plateau search, real-time parameter adaptation and dynamic solution history - can be used in many other problem scenarios. In short, code that solves the maximum clique problem can be directly userful to you, and the advanced techniques employed in the alogrithm can be helpful for solving other difficult programming problems. In the following figure the set of nodes 0, 1, 3, 4 form the maximum clique.
Figure 1.
You can find more information on clique problem on Wikipaedia and many other web sites. While working towards solving this problem, I found myself reflecting on my school years.
When I grew up in India, I disliked mathematics like every one else. Most students were true haters but others loved it only because it provided an opportunity to score perfectly in a test. Achieving the perfect score wasn't that harder in spite of our dislike, because every teacher and parent instilled this notion that good score in Mathematics is the yardstick of your intelligence. No matter you liked math or not, or scored perfectly or not, I seriously doubt if any student was interested in knowing why mathematics was needed at all. Any one who dared to raise the question, would typically have to face the silent treatment from the teacher.
Through out the school years, from the day I learnt to count numbers to the days of triple integration in engineering school, I must have asked this question to myself countless number of times. However, by the time I graduated, I was grudgingly admitting to myself that mathematics used to be and would forever be the foundation stone of so many fields of science. Despite my dislike, I thought I won't escape mathematics due to my engineering profession, but then, personal computers took over the world, India's software industry boomed and all every student could think of, was becoming a software professional. It provided a level playing field for all, engineers and non-engineers alike. Any one with decent analytical skills could become a programmer. Engineers too became software programmers en mass and marvelled at the thought of not having to do anything with mathematics any more.
Really? Would software profession be that exciting or sexy if you take away search alogrithms by Google, content distribution algorithms by Akamai or algorithms developed for ultra fast equity trading by nerds on wall street? Take away this exciting stuff and what remains is the mundane 'go to', 'if then' statements or uber present 'do while' or 'for when' statements. So, whether we like it or not, mathematics is the foundation required to solve challenging problems .
The reason for the post though, is to post Java code I wrote to solve maximum clique problem for the following graph. Readers are encouraged to see if the code works on other graphs. I didn't want to look at the solution presented by Dr. McCafferey (which by the way is going to be C# code) before I tried it myself. Creating the data set (storing graph information like nodes and segments) is a challenge in itself. I have taken a short cut by creating a static array of strings to represent segments of the graph. My co-worker Tyler Perry worked on a c++ solution to this problem while I worked on the Java solution. If you like to see more of such posts click on +1 button at the bottom or use share widget on the right to share it with others. My code was tested on the following graph.
Let's do it a little differently this time. Instead of posting the code here, I would like to send it to you directly if requested. Please contact/comment to receive the code.
No comments:
Post a Comment