Get the list of all paths between 2 nodes

Question

Can anyone help me understand what I'm doing wrong in here. I want to get the list of all paths between 2 given nodes in a graph. Any help would be very appriciated.

public class City {
    final private String id;  

      public City(String id) {
        this.id = id;
      }
      public City getCity() {
    return node;
  }
  public int getCost() {
    return cost;
  }
}

public class Route {

    private final City node;
    private final int cost; 

      public Route(City node, int cost) {
        this.node = node;
        this.cost = cost;
      }
}

    public class Graph {

private final List<City> cities;
private final List<Route> routes;
private final Map<City, List<Route>> myGraph = new HashMap<City,List<Route>>();
private Queue<City> visited = new LinkedList<City>();
private Queue<City> beenThere = new LinkedList<City>();

 public Graph(List<City> vertexes, List<Route> edges) {
    this.cities = vertexes;
    this.routes = edges;
  }

  public String toString () {
        StringBuffer s = new StringBuffer();
        for (City c: myGraph.keySet()) 
            System.out.println(c + " -> " + myGraph.get(c));
        System.out.println();
        return s.toString();                
    }

  public void addNew (City vertex) {
        if (myGraph.containsKey(vertex)) 
            return;
        myGraph.put(vertex, new ArrayList<Route>());   
    }

  public void add (City from, City to, int cost) {
        this.addNew(from); 
        this.addNew(to);
        myGraph.get(from).add(new Route(to,cost));
        myGraph.get(to).add(new Route(from,cost));
    }

  public boolean contains (City vertex) {
        return myGraph.containsKey(vertex);
    }

 // public Route returnRoute

  public Queue<City> getNeighbors(City city) {
        Queue<City> neighbors = new LinkedList<City>();
        for (City c : myGraph.keySet()) {
            String c1 = c.toString();
            String city1 = city.toString();
            if (c1.equals(city1)) 
                neighbors.add(myGraph.get(c).get(0).getCity()); 
        }
        return neighbors;
        }

  public Queue<City> checkRoute(City node) {
      Queue<City> neighbors = new LinkedList<City>();
      neighbors = this.getNeighbors(node);
      for (City n : neighbors) 
              if(visited.contains(n))
                  break;
              else
          {
                  visited.add(n);
                  beenThere.add(n);
                  checkRoute(n);
              }

      return beenThere;
  }

  public List<Queue<City>> BFS(Graph graph, City from, City to) {
      List<Queue<City>> rute = new ArrayList<Queue<City>>();
      Queue<City> toVisit = new LinkedList<City>();
      toVisit.add(from);
      beenThere.add(from);
      while(!toVisit.isEmpty()) {
          City node = toVisit.remove();
          visited.add(node);
          Queue<City> neighbors = new LinkedList<City>();
          neighbors = this.getNeighbors(node);
          while(!neighbors.isEmpty()) {
              visited.add(neighbors.element());
              checkRoute(neighbors.remove());
          }
          if (beenThere.poll().equals(to))
              rute.add(beenThere);
          beenThere.clear();
          beenThere.add(from);
          //visited.clear();
      }
      return rute;
    }

    public void ReadFile() throws IOException  {
      String scan;
        FileReader file = new FileReader("C:\\Users\\W7\\workspace\\AI-Lab1\\graph.txt");
        BufferedReader br = new BufferedReader(file);
        while((scan = br.readLine()) != null) {
            String[] numberString =scan.split(" ");
            String from = numberString[0];
            City city1 = new City(from);
            String to = numberString[1];
            City city2 = new City(to);
            int cost = Integer.parseInt(numberString[2]);
            this.add(city1, city2, cost);
        }
        br.close();
  }
    }

the cities are read from a text file graph.txt:

Bucuresti Atena 1700
Bucuresti Budapesta 800
Paris Bucuresti 2000
Madrid Berlin 500
Kiew Moscova 800
Oslo Stokolm 590
Bucuresti Berlin 1500
Budapesta Berlin 500

public class Start {

    private static  List<City> nodes;
    private static List<Route> edges;

    private static void run () throws IOException {
        nodes = new ArrayList<City>();
        edges = new ArrayList<Route>();
        Graph graph = new Graph(nodes, edges); 
        graph.ReadFile();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            System.out.println("Press:");
            System.out.println("[1] VIEW THE GRAPH");
            System.out.println("[2] GET THE SHORTEST PATH");
            try {
                String s = br.readLine();
                if(s.equals("exit"))
                    return;
                int option=Integer.parseInt(s);
                if (option == 1 ) {
                    System.out.println("The graph is:" );
                    System.out.println(graph);
                    //getGraph();
                    System.out.println("========================");
                }
                if (option == 2) {
                    System.out.println("\tGive source vertex : ");
                    String source = br.readLine();
                    City from =  new City(source);
                    System.out.println("\tGive destination vertex : ");
                    String destination = br.readLine();
                    City to = new City(destination);
                    //getShortestPath(graph,source,destination);
                    System.out.println(graph.BFS(graph, from, to));
                    System.out.println("========================");
                }
                if (option == 3) {
                    System.out.println("Please insert city:");
                    String c = br.readLine();
                    City city = new City(c);
                    System.out.println(graph.getNeighbors(city));
                }
            }catch(IOException e) {
                e.printStackTrace();
            }
        } 
      }

      public static void main(String[] args) throws IOException  {
          run();

}
}

This returns an empty list and I don't understand why...

Answer 1

I notice you have:

if (beenThere.poll().equals(to)) {
  rute.add(beenThere);
}

To evaluate equality of one of your own personal Objects, you need to override the hashCode() and equals() methods for that class.

Otherwise, two objects will never be equal unless they are the exact same object in memory. Add these two methods to your City class:

@Override
public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((id == null) ? 0 : id.hashCode());
  return result;
}

@Override
public boolean equals(Object obj) {
  if (this == obj)
return true;
  if (obj == null)
return false;
  if (getClass() != obj.getClass())
return false;
  City other = (City) obj;
  if (id == null) {
if (other.id != null)
  return false;
  } else if (!id.equals(other.id))
return false;
  return true;
}

Another issue is that you are clearing beenThere this also clears the value in your ArrayList since they both refer to the same object in memory. To understand, try playing with the following code where you comment out the clear() method to see the difference.

public static void main(String[] args) {
  List<Queue<Integer>> rute = new ArrayList<Queue<Integer>>();
  Queue<Integer> beenThere = new LinkedList<Integer>();

  beenThere.add(1);
  beenThere.add(2);
  beenThere.add(3);
  rute.add(beenThere);

  beenThere.clear(); // run this code with this commented out to see the difference

  System.out.println(rute.toString());
}

Answer 2

I'm currently too low to comment. But in your Graph class, getNeighbours method you've got a variable called myGraph however I cannot see the declaration anywhere.