Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 19 of 19

Thread: Euler Paths with dfs algorithm problem

  1. March 22nd, 2012, 05:59 AM #1
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Euler Paths with dfs algorithm problem

    Hi everyone, it's my first time here

    I'm implementing an algorithm to find all the euler paths in a graph. I'm basing myself, to create the dfs, in the code found here: algorithm - Find all possible Euler cycles - Stack Overflow

    Here is my current code:

    public class Graph {
 
	private int numVertex;
	private int numEdges;
	private boolean[][] adj;
 
	public Graph(int numVertex, int numEdges) {
		this.numVertex = numVertex;
		this.numEdges = numEdges;
		this.adj = new boolean[numVertex+1][numVertex+1];
	}
 
	public void addEdge(int start, int end){
		adj[start][end] = true;
		adj[end][start] = true;
	}
 
	List<Integer> visited = new ArrayList<Integer>();
 
	public Integer DFS(Graph G, int startVertex){
		int i=0;
		pilha.push(startVertex);
		for(i=0; i<G.numVertex; i++){
 
			if(G.adj[i][startVertex] != false){
				System.out.println("i: " + i);
				G.adj[i][startVertex] = false;
				G.adj[startVertex][i] = false;
 
				int c = pilha.pop();
 
				visited.add(c);
				System.out.println("visited: " + visited);
 
				DFS(G, i);
 
				G.adj[i][startVertex] = true;
				G.adj[startVertex][i] = true;
			}
 
		}
		return -1;
	}
 
	Stack<Integer> pilha = new Stack();
 
	public static void main(String[] args) {
 
        Scanner input = new Scanner(System.in);
 
        int numVertices = input.nextInt();
        int numLinks = input.nextInt();
        int startNode = input.nextInt();
 
        Graph g = new Graph(numVertices, numLinks);
 
        for(int i = 0; i<numLinks; i++){
            g.addEdge(input.nextInt(),input.nextInt());
        }
 
        g.DFS(g, startNode);
	}
}

    Unfortunately i don't get the right results and i can't seem to figure out why. I've tried a lot of thing as storing the results from the dfs in a list and print them, but still i got no paths.

    any idea on how can i modify my code so i start getting the euler paths?
    Last edited by claudio.r; March 22nd, 2012 at 07:17 AM. Reason: Cleaned up the code a bit
    Reply With Quote Reply With Quote

  2. Default Related threads:

  3. March 22nd, 2012, 09:01 AM #2
    andreas90
    andreas90 is offline
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Quote Originally Posted by claudio.r View Post
    Unfortunately i don't get the right results and i can't seem to figure out why. I've tried a lot of thing as storing the results from the dfs in a list and print them, but still i got no paths.

    any idea on how can i modify my code so i start getting the euler paths?
    I think the problem is in your main() method but can you specify what's the expected and your current result?
    Reply With Quote Reply With Quote
  4. March 22nd, 2012, 09:29 AM #3
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    For testing can you make a main method that loads the Graph from the program without any user input required. That way everyone will be working with the same graph and testing will be faster without requiring user input.
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  5. March 22nd, 2012, 11:36 AM #4
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Here os the code with the main loading a graph. Currently it only makes a DFS search, i want to modify it to at least make some backtracking based on the edges it already visited. My main goal is to solve the euler path problem.

    public class Graph {
 
	private int numVertex;
	private int numEdges;
	private boolean[][] adj;
 
	public Graph(int numVertex, int numEdges) {
		this.numVertex = numVertex;
		this.numEdges = numEdges;
		this.adj = new boolean[numVertex+1][numVertex+1];
	}
 
	public void addEdge(int start, int end){
		adj[start][end] = true;
		adj[end][start] = true;
	}
 
	List<Integer> visited = new ArrayList<Integer>();
 
	public Integer DFS(Graph G, int startVertex){
		int i=0;
		pilha.push(startVertex);
		boolean hasAdjacent = false;
		for(i=0; i<G.numVertex; i++){
 
			if(G.adj[i][startVertex] != false){
				hasAdjacent = true;
				System.out.println("i: " + i);
				G.adj[i][startVertex] = false;
				G.adj[startVertex][i] = false;
 
				DFS(G, i);
				pilha.push(i);
 
				G.adj[i][startVertex] = true;
				G.adj[startVertex][i] = true;
			}
 
/*			else{
				pilha.pop();
			}*/
 
			if(!pilha.isEmpty()){
			int c = pilha.pop();
 
			visited.add(c);
			System.out.println("visited: " + visited);
			}
 
		}
		return -1;
	}
 
	Stack<Integer> pilha = new Stack();
 
	public static void main(String[] args) {
 
		Graph g = new Graph(6, 9);
 
        g.addEdge(1, 2);
        g.addEdge(1, 5);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);
        g.addEdge(6, 4);
 
        g.DFS(g, 1);
	}
}
    Reply With Quote Reply With Quote
  6. March 22nd, 2012, 12:09 PM #5
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Quote Originally Posted by claudio.r View Post
    Here os the code with the main loading a graph. Currently it only makes a DFS search, i want to modify it to at least make some backtracking based on the edges it already visited. My main goal is to solve the euler path problem.

    public class Graph {
 
	private int numVertex;
	private int numEdges;
	private boolean[][] adj;
 
	public Graph(int numVertex, int numEdges) {
		this.numVertex = numVertex;
		this.numEdges = numEdges;
		this.adj = new boolean[numVertex+1][numVertex+1];
	}
 
	public void addEdge(int start, int end){
		adj[start][end] = true;
		adj[end][start] = true;
	}
 
	List<Integer> visited = new ArrayList<Integer>();
 
	public Integer DFS(Graph G, int startVertex){
		int i=0;
		pilha.push(startVertex);
		boolean hasAdjacent = false;
		for(i=0; i<G.numVertex; i++){
 
			if(G.adj[i][startVertex] != false){
				hasAdjacent = true;
				System.out.println("i: " + i);
				G.adj[i][startVertex] = false;
				G.adj[startVertex][i] = false;
 
				DFS(G, i);
				pilha.push(i);
 
				G.adj[i][startVertex] = true;
				G.adj[startVertex][i] = true;
			}
 
/*			else{
				pilha.pop();
			}*/
 
			if(!pilha.isEmpty()){
			int c = pilha.pop();
 
			visited.add(c);
			System.out.println("visited: " + visited);
			}
 
		}
		return -1;
	}
 
	Stack<Integer> pilha = new Stack();
 
	public static void main(String[] args) {
 
		Graph g = new Graph(6, 9);
 
        g.addEdge(1, 2);
        g.addEdge(1, 5);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);
        g.addEdge(6, 4);
 
        g.DFS(g, 1);
	}
}
    What does the program do now? Can you post its output and explain what is wrong with the output and show what the output should be?
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  7. March 22nd, 2012, 12:19 PM #6
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Right now, the program outputs the result of a dfs search on the graph:

    visited: [1]
i: 2
visited: [1, 2]
i: 4
visited: [1, 2, 4]
i: 3
visited: [1, 2, 4, 3]
i: 5
visited: [1, 2, 4, 3, 5]
i: 1
visited: [1, 2, 4, 3, 5, 1]
visited: [1, 2, 4, 3, 5, 1, 1]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2]
i: 3
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3]
i: 5
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5]
i: 2
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2]
i: 1
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1]
i: 4
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5, 3]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5, 3, 4]
visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5, 3, 4, 5]

    What i want is to have an euler path, where the program visits each one of the graph edges only once. So, in this particular example the correct output should be all the euler path on the graph such as:

    1 2 4 3 5 2 6 4 5 1

    To achieve this i think the first step should be, add backtracking to my DFS search, but i'm having trouble with that.
    Reply With Quote Reply With Quote
  8. March 22nd, 2012, 12:21 PM #7
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Is this an algorithm question
    or do you have the algorithm and want help coding it in java?
    I might be able to help with the second one.
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  9. March 22nd, 2012, 12:28 PM #8
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    I have the algorithm, i need helping with the java part.

    This is what i'm trying to achieve:
    Euler tour - Algorithmist

    right now i have an adjacency matrix, that is populated with the all the graph adjacencys. I'm performing DFS search on the graph, it runs through the graph choosing the first edge it finds in the adjacency list.
    What i wnat right now, is to limit the edges he chooses, in a way that he only visits edges he has no visited before.
    Reply With Quote Reply With Quote
  10. March 22nd, 2012, 12:33 PM #9
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    i need helping with the java part.
    What are your java programming questions?
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  11. March 22nd, 2012, 12:46 PM #10
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Right now, i'm trying to use a stack strucuture to remove a node from the list, but everytime i try to use pop() i get exceptions.

    This is my current code:

    public class Graph {
 
	private int numVertex;
	private int numEdges;
	private boolean[][] adj;
 
	public Graph(int numVertex, int numEdges) {
		this.numVertex = numVertex;
		this.numEdges = numEdges;
		this.adj = new boolean[numVertex+1][numVertex+1];
	}
 
	public void addEdge(int start, int end){
		adj[start][end] = true;
		adj[end][start] = true;
	}
 
	List<Integer> visited = new ArrayList<Integer>();
 
	public Integer DFS(Graph G, int startVertex){
		int i=0;
		pilha.push(startVertex);
		boolean hasAdjacent = false;
		for(i=0; i<G.numVertex; i++){
 
			if(G.adj[i][startVertex] != false){
				hasAdjacent = true;
				System.out.println("i: " + i);
				G.adj[i][startVertex] = false;
				G.adj[startVertex][i] = false;
 
				pilha.push(i);
				DFS(G, i);
			}
 
			else{
				hasAdjacent=false;
			}
		}
 
		//System.out.println("Conteudo da pilha: " + pilha);
 
		if(!hasAdjacent){
			pilha.pop();
			DFS(G, pilha.firstElement());
 
		}
		return -1;
	}
 
	Stack<Integer> pilha = new Stack();
 
	public static void main(String[] args) {
 
		Graph g = new Graph(6, 9);
 
        g.addEdge(1, 2);
        g.addEdge(1, 5);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);
        g.addEdge(6, 4);
 
        g.DFS(g, 1);	
 
	}
}
    Reply With Quote Reply With Quote
  12. March 22nd, 2012, 12:51 PM #11
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Can you post the full text of the error message.
    One reason you get an exception is if the stack is empty.
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  13. March 22nd, 2012, 12:58 PM #12
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Here's the full error message:

    java.lang.StackOverflowError
	at java.util.Vector.ensureCapacityHelper(Unknown Source)
	at java.util.Vector.addElement(Unknown Source)
	at java.util.Stack.push(Unknown Source)
	at Graph.DFS(Graph.java:28)
	at Graph.DFS(Graph.java:65)
	at Graph.DFS(Graph.java:65)
	at Graph.DFS(Graph.java:65)

    I had errors because of empty stack too. I'm having trouble with the stack operations.

    If you read python, what i'm trying to do is something like this: Finding Eulerian path in undirected graph Python recipes ActiveState Code

    Only with diferent syntax and inputs.
    Reply With Quote Reply With Quote
  14. March 22nd, 2012, 01:02 PM #13
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Looks like an infinite loop.

    Try debugging by adding some printlns to show the values that are being used to see why it is not stopping.
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  15. March 22nd, 2012, 03:12 PM #14
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Right now i can find the simple euler paths. But when the algorithm needs to backtrack i have a problem.

    this is my current code:

    public class Graph {
 
	private int numVertex;
	private int numEdges;
	private boolean[][] adj;
 
	public Graph(int numVertex, int numEdges) {
		this.numVertex = numVertex;
		this.numEdges = numEdges;
		this.adj = new boolean[numVertex][numVertex];
	}
 
	public void addEdge(int start, int end){
		adj[start-1][end-1] = true;
		adj[end-1][start-1] = true;
	}
 
	List<Integer> visited = new ArrayList<Integer>();
 
	public Integer DFS(Graph G, int startVertex){
		int i=0;
 
		if(pilha.isEmpty())
			pilha.push(startVertex);
 
		for(i=1; i<G.numVertex; i++){
			pilha.push(i);
			if(G.adj[i-1][startVertex-1] != false){
				G.adj[i-1][startVertex-1] = false;
				G.adj[startVertex-1][i-1] = false;
				 DFS(G,i);
				 break;
			}else{
			visited.add(pilha.pop());
			}
			System.out.println("Stack: " + pilha);
		}
		return -1;
	}
 
		Stack<Integer> pilha = new Stack();
 
	public static void main(String[] args) {
 
		Graph g = new Graph(6, 9);
 
        g.addEdge(1, 2);
        g.addEdge(1, 5);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);
        g.addEdge(6, 4);
 
        g.DFS(g, 1);	
 
	}
}

    If you execute the code, it stops in 1, when in reality, it should backtrack to 5 and select the edge to 2. Any ideia on how to solve this problem? I think the issue is in the stack operations... but i really don't know.
    Reply With Quote Reply With Quote
  16. March 22nd, 2012, 03:25 PM #15
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Read the code's comments does not tell me anything about what the code is trying to do.
    Where does it "stop" or "backtrack"?
    "stops in 1" and "backtrack to 5" have no meaning
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  17. March 22nd, 2012, 04:19 PM #16
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    The code output should be 1 2 4 3 5 2 6 4 5 1 that represent the order in the graph that the nodes are visited. The out put of the program is 1 2 4 3 5 1 2 6 4 5, which means that he is visiting an edge it already visited "1 2". What i wanted to happen is that when it finds out that he is going to an edge he already visited, the program backtracks to the node after, and visit a different edge instead.
    Reply With Quote Reply With Quote
  18. March 22nd, 2012, 04:24 PM #17
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    Where in the code does it detect that it has visited an edge?
    Where does the code backtrack to a node?
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
  19. March 22nd, 2012, 04:34 PM #18
    claudio.r
    claudio.r is offline
    Junior Member
    Join Date
    Mar 2012
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Euler Paths with dfs algorithm problem

    It is supposed to backtrack in the pop() instruction, and after we visit an edge, i delete that edge from the matrix. The problem, is that when the program goes to a dead end, it does not backtrack, which means i'm doing something wrong in the code...
    Reply With Quote Reply With Quote
  20. March 22nd, 2012, 04:39 PM #19
    Norm
    Norm is offline
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Euler Paths with dfs algorithm problem

    The only way I know to find logic problems is to debug the code while it is running. If you don't have an interactive debugger, use lots of println statements to show variables' values and execution flow.
    If you don't understand my answer, don't ignore it, ask a question.
    Reply With Quote Reply With Quote
« Stack implementation and shallow copy | Creating a TreeModel from SQL Data »

Similar Threads

  1. [SOLVED] Project Euler: Truncatable Primes
    By Staticity in forum What's Wrong With My Code?
    Replies: 7
    Last Post: October 10th, 2011, 12:27 PM
  2. I have algorithm problem
    By Newoor in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 11th, 2009, 08:11 PM
  3. Euler integration
    By Kakashi in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 2nd, 2009, 04:19 PM
  4. Project Euler
    By helloworld922 in forum The Cafe
    Replies: 5
    Last Post: September 9th, 2009, 02:51 PM
  5. Probelm in Path and Paths Classes
    By neo_2010 in forum File I/O & Other I/O Streams
    Replies: 4
    Last Post: July 14th, 2009, 10:39 AM