Pathfinding using DFS and java

Question

I'm developing a search algorithm for finding paths in a graph. In this algorithm i need to find all the paths in an undirected, not weighted graph that go trough each graph connection only once. It must start and end in the same node. Currently, what my program is doing, is finding all the paths that go trough each node only once. I need connections and not nodes.

Here is my code:

import java.util.*;

public class dfs {  

    private static Map<Integer, LinkedHashSet<Integer>> map = new HashMap<Integer, LinkedHashSet<Integer>>();
    private int startNode;
    private int numLinks;

    public dfs(int startNode, int numLinks) {
        super();
        this.startNode = startNode;
        this.numLinks = numLinks;
    }

    public int getNumLinks(){
        return numLinks;    
    }

    public void addEdge(int source, int destiny) {
        LinkedHashSet<Integer> adjacente = map.get(source);
        if(adjacente==null) {
            adjacente = new LinkedHashSet<Integer>();
            map.put(source, adjacente);
        }
        adjacente.add(destiny);
    }

    public void addLink(int source, int destiny) {
        addEdge(source, destiny);
        addEdge(destiny, source);
    }

    public LinkedList<Integer> adjacentNodes(int adj) {
        LinkedHashSet<Integer> adjacente = map.get(adj);
        System.out.println("adjacentes:" + adjacente);
        if(adjacente==null) {
            return new LinkedList<Integer>();
        }
        return new LinkedList<Integer>(adjacente);
    }


public static void main(String[] args) {

    Scanner input = new Scanner(System.in);

    int numVertices = input.nextInt();
    int numLinks = input.nextInt();
    int startNode = input.nextInt();
    int endNode = startNode;

    dfs mapa = new dfs(startNode, numLinks);

    for(int i = 0; i<numLinks; i++){
        int inicio = input.nextInt();
        int fim = input.nextInt();
        mapa.addLink(inicio, fim);

    }

    List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
    List<Integer> visited = new ArrayList<Integer>();
    visited.add(startNode);
    Integer currentNode = 0;

    Iterator it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pairs = (Map.Entry)it.next();
        currentNode = (Integer) pairs.getKey(); 

        mapa.findAllPaths(mapa, visited, paths, currentNode);

    }
}

private void findAllPaths(dfs mapa, List<Integer> visited,
        List<ArrayList<Integer>> paths, Integer currentNode) {

    if (currentNode.equals(startNode)) { 
        paths.add(new ArrayList<Integer>(visited));

        LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode); 

        for (Integer node : nodes) {

            List<Integer> temp = new ArrayList<Integer>();
            temp.addAll(visited);
            temp.add(node);  
            System.out.println("temp:" + temp);

            findAllPaths(mapa, temp, paths, node);
        }   
    }
    else {
        LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);  
        System.out.println("currentNode:" + currentNode);

        List<Integer> inseridos = new ArrayList<Integer>();

        for (Integer node : nodes) {   
            if (visited.contains(node)) {
                continue;
            } 
            List<Integer> temp = new ArrayList<Integer>();
            inseridos.add(currentNode);
            temp.addAll(visited);
            System.out.println("visited:" + visited);

            temp.add(node);

            findAllPaths(mapa, temp, paths, node);
        }
    }
} 
}

The program receives integers on his input. The first one is the number of nodes, the second one is the number of links and the third is the start node and end note, which are the same. All the integers that come after represent the connections between nodes.

As an example: the program receives "1 2 3 3 4 5 6" 1 is the number of nodes, 2 is the number of links, 3 is the starting node, 3 4 is a connection from node 3 to node 4 and 5 6 is a connection from node 5 to 6.

Right now, i think the following code:

if (visited.contains(node)) {
 continue;
}

is making that the program not going through each node more than once. I need help transforming my program to go trough each connection only once, and not through each node once.

Any ideas on how i can do this?

Answer 1

I'm assuming that you mean Edge instead of Connection. This way, what you want is to find all cycles (paths that start and end in the same node) that contain all edges.

A cycle passing through every single edge once is known as an Euler Path. You can see a solution here.