Results 1 to 12 of 12
  1. #1
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Question 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] = 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!
    Last edited by Claymz; 05-31-2011 at 12:16 PM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Claymz View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

    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!

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Claymz View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

    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?

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Claymz View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

    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 12:49 PM.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

    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 02:25 PM.

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

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

  12. #12
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

Similar Threads

  1. N while loops into recursion
    By Claymz in forum New To Java
    Replies: 1
    Last Post: 04-17-2011, 03:05 PM
  2. Replies: 20
    Last Post: 03-22-2011, 04:02 AM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  4. Recursion
    By kathyla18 in forum New To Java
    Replies: 2
    Last Post: 04-09-2009, 02:26 AM
  5. help with recursion
    By Nari in forum New To Java
    Replies: 15
    Last Post: 04-24-2008, 09:13 AM

Posting Permissions

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