01204212/friends

This part of 01204212

In this task you will work with graphs from real social networks.

• facebook.in -- This is a graph from facebook. It is an undirected graph. The graph is from [1]. It has 4,039 vertices and 88,234 edges.
• twitter.in -- This is a graph from twitter. It is a directed graph. This graph is from [2]. It has 81,306 vertices and 1,768,149 edges.

The graph format:

• First line: two integers n and m, where n is the number of vertices and m is the number of edges
• Next m lines: each line contains two integers u and v (ranging from 0 to n-1). In an undirected graph, this means that there is an edge between u and v. In a directed graph, this means that there is an edge from u to v.

Tasks 1

For an undirected graph, find the vertices with the highest degree. For a directed graph (twitter), find vertices with the highest in-degree and vertices with highest out-degree.

Tasks 2

Consider vertex 0 and vertex n-1. Find the length of the shortest path from vertex 0 to vertex n-1.

Tasks 3

In twitter graph, find out how many vertices that are reachable from vertex 0 but vertex 0 cannot be reachable from them.

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        
        main.process();
    }
    
    int n,m;
    List<Integer> [] adjList;
    
    void process() {
        readInput();
    }

    private void readInput() {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        try {
            String[] items = reader.readLine().split(" ");

            n = Integer.parseInt(items[0]);
            m = Integer.parseInt(items[1]);

            adjList = (List<Integer>[])(new List[n]);
            for(int i=0; i<n; i++) {
                adjList[i] = new ArrayList<Integer>();
            }
            
            for(int i=0; i<m; i++) {
                items = reader.readLine().split(" ");
                int u = Integer.parseInt(items[0]);
                int v = Integer.parseInt(items[1]);
                
                adjList[u].add(v);
                adjList[v].add(u);
            }
        } catch(Exception e) {
        }
    }
}

findLevels

	void findLevels(int s) {
		List<Integer> nextLevel = new ArrayList<Integer>();
		levels = new int[n];
		for(int u=0; u<n; u++) {
			levels[u] = -1;
		}
		levels[s] = 0;
		nextLevel.add(s);
		
		while(! nextLevel.isEmpty()) {
			List<Integer> currentLevel = nextLevel;
			nextLevel = new ArrayList<Integer>();

			for(int u : currentLevel) {
				for(int v : adjList[u]) {
					if(levels[v] == -1) {
						levels[v] = levels[u] + 1;
						nextLevel.add(v);
					}
				}
			}
		}
	}