Re: Maximal Clique

[Stefan Balev <stefan.balev AT gmail.com>]

Hi Rodrigo,

Here is a "quick and dirty" implementation. Basically it consists in
enumerating all the cliques and keeping the best found. As Julian, I
think that it is hopeless for the size of your graphs, but you can
give it a try.

Cheers,

--
Stefan

2011/6/20 Rodrigo Lins 
<lins.oliveira AT gmail.com>:
> Hi Julien,
> You can do this algorithm?
> In my project, i use all active stock (140 stocks) in BOVESPA (a stock
> exchange from Brazil).
> And i use an algorithm to find the Pearson Product Momentum between all
> stocks. Every stock represent an node in my graph and If the PPM > than a
> empirical value, i put a vertice between this nodes. Then i need to find the
> maximum cliques and plot this graph.
> I'm already calculating the PPM. Now, i need to calculate the maximal clique
> and plot a graph.
>
> Thanks for all,
> Rodrigo.
>
> On Mon, Jun 20, 2011 at 10:21 AM, julien schleich 
> <julien.schleich AT uni.lu>
> wrote:
>>
>>
>> Thanks Frederic,
>> My graph have at the maximum 140 nodes and 140*140 vertices.
>>
>> With this size of graphs, I would give up finding an optimal solution.
>> Really.
>>
>> The computational effort it's no a problem. I need only to make an image
>> with the graph.
>> I have found this implementation
>> (http://code.google.com/p/jung/issues/attachmentText?id=2&aid=20000001&name=BronKerboschCliqueFinderTest.java&token=7f10e4f3acb29d35ffa92a2744dfc3ca)
>> but i'm using the Graph Stream graph objects and i dont want to use the
>> JUNG framework.
>> If you can make an implementation of this algorithm i'll be very happy!
>> Thanks for your patience and your help!
>> If you can't do this, let me know, and I will try to use a JUNG or make an
>> implementation!
>>
>> Thanks a lot,
>> Rodrigo.
>>
>> 2011/6/20 Frédéric Guinand 
>> <frederic.guinand AT gmail.com>
>>>
>>> Hello Rodrigo,
>>>
>>> What is the size of your graph(s)?
>>>
>>> I can try to implement a quick'n'dirty algo if you really need this
>>> urgently.
>>>
>>>
>>>     Frederic
>>>
>>>
>>> Rodrigo Lins wrote:
>>>>
>>>> Hi Stefan,
>>>> I need only to find a maximum cardinality.
>>>> I mount the graph based in a correlation algorithm.
>>>> I`m looking for a implemented algorithm or if the graph stream have one
>>>> implementation.
>>>>
>>>> Thanks a lot,
>>>> Rodrigo.
>>>>
>>>> On Sun, Jun 19, 2011 at 5:56 PM, Stefan Balev 
>>>> <stefan.balev AT gmail.com
>>>> <mailto:stefan.balev AT gmail.com>>
>>>>  wrote:
>>>>
>>>>    Hi Rodrigo,
>>>>
>>>>    If you can wait, just use a brute force approach. Is your graph
>>>>    weighted or you just want to find a maximum cardinality clique ?
>>>>
>>>>    Cheers,
>>>>
>>>>    --
>>>>    Stefan
>>>>
>>>>
>>>>    2011/6/19 Rodrigo Lins 
>>>> <lins.oliveira AT gmail.com
>>>>    
>>>> <mailto:lins.oliveira AT gmail.com>>:
>>>>     > Thanks Frederic for your answer.
>>>>     > But I really need to find de cliques in a graph, and I know this
>>>>    algorithm
>>>>     > is a NP-Hard problem.
>>>>     > I realy need to find the maximum cliques in a graph. I can wait.
>>>>     > Thanks,
>>>>     > Rodrigo.
>>>>     >
>>>>     > 2011/6/19 Frédéric Guinand 
>>>> <frederic.guinand AT gmail.com
>>>>    
>>>> <mailto:frederic.guinand AT gmail.com>>
>>>>     >>
>>>>     >> Hello Rodrigo,
>>>>     >>
>>>>     >> The problem of finding the maximum clique in a graph is an
>>>> NP-Hard
>>>>     >> problem. In other words, it is not possible to do so in a
>>>>    reasonable time
>>>>     >> (polynomial in the size of the graph). So, any method for
>>>>    finding a maximum
>>>>     >> clique is equivalent to use a brute force approach.
>>>>     >>
>>>>     >> If you want to know more:
>>>>     >>
>>>>     >> http://en.wikipedia.org/wiki/NP-complete
>>>>     >> http://en.wikipedia.org/wiki/Clique_problem
>>>>     >>
>>>>     >> What was the original problem you try to deal with?
>>>>     >>
>>>>     >>     Bye,
>>>>     >>
>>>>     >>         Frederic
>>>>     >>
>>>>     >>
>>>>     >> Rodrigo Lins wrote:
>>>>     >>>
>>>>     >>> Anyone knows if it is possible to find a maximal clique in a
>>>>    graph using
>>>>     >>> GraphStream?
>>>>     >>> If it is possible what class do it?
>>>>     >>>
>>>>     >>> Thanks a lot!
>>>>     >>> Rodrigo.
>>>>     >
>>>>     >
>>>>
>>>>
>>
>>
>
>
import java.util.ArrayList;
import java.util.List;

import org.graphstream.algorithm.generator.Generator;
import org.graphstream.algorithm.generator.RandomGenerator;
import org.graphstream.graph.Graph;
import org.graphstream.graph.Node;
import org.graphstream.graph.implementations.SingleGraph;


public class MaxClique {
	protected Graph graph;
	protected List<Node> currentClique;
	protected List<Node> bestClique;
	
	public MaxClique(Graph graph) {
		this.graph = graph;
		currentClique = new ArrayList<Node>();
		bestClique = new ArrayList<Node>();
		List<Node> candidates = new ArrayList<Node>(graph.getNodeSet());
		enumerateCliques(candidates);
	}
	
	protected void enumerateCliques(List<Node> candidates) {
		if (candidates.isEmpty()) {
			if (currentClique.size() > bestClique.size())
				bestClique = new ArrayList<Node>(currentClique);
			return;
		}
		List<Node> nextCandidates = new ArrayList<Node>();
		for (int i = 0; i < candidates.size(); i++) {
			Node candidate = candidates.get(i);
			currentClique.add(candidate);
			nextCandidates.clear();
			for (int j = i + 1; j < candidates.size(); j++) {
				Node x = candidates.get(j);
				if (candidate.getEdgeBetween(x.getId()) != null)
					nextCandidates.add(x);
			}
			enumerateCliques(nextCandidates);
			currentClique.remove(currentClique.size() - 1);
		}
	}
	
	public List<Node> getMaxClique() {
		return bestClique;
	}
	
	public static void main(String[] args) {
		Graph graph = new SingleGraph("test");
		Generator gen = new RandomGenerator(8);
		gen.addSink(graph);
		gen.begin();
		for (int i = 0; i < 20; i++)
			gen.nextEvents();
		gen.end();
		graph.display();
		
		List<Node> clique = new MaxClique(graph).getMaxClique();
		for (Node x : clique)
			x.addAttribute("ui.style", "fill-color: red;");
		for (int i = 0; i < clique.size(); i++)
			for (int j = i + 1; j < clique.size(); j++)
				clique.get(i).getEdgeBetween(clique.get(j).getId()).addAttribute("ui.style", "fill-color: red;");
	}
}