Graph Problem - Finding Cliques
Hi Folks,
I'm stuck with a problem involving undirected graphs and was wondering if anyone might be able to help.
I have a Vector containing pairs of letters which represent edges in a graph from one point to another. e.g. 'ab' would be an edge from point 'a' to point 'b'. In many cases this Vector contains a number of sub-graphs e.g.
ab
ac
bc
de
df
ef
{ab, ac, bc} make up one complete sub-graph and {de, df, ef} makes up another, where each point has an edge to all the other points in the group.
I want to be able to identify these sub-graphs and seperate them (or at least identify them as being different groups). In graph theory I believe these groups are known as cliques.
I am only interested in finding maximal cliques (complete sub-groups) and in my particular situation a point will never exist in more than one clique (so no overlapping groups). Also the vector will only ever contain complete sub-graphs (no incomplete sub-graphs where edges are missing).
Does anyone know how to solve this problem? Any help would be greatly appreciated. Please let me know if you need any more info.
Regards,
Jamie
[1212 byte] By [
ph0enixa] at [2007-10-1 19:37:38]
The subgraph isomorphism problem is NP-complete. There are approximation algorithms, see e.g. http://citeseer.ist.psu.edu/alon98finding.htmFor small graphs you can solve the problem with a brute force approach but for large graphs the problem is intractable.
Your first question is, "how to find the 1-connected components"?
Typically this is done by building a graph data structure and running a DFS or BFS search on it.
for each node n
if (n is not visited) {
// found new 1-connected component
DFS(n);
}
}
DFS(n) {
push n on Stack
while (Stack is not empty) {
n = pop(stack)
n.visited = true;
//etc
}
}
Your next question is how to identify the largest clique in each component. This is an NP complete problem. However, it's fairly
easy to code a brute force algorithm. Search the forums for the answer to do this:
http://onesearch.sun.com/search/onesearch/index.jsp?qp_name=null&qt=clique&subCat=siteforumid%3Ajava426&site=dev&qp=siteforumid%3Ajava426&chooseCat=javaall&col=developer-forums
I use the following O(n^4 or less) method in my map-folding algorithm:
static int fastGroups(Group[] group, boolean[][] join, int n) {
int[] g = new int[n];
boolean[] row;
int c = 0, d;
for(int i=0, j, k, m; i<n; i++) {
for(j=i+1; j><n; j++) {
if(!join[ i][j]) continue;
for(m=0; m><c; m++) {
if(group[m].contains(i) && group[m].contains(j)) break;
}
if(m><c) continue;
for(k=0, d=0; k><n; k++) {
row = join[k];
if(!row[ i] || !row[j]) continue;
for(m=0; m><d; m++) if(!row[g[m]]) break;
if(m==d) g[d++] = k;
}
group[c++] = new Group(g,d);
}
}
group[c] = null;
return c;
}
This populates the cliques in the given array and returns the number of cliques.
This method works with "well behaved" groups, where each group can be achieved by choosing some two elements of it and then searching the rest in order of appearance. So if you have the followin cliques (1,4,5), (2,5,6), (3,4,6) and (4,5,6):
1-4-3
\ /\ /
5-6
\/
2
you will miss the clique (4,5,6). In your case this should not be a problem.>
Is it possible to return say a Vector where each element is a String Object containing each clique found? So instead of finding the number of cliques it returns the actual cliques identified.
As pointed out above, this problem is NP-complete. However
it is only NP-complete if considering any input instances
of the problem. For many subsets of the set of all possible
input instances, it is NOT NP-complete.
What you can do is to try to find properties of your input
sets that you can use to find a fast algorithm. Do you have
any additional information on these input sets?
parza at 2007-7-11 15:53:49 >
I had a similar situation and I solved this as below. Call it a brute force approach but gets my thing done where my graph is not too big (about 1000 nodes): -
My problem was:
To find the begining nodes i.e. the nodes which do not have incoming edges and may or may not have out oing edges in your situation node "d" and node "a". I used Java object design along with small algorithm.
I wrote following classes
Graph, Node and Edge
Node can be created only by Graph so that Graph becomes creational factory and keep track of all nodes. Each node contains a list of outgoing Edge and list of incoming Edge. Edge can have 2 attributes incomingNode and outoingNode of type Node. Graph object will do the job of creating node and link them as well thereby it can track what nodes do not have incoming Edge.
You need the Nodes that do not have ant incoming Edges. Once you get hold of Nodes you are in essence holding the subgraph.
Good luck
