Prev: Help for Simplescalar's cache.c code
Next: signal
From: arne.muller on 30 Jan 2007 11:49
Dear All,

I'm new to this group and I'm not really sure whether this is the
right place to ask - so please let me know if this is off topic ... .

I'm looking for an implementation of the Bron-Kerbosh algorithm for
clique detection in graphs, preferably in C. Any hints are very
welcome.

thanks in advance,
+kind regards

Arne

From: Arthur J. O'Dwyer on 30 Jan 2007 14:11

On Tue, 30 Jan 2007, arne.muller(a)gmail.com wrote:
>
> I'm new to this group and I'm not really sure whether this is the
> right place to ask - so please let me know if this is off topic ... .

It's on-topic, but if you'd searched Google first, you wouldn't
have needed to ask the question in the first place.

> I'm looking for an implementation of the Bron-Kerbosh algorithm for
> clique detection in graphs, preferably in C. Any hints are very
> welcome.

An implementation in Java, GPL'ed:
http://www.koders.com/java/fidDE645B4EC64565617F083AAB0AB7A7E2E8741C7B.aspx?s=sort

The correct spelling is "Bron-Kerbosch" (as Google would also have
told you). I haven't looked to see whether the large number of papers
available online explain the algorithm in detail, but you should be
able to extract the algorithm from the JOELib Java code easily enough.

If you have specific questions about the algorithm, or C, or style,
or whatever, please ask! But Usenet is not a search engine: You'll
get more results, and faster, by typing the name of the thing you're
looking for into Google or Ask.com.

HTH,
-Arthur
From: user923005 on 31 Jan 2007 13:57
On Jan 30, 8:49 am, "arne.mul...(a)gmail.com" <arne.mul...(a)gmail.com>
wrote:
> Dear All,
>
> I'm new to this group and I'm not really sure whether this is the
> right place to ask - so please let me know if this is off topic ... .
>
> I'm looking for an implementation of the Bron-Kerbosh algorithm for
> clique detection in graphs, preferably in C. Any hints are very
> welcome.
>
> thanks in advance,
> +kind regards

Java versions:
http://www.jgrapht.org/javadoc/org/jgrapht/alg/BronKerboschCliqueFinder.html
http://joelib.sourceforge.net/wiki/index.php/Bron-Kerbosch

It's ACM algorithm 457:
http://portal.acm.org/citation.cfm?id=362367&dl=ACM&coll=portal

This link looks promising:
http://www.krugle.com/examples/keywords/clique-algorithm.html

I just did a google search and looked at the first 3 pages. I had
never heard of this algorithm before.

From: user923005 on 31 Jan 2007 16:40
This technical report:
http://homepages.dcc.ufmg.br/~nivio/cursos/pa06/tp2/tp22/tp22.pdf

Leads to this code:
http://homepages.dcc.ufmg.br/~msalvim/pos/disciplinas/paa/tp2/fonte/

Which is (I think) exactly what you are after.



 | 
Pages: 1
Prev: Help for Simplescalar's cache.c code
Next: signal