Graph Applications

public class NavigationSystem {
    static class Location {
        int id;
        String name;
        double latitude, longitude;
        
        Location(int id, String name, double lat, double lng) {
            this.id = id;
            this.name = name;
            this.latitude = lat;
            this.longitude = lng;
        }
    }
    
    private List<Integer>[] routes;
    private int[][] distances;
    private int V;
    
    public NavigationSystem(int V) {
        this.V = V;
        routes = new ArrayList[V];
        distances = new int[V][V];
        for (int i = 0; i < V; i++) {
            routes[i] = new ArrayList<>();
            for (int j = 0; j < V; j++) {
                distances[i][j] = Integer.MAX_VALUE;
            }
            distances[i][i] = 0;
        }
    }
    
    public void addRoad(int from, int to, int distance) {
        routes[from].add(to);
        routes[to].add(from);
        distances[from][to] = distance;
        distances[to][from] = distance;
    }
    
    // Find shortest route using Dijkstra
    public List<Integer> findRoute(int start, int destination) {
        int[] dist = new int[V];
        int[] parent = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        
        dist[start] = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (a, b) -> Integer.compare(dist[a], dist[b])
        );
        pq.add(start);
        
        while (!pq.isEmpty()) {
            int u = pq.poll();
            
            for (int v : routes[u]) {
                if (dist[u] + distances[u][v] < dist[v]) {
                    dist[v] = dist[u] + distances[u][v];
                    parent[v] = u;
                    pq.add(v);
                }
            }
        }
        
        // Reconstruct path
        List<Integer> path = new ArrayList<>();
        int current = destination;
        while (current != -1) {
            path.add(0, current);
            current = parent[current];
        }
        
        return path;
    }
    
    public static void main(String[] args) {
        NavigationSystem gps = new NavigationSystem(5);
        gps.addRoad(0, 1, 5);
        gps.addRoad(0, 2, 3);
        gps.addRoad(1, 2, 2);
        gps.addRoad(1, 3, 7);
        gps.addRoad(2, 4, 6);
        gps.addRoad(3, 4, 1);
        
        List<Integer> route = gps.findRoute(0, 4);
        System.out.println("Route from 0 to 4: " + route);
    }
}

public class SocialNetwork {
    private List<Integer>[] friends;
    private int V;
    
    public SocialNetwork(int V) {
        this.V = V;
        friends = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            friends[i] = new ArrayList<>();
        }
    }
    
    public void addFriendship(int u, int v) {
        friends[u].add(v);
        friends[v].add(u);
    }
    
    // Find degrees of separation (BFS)
    public int degreeOfSeparation(int person1, int person2) {
        Queue<Integer> q = new LinkedList<>();
        int[] distance = new int[V];
        Arrays.fill(distance, -1);
        
        q.add(person1);
        distance[person1] = 0;
        
        while (!q.isEmpty()) {
            int current = q.remove();
            
            if (current == person2) {
                return distance[current];
            }
            
            for (int friend : friends[current]) {
                if (distance[friend] == -1) {
                    distance[friend] = distance[current] + 1;
                    q.add(friend);
                }
            }
        }
        
        return -1;  // Not connected
    }
    
    // Find all friends (1st degree connections)
    public List<Integer> getDirectFriends(int person) {
        return friends[person];
    }
    
    // Find all friends of friends (2nd degree connections)
    public Set<Integer> getSecondDegreeFriends(int person) {
        Set<Integer> secondDegree = new HashSet<>();
        
        for (int friend : friends[person]) {
            for (int foaf : friends[friend]) {
                if (foaf != person && !friends[person].contains(foaf)) {
                    secondDegree.add(foaf);
                }
            }
        }
        
        return secondDegree;
    }
    
    // Get user's network size (BFS)
    public int getNetworkSize(int person) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[V];
        int size = 0;
        
        q.add(person);
        visited[person] = true;
        
        while (!q.isEmpty()) {
            int current = q.remove();
            size++;
            
            for (int friend : friends[current]) {
                if (!visited[friend]) {
                    visited[friend] = true;
                    q.add(friend);
                }
            }
        }
        
        return size;
    }
    
    public static void main(String[] args) {
        SocialNetwork network = new SocialNetwork(6);
        network.addFriendship(0, 1);
        network.addFriendship(0, 2);
        network.addFriendship(1, 3);
        network.addFriendship(3, 4);
        network.addFriendship(4, 5);
        
        System.out.println("Degrees of separation 0→5: " + 
                          network.degreeOfSeparation(0, 5));  // 3
        System.out.println("Direct friends of 0: " + 
                          network.getDirectFriends(0));
    }
}

public class RecommendationEngine {
    static class Movie {
        int id;
        String title;
        List<Integer> viewers;
        
        Movie(int id, String title) {
            this.id = id;
            this.title = title;
            this.viewers = new ArrayList<>();
        }
    }
    
    private Movie[] movies;
    private int[][] similarity;
    
    public RecommendationEngine(int movieCount) {
        movies = new Movie[movieCount];
        similarity = new int[movieCount][movieCount];
    }
    
    public void addMovie(int id, String title) {
        movies[id] = new Movie(id, title);
    }
    
    public void userWatched(int userId, int movieId) {
        movies[movieId].viewers.add(userId);
    }
    
    // Calculate similarity between movies
    public void calculateSimilarity() {
        int n = movies.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Count common viewers (co-occurrence)
                Set<Integer> movie1Viewers = new HashSet<>(movies[i].viewers);
                movie1Viewers.retainAll(movies[j].viewers);
                
                int commonViewers = movie1Viewers.size();
                similarity[i][j] = commonViewers;
                similarity[j][i] = commonViewers;
            }
        }
    }
    
    // Recommend movies based on watched movies
    public List<Integer> recommend(int userId, int count) {
        // Find all movies watched by user
        Set<Integer> watchedMovies = new HashSet<>();
        for (int i = 0; i < movies.length; i++) {
            if (movies[i].viewers.contains(userId)) {
                watchedMovies.add(i);
            }
        }
        
        // Find similar movies with scores
        Map<Integer, Integer> scores = new HashMap<>();
        for (int watched : watchedMovies) {
            for (int i = 0; i < movies.length; i++) {
                if (!watchedMovies.contains(i)) {
                    scores.put(i, scores.getOrDefault(i, 0) + similarity[watched][i]);
                }
            }
        }
        
        // Return top recommendations
        return scores.entrySet().stream()
            .sorted((a, b) -> Integer.compare(b.getValue(), a.getValue()))
            .limit(count)
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());
    }
}

public class PageRank {
    private List<Integer>[] outlinks;
    private int V;
    
    public PageRank(int V) {
        this.V = V;
        outlinks = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            outlinks[i] = new ArrayList<>();
        }
    }
    
    public void addLink(int from, int to) {
        outlinks[from].add(to);
    }
    
    // Calculate PageRank
    public double[] calculatePageRank(int iterations) {
        double[] rank = new double[V];
        double[] newRank = new double[V];
        double damping = 0.85;
        double initialRank = 1.0 / V;
        
        // Initialize all ranks
        for (int i = 0; i < V; i++) {
            rank[i] = initialRank;
        }
        
        // Iteratively calculate ranks
        for (int iter = 0; iter < iterations; iter++) {
            for (int i = 0; i < V; i++) {
                newRank[i] = (1 - damping) / V;
            }
            
            // For each page with outlinks
            for (int from = 0; from < V; from++) {
                if (!outlinks[from].isEmpty()) {
                    double contribution = rank[from] / outlinks[from].size();
                    
                    for (int to : outlinks[from]) {
                        newRank[to] += damping * contribution;
                    }
                }
            }
            
            // Swap arrays
            double[] temp = rank;
            rank = newRank;
            newRank = temp;
        }
        
        return rank;
    }
}