1. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## Recursion with loops

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:

Java Code:
```    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; rec < vertEdge.size(); rec++) {
for(rec = 0; rec < vertEdge.size() && [B]rec != rec[/B]; rec++) {
if([I]!vertEdge.get(m.get(rec)).contains(m.get(rec))[/I]) {
Set<String> visited1 = new HashSet<String>();
Set<String> visited2 = new HashSet<String>();
for(int a = 0; a < num*2; a++) {
if(a < num)
else
}

if(!((blue.contains(visited1) && red.contains(visited2)) || (blue.contains(visited2) && red.contains(visited1)))) {
}
}
}
}
//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; rec < vertEdge.size(); rec++) {
for(rec = 0; rec < vertEdge.size(); rec++) {
for(rec = 0; rec < vertEdge.size(); rec++) {
for(rec = 0; rec < vertEdge.size(); rec++) {
if([I]!vertEdge.get(m.get(rec)).contains(m.get(rec)) && !vertEdge.get(m.get(rec)).contains(m.get(rec))&& !vertEdge.get(m.get(rec)).contains(m.get(rec)) && !vertEdge.get(m.get(rec)).contains(m.get(rec))[/I] /*one type of conditions*/ && [B]rec != rec && rec != rec && rec != rec && rec != rec && rec != rec && rec != rec[/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)
else
}

if(!((blue.contains(visited1) && red.contains(visited2)) || (blue.contains(visited2) && red.contains(visited1)))) {
}
}
}
}
}
}
//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!
Last edited by Claymz; 05-31-2011 at 01:16 PM.  Reply With Quote

2. ##  Originally Posted by 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.
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  Reply With Quote

3. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## 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!  Reply With Quote

4. ##  Originally Posted by Claymz 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  Reply With Quote

5. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## 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?  Reply With Quote

6. ##  Originally Posted by 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?
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  Reply With Quote

7. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## 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!
Last edited by Claymz; 05-31-2011 at 01:49 PM.  Reply With Quote

8. ## 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  Reply With Quote

9. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## 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.
Last edited by Claymz; 05-31-2011 at 03:25 PM.  Reply With Quote

10. ## 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  Reply With Quote

11. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## They both need exact same number of verticies, in your case, 3.  Reply With Quote

12. Member Join Date
Apr 2011
Posts
25
Rep Power
0

## Any ideas?   Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•