A little clique "game" in Java - Clique Problem

  • Java
  • Thread starter Jeronimus
  • Start date
  • Tags
    Game Java
In summary, the program looks for maximum cliques in a group of students, by randomly connecting them. You can change the values for the minimum and maximum connections, and the number of students.
  • #1
Jeronimus
287
9
For what it's worth, i created a little java program in relation to the clique problem

https://en.wikipedia.org/wiki/Clique_problem

The idea was, to play around with it and maybe discover some better algorithm than the known ones used to discover all maximum cliques

The code is quite small and can be found here

http://pastebin.com/zUuEscqu

You have to compile it yourself using javac (should work both in linux and windows but i have tested only windows)

An easier method for those who do not know much about programming, would be to download the free drjava IDE (google it) and just copy and paste the code into the IDE. Then hit the compile button and the run button after.
Make sure you have Java installed on your system however.

Here is an image of how this would look like, with the program running on the top left side and the drjava IDE with the code pasted into it.

VVrgWQ9.png


From left to right, the boxes you can enter numbers into act as follows:

1) You can enter a seed for the random number generator or have the program generate one randomly for you.
2) The minimum connections a student or node will build to another student or node.
(The program generates connections for a particular node to other nodes. A minimum of 6 connections will be generated with default values for a particular node.
However, other nodes might also generate connections to this node as they are generated, so the number of connections to other nodes will be greater than this value most likely.)

3) The maximum connections
4) The number of students/nodes
5) The size of the program box in pixels. Increase the number if you have a larger monitor

The green button top right will generate a binary output of the small squares (0 = grey square 1 = red square) in the command line or drjava interaction pane.

The idea is to find the most efficient way of generating a square made up of red squares like the one top right. Red squares symbolize the nodes being connected or "the students know each other, hence are part of a clique".
In this case 1,11,7,9,13,16,14 are part of a clique.

As long as the checkbox bottom left of the program is checked, the columns and rows remain at the same position as you move them.
But you can remove this lock if you believe that it would help you discover an algorithm easier that way.
You just have to make sure that the numbers in the columns and row next to the large square, made out of smaller red squares, are the same. Hence whatever numbers are in the column section of the red square, are also in the row section.

example:

Q2MkmMX.png


Here i removed the lock bottom left. The order of the numbers in the row section of the large square, made up of smaller red squares, does not correspond to the order of the column section any more. It is the same clique still however. 1,7,9,11,13,14,16 being part of one clique.

Hope some might find this little code interesting. Feel free to use the code in any way you like as long as you do not try to prevent others from using it in any way they like :)
 
Technology news on Phys.org
  • #3
Greg Bernhardt said:
Looks good, nice work!

Thanks. However, more accurate would have been "Looks good, it works". I am just a hobby programmer, not coding much really and i made a terrible mistake in this code. It only works because of "luck" in a sense.

I used if (str==("<some String>")){ to compare the strings but the proper way is if (str.equals("<some String")){

The only reason it worked, is because the JVM is smart enough to use the same reference for equal strings. But that isn't always the case, so it might break for other programs.
So i was comparing the references rather than the strings themselves.

Here is the fixed version http://pastebin.com/zpReBGK0
also cleaned of some obsolete System.out.println calls i used for debugging and forgot to remove.

It's not really absolutely necessary to use the new version. The old works i guess because i got lucky, but i had to set this straight for anyone who actually wants to use part of the code for their own projects.
 

1. What is the "Clique Problem" game in Java?

The "Clique Problem" is a game in Java that involves finding the largest group of people within a larger group who all know each other. The goal is to find a clique, or a complete subgraph, within the larger graph of people.

2. How does the Java program for "Clique Problem" work?

The Java program for "Clique Problem" works by inputting a graph of people and their connections, and then using algorithms to find the largest clique within that graph. It utilizes concepts from graph theory and algorithms such as depth-first search and backtracking to efficiently find the solution.

3. What are the applications of the "Clique Problem" game in Java?

The "Clique Problem" game in Java has various applications in computer science, including network analysis, social network analysis, and community detection. It can also be used in real-world scenarios such as identifying influential individuals in a group or finding the best group of people for a specific task.

4. Is the "Clique Problem" game in Java a difficult problem to solve?

The "Clique Problem" is classified as an NP-complete problem, meaning that it is difficult to solve efficiently for large input sizes. However, with the use of efficient algorithms and techniques, it is possible to find approximate solutions or generate optimal solutions for smaller instances of the problem.

5. Are there any alternative versions of the "Clique Problem" game in Java?

Yes, there are various alternative versions of the "Clique Problem" game in Java, such as the weighted clique problem, where the goal is to find the clique with the highest total weight, and the densest subgraph problem, where the goal is to find the largest subgraph with the highest density. These variations can provide different challenges and applications for the game.

Similar threads

  • Programming and Computer Science
Replies
4
Views
4K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Special and General Relativity
Replies
5
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
5K
  • STEM Academic Advising
Replies
6
Views
847
  • Engineering and Comp Sci Homework Help
Replies
4
Views
7K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
Back
Top