Daily Archives: January 9, 2015

This is problem is from careerup link:

You have an vector like this
[JFK, LXA, SNA, RKJ, LXA, SNA]
each 2 group define a route. so,
JFK -> LXA
SNA -> RKJ
LXA -> SNA
Find the path from departure to destination. note: departure and destination are not known.
The final destination should be
JFK-> LXA -> SNA -> RKJ

In mycode, I use DFS for topological sorting. The advantage of it is that it won’t require the in-degree information, compared to BFS. Besides, I constructed the graph by using HashMap < String, AirNode > outgoing , instead of using self-defined graph class, which make the code easier.

1. import java.util.HashMap;
2. import java.util.HashSet;
3. import java.util.Map;
4. import java.util.Set;
5. import java.util.Vector;
6. public class TopogicalSorintDFS {
7.     public static void main(String[] args) {
8.         Vector airports = new Vector();
9.         airports.add(“JFK”);
10.         airports.add(“LAX”);
11.         airports.add(“SNA”);
12.         airports.add(“RKJ”);
13.         airports.add(“LAX”);
14.         airports.add(“SNA”);
15.         Vector result = findPath(airports);
16.         System.out.println(result.toString());
17.     }
18.     public static Vector findPath(Vector airports) {
19.         Map nodes = new HashMap();
20.         // construct graph
21.         for (int i = 0; i < airports.size(); i += 2) {
22.             String from = airports.get(i);
23.             String to = airports.get(i + 1);
24.             if (!nodes.containsKey(from)) {
25.                 nodes.put(from, new AirNode(from));
26.             }
27.             if (!nodes.containsKey(to)) {
28.                 nodes.put(to, new AirNode(to));
29.             }
30.             nodes.get(from).outgoing.add(nodes.get(to));
31.         }
32.         Vector result = new Vector();
33.         HashSet visited = new HashSet();
34.         //start the dfs on graph
35.         for (AirNode node : nodes.values()) {
36.             dfs(node, visited, result);
37.         }
38.         return result;
39.     }
40.     public static void dfs(AirNode node, HashSet visited,
41.             Vector result) {
42.         if (visited.contains(node.airport)) {
43.             return;
44.         }
45.         visited.add(node.airport);
46.         for (AirNode curr : node.outgoing) {
47.             dfs(curr, visited, result);
48.         }
49.         result.insertElementAt(node.airport, 0);
50.     }
51. }
52. class AirNode {
53.     String airport;
54.     Set outgoing;
55.     public AirNode(String airport) {
56.         this.airport = airport;
57.         outgoing = new HashSet();
58.     }
59.     public boolean equals(Object obj) {
60.         if (obj == null) {
61.             return false;
62.         }
63.         if (this == obj) {
64.             return true;
65.         }
66.         if (obj instanceof AirNode) {
67.             AirNode node = (AirNode) obj;
68.             return this.airport.equals(node.airport);
69.         }
70.         return false;
71.     }
72.     public int hashCode() {
73.         return this.airport.hashCode();
74.     }
75. }