Recursion with loops

[Claymz]

Hi all,
im working with undirected unweighted graph, and want to get all of the combinations of two sets, where user inputs the number of verticies for each set, and each vertex of one set must not have any edge connected to any vertex of an other set. So, to get to the point, ive implemented this method for set of size 1 and of size 2, which looks like this:

    public void sets(int num) {

    	List<String> m = new ArrayList<String>(vertEdge.keySet());
    	
    	if(num== 1) {
    		List<Set<String>> blue = new ArrayList<Set<String>>(); 
    		List<Set<String>> red = new ArrayList<Set<String>>(); 
    		int[] rec = new int[num*2]; //this could come in handy for recursive way, i think?
        	
	    	for(rec[0] = 0; rec[0] < vertEdge.size(); rec[0]++) {
	    		for(rec[1] = 0; rec[1] < vertEdge.size() && [B]rec[1] != rec[0][/B]; rec[1]++) {
	    			if([I]!vertEdge.get(m.get(rec[0])).contains(m.get(rec[1]))[/I]) {			
	    				Set<String> visited1 = new HashSet<String>();
	    				Set<String> visited2 = new HashSet<String>();
	    				for(int a = 0; a < num*2; a++) {
	    					if(a < num)
	    						visited1.add(m.get(rec[a]));
	    					else
	    						visited2.add(m.get(rec[a]));
	    				}

	    				if(!((blue.contains(visited1) && red.contains(visited2)) || (blue.contains(visited2) && red.contains(visited1)))) {	
    						blue.add(visited1);
    						red.add(visited2);
		    			}
	    			}
	    		}
	    	}
	    	 //just for the output
	    	for(int a = 0; a < blue.size(); a++) 
	    		System.out.println(blue.get(a)+ " - " + red.get(a));
    	}
    	else if(num== 2) {
    		List<Set<String>> blue = new ArrayList<Set<String>>(); 
    		List<Set<String>> red = new ArrayList<Set<String>>(); 
    		int[] rec= new int[num*2];
	    	
	    	for(rec[0] = 0; rec[0] < vertEdge.size(); rec[0]++) {	
		    	for(rec[1] = 0; rec[1] < vertEdge.size(); rec[1]++) {
		    		for(rec[2] = 0; rec[2] < vertEdge.size(); rec[2]++) {
		    			for(rec[3] = 0; rec[3] < vertEdge.size(); rec[3]++) {
			    			if([I]!vertEdge.get(m.get(rec[0])).contains(m.get(rec[2])) && !vertEdge.get(m.get(rec[1])).contains(m.get(rec[2]))&& !vertEdge.get(m.get(rec[0])).contains(m.get(rec[3])) && !vertEdge.get(m.get(rec[1])).contains(m.get(rec[3]))[/I] /*one type of conditions*/ && [B]rec[3] != rec[2] && rec[3] != rec[1] && rec[3] != rec[0] && rec[2] != rec[1] && rec[2] != rec[0] && rec[1] != rec[0][/B]  /*second type of conditions*/) { 
			    				Set<String> visited1 = new HashSet<String>();
			    				Set<String> visited2 = new HashSet<String>();
			    				for(int a = 0; a < num*2; a++) {
			    					if(a < num)
			    						visited1.add(m.get(rec[a]));
			    					else
			    						visited2.add(m.get(rec[a]));
			    				}
			    				
			    				if(!((blue.contains(visited1) && red.contains(visited2)) || (blue.contains(visited2) && red.contains(visited1)))) {	
		    						blue.add(visited1);
		    						red.add(visited2);
				    			}
			    			}
		    			}
		    		}
		    	}
	    	}
                //just for the output
	    	for(int a = 0; a < blue.size(); a++) 
	    		System.out.println(blue.get(a)+ " - " + red.get(a));
    	}
        //...
    }

My problem is, mainly, how to get this to work in recursive way, because i need this to work with any inputed number - which means, i need a recursive method, in which each call adds two more for loops and corresponding conditions for them. And theres where the other problem occures, which is connected with its recursive implementation - as you can see, for set size 1, the only condition for for loops is stated in the second for loop condition place, whereas, in the case of set size 2, i wasnt able to do that, so i stated all of the for loops conditions in the first if statement of the most inner loop. So, how could i get them into each corresponding loops condition place? I have two different "types", if i may say so, of conditions, first of which is written in underlined, and second in bold way.

Ty for help!

[JosAH]

Hi all,
im working with undirected unweighted graph, and want to get all of the combinations of two sets, where user inputs the number of verticies for each set, and each vertex of one set must not have any edge connected to any vertex of an other set.

First construct the sets of connected vertices (see below); Name those sets S1, S2, S3 ... Sn. If is easy to construct two sets out of those sets. Constructing a set S of connecting vertices is done as follows:

1) Let S be S-temp | S-perm (two disjoint empty subsets)
2) add any vertex to S-temp
3) for any vertex v in S-temp, move it to S-perm
4) for any vertex vc with an edge connecting to v and not in S already, add it to S-temp
5) go to step 3

If step 3) fails you're ready with S1 and if there are any remaining vertices is the graph start over and construct a new set. (set S2 and again if needed for S3 etc.)

kind regards,

Jos

[Claymz]

Im sorry, i dont completely understand your explanation, could you type it in pseudo code or something? Because im quite tired of trying different tactics and would appreciate such a favor, and am quite short on time and want to move on, if its not too much of course!

[JosAH]

Im sorry, i dont completely understand your explanation, could you type it in pseudo code or something?

I already gave you the pseudo code for the algorithm; it constructs a set of connected vertices.

kind regards,

Jos

[Claymz]

But what does the set contain? Only such a number of verticies that i need in some case (if num is 2 then 2 and so one), or all of the possible "paths" between them, and then i just need to get ones with the specified number of verticies in it?

[JosAH]

But what does the set contain? Only such a number of verticies that i need in some case (if num is 2 then 2 and so one), or all of the possible "paths" between them, and then i just need to get ones with the specified number of verticies in it?

The set(s) you have to construct contain vertices only; all the other information can be found in the original graph. Try to exercise the algorithm by hand (and a piece of paper and a pencil) and see how it works.

kind regards,

Jos

[Claymz]

Here are all the verticies and corresponding connected(neighbour) verticies for each of them. Let me remind you that the graph is conncted. I made picture to show just how it looks:

D: [B, C]
E: [F]
F: [C, A, E]
A: [B, F]
B: [A, D]
C: [D, F]



So, for this example, how would i do it?


For num = 1 i need to get the following:
[E] - [D]
[F] - [D]
[A] - [D]
[A] - [E]
[B] - [E]
[B] - [F]
[C] - [E]
[C] - [A]
[C] - [B]

and for num = 2:
[D, B] - [E, F]
[D, C] - [E, A]
[E, C] - [A, B]

I got this working with the code above, but need a recursive way, or, i need to make it like you suggested, but i dont understand your explanation, as stated before.

Ty!

[JosAH]

Hold on for a second; I think my algorithm solves an entirely different question. This was your original question:

each vertex of one set must not have any edge connected to any vertex of an other set.

Do you mean a direct edge? e.g. if vertex a is in set A and vertex b is in set B then no edge exists a <---> b. Right? No matter if a path (with more than one edge exists leading from a to b)?

kind regards,

Jos

[Claymz]

Yes. I need to get two sets out of this graph, which both contain num number of verticies, which can be any vertex on graph. the only restriction is that, verticies of one set must not have any direct edge, which would be connected to vertex of second set. Which means, i need to get two sets of verticies, which both contain num number of any verticies from the graph, but the two sets must not be connected directly (e.g. verticies of one set must not have any direct (edge) connection to verticies of the other set). However, they can be connected indirectly, which means that between each vertex of one set and each vertex of the other set, must be at least one vertex, which seperates them, or no vertex at all. And i need to get all possible combinations of such sets.

Look at the example for num = 2:
[D, B] - [E, F]
[D, C] - [E, A]
[E, C] - [A, B]

For first combination, D and B (all verticies of one set) have no direct connection with E and F (all verticies of the other set). For example, [B, D] - [C, F] would not be an option, as D and C are connected directly.

[JosAH]

If num == n need both sets contain n vertices or would the 'solution' for num == 3: {a, e, f} - {d} be ok?

kind regards,

Jos

[Claymz]

They both need exact same number of verticies, in your case, 3.

[Claymz]

Any ideas?