Graphs Workshop

What is a Graph?

Imagine a map where cities are represented as points (vertices) and roads connecting these cities are represented as lines (edges). A graph is a similar concept, but more generalized. A graph consists of points (vertices) and the connections between these points (edges).

Basic Terminology

• Vertex (Node): An element in the graph. For example, a city, a person, or a webpage.
• Edge (Link): A connection between two vertices. For example, a road between two cities, a friendship between two people, or a link between two web pages.
• Neighbors: Two vertices are neighbors if they are connected by an edge.
• Degree: The number of edges connected to a vertex.
• Path: A sequence of vertices where each consecutive pair is connected by an edge.
• Cycle: A path that starts and ends at the same vertex.
• Connected Component: A subset of vertices where every vertex is reachable from every other vertex in that subset.

Types of Graphs

1. Directed Graph (Digraph): Edges have a direction (e.g., a one-way street, a follower relationship on social media).

   • Each edge goes from one vertex to another
   • If there's an edge from A to B, it doesn't mean there's an edge from B to A

2. Undirected Graph: Edges have no direction (e.g., a friendship, a road that can be traveled both ways).

   • Each edge connects two vertices bidirectionally
   • If A is connected to B, then B is also connected to A

3. Weighted Graph: Numbers (weights) are assigned to edges (e.g., the length of a road, the cost of a flight).

   • Useful for optimization problems like finding the shortest or cheapest path

4. Unweighted Graph: All edges are considered equal.

Graph Representations

There are two common ways to represent a graph in code:

1. Adjacency List: Each vertex stores a list of its neighbors.

   • Memory efficient for sparse graphs (few edges)
   • Fast to iterate over neighbors

2. Adjacency Matrix: A 2D array where matrix[i][j] indicates if there's an edge between vertex i and vertex j.

   • Memory inefficient for sparse graphs
   • Fast to check if an edge exists

Graph Algorithms

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking.

How it works:

1. Start at a vertex and mark it as visited
2. For each unvisited neighbor, recursively apply DFS
3. Backtrack when you reach a vertex with no unvisited neighbors

Use cases:

• Finding connected components
• Detecting cycles
• Topological sorting
• Solving mazes

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges.

Breadth-First Search (BFS)

BFS explores a graph layer by layer, visiting all neighbors before moving to the next level.

How it works:

1. Start at a vertex and add it to a queue
2. While the queue is not empty:
   • Remove a vertex from the queue
   • Visit all its unvisited neighbors and add them to the queue

Use cases:

• Finding the shortest path in unweighted graphs
• Level-order traversal
• Finding connected components
• Social network analysis (degrees of separation)

Time complexity: O(V + E)

Real-World Applications

• Social Networks: Friends, followers, connections (Facebook, LinkedIn, Twitter)
• Internet: Web pages and links, network topology
• Transportation: Roads, flights, public transit routes
• Computer Networks: Routers, switches, connections
• Biology: Protein interactions, neural networks, food chains
• Recommendation Systems: Users and products they like
• Compilers: Dependency graphs for build systems

Project Structure

This is project works with a data file (data/friends.csv) representing a social network. The CSV parsing logic is already provided in Main.java, creating the Graph and Node objects for you.

Assignments

In this workshop, you'll implement two fundamental graph algorithms to analyze a social network. The network is represented as an undirected graph where people are vertices and friendships are edges.

Assignment 1: Detecting Friendship Groups (DFS)

Goal: Find out how many separate friendship groups (connected components) exist in the network.

For example, if Alice knows Bob, Bob knows Charlie, and David knows Eve, but there's no connection between these two groups, then there are 2 friendship groups.

Step-by-Step Implementation Guide

Step 1: Understand the Data Structure

• Each Node represents a person
• Each Node has a list of friends (neighbors)
• The Graph contains all nodes

💡 Hint for Step 1

Look at the Node class. What properties does it have? How are friendships stored?

public class Node {
    private String name;
    private List<Node> friends;
    // getters...
}

Step 2: Set Up the DFS Method

• Create a method countCircles() in the Graph class
• You'll need a way to track which nodes you've already visited
• Initialize a counter for the number of groups

💡 Hint for Step 2

Use a Set or similar data structure to keep track of visited nodes. Why? Because we need to quickly check if a node has been visited, and sets provide O(1) lookup time.

Step 3: Iterate Through All Nodes

• Loop through all nodes in the graph
• For each unvisited node, you've found a new group!

💡 Hint for Step 3

for (Node node : nodes) {
    if (!visited.contains(node)) {
        circles++;
        dfs(node, visited);
    }
}

Step 4: Implement the DFS Helper Method

• Create a recursive DFS method that takes a node and the visited set
• Mark the current node as visited
• Recursively visit all unvisited neighbors

💡 Hint for Step 4

The DFS method should:

1. Add the current node to the visited set
2. For each friend of the current node:
   • If the friend hasn't been visited, recursively call DFS on that friend

private void dfs(Node node, Set<Node> visited) {
    visited.add(node);
    
    for (Node friend : node.getFriends()) {
        if (!visited.contains(friend)) {
            dfs(friend, visited);
        }
    }
}

Step 5: Test Your Implementation

• Run your code with the provided friends.csv
• You should find 3 separate friendship groups

💡 Hint for Step 5

Look at the CSV file:

• Group 1: Alice, Bob, Charlie, David (they form a cycle)
• Group 2: Eve, Frank, Grace, Helen (they form a cycle)
• Group 3: Ian, Jane, Ken (they form a cycle)

---

Assignment 2: Shortest Chain of Acquaintances (BFS)

Goal: Given two people, find the shortest chain of friendships connecting them.

For example, if you want to find the shortest path from Alice to David, and the network is: Alice → Bob → Charlie → David, the shortest path length is 3 (three edges/hops).

Step-by-Step Implementation Guide

Step 1: Understand the Problem

• We want the shortest path in an unweighted graph
• BFS naturally finds the shortest path because it explores layer by layer

💡 Hint for Step 1

Why BFS and not DFS? DFS might find a path, but not necessarily the shortest one. BFS explores all paths of length 1 before exploring paths of length 2, guaranteeing the shortest path.

Step 2: Set Up the BFS Method

• Create a method BFS(startName, endName) in the Graph class
• You'll need:
  • A queue to track nodes to visit (FIFO - First In, First Out)
  • A way to track the distance from the start node to each visited node

💡 Hint for Step 2

Use:

• A Queue for nodes to process
• A Map<Node, Integer> to store the distance from the start node to each node
  • This map also serves as a "visited" tracker!

Step 3: Initialize BFS

• Find the start and end nodes by their names
• Add the start node to the queue
• Set the distance to the start node as 0

💡 Hint for Step 3

Queue<Node> queue = new LinkedList<>();
Map<Node, Integer> distance = new HashMap<>();

queue.add(startNode);
distance.put(startNode, 0);

Step 4: Implement the BFS Loop

• While the queue is not empty:
  • Remove a node from the queue
  • If it's the target node, return the distance
  • Otherwise, explore all unvisited neighbors

💡 Hint for Step 4

while (!queue.isEmpty()) {
    Node current = queue.poll();
    
    if (current.equals(endNode)) {
        return distance.get(current);
    }
    
    for (Node neighbor : current.getFriends()) {
        if (!distance.containsKey(neighbor)) {
            distance.put(neighbor, distance.get(current) + 1);
            queue.add(neighbor);
        }
    }
}

The key insight: A neighbor's distance is always current node's distance + 1

Step 5: Handle Edge Cases

• What if the start or end node doesn't exist?
• What if there's no path between them?

💡 Hint for Step 5

• Return -1 if start or end node is null
• Return -1 if the BFS completes without finding the target (no path exists)

Step 6: Test Your Implementation

• Try finding the path between David and Bob
• They're in the same group, so there should be a path
• Try finding the path between Alice and Eve
• They're in different groups, so there's no path (should return -1)

💡 Hint for Step 6

Expected results with the provided data:

• David to Bob: 2 (David → Alice → Bob or David → Charlie → Bob, depending on the path)
• Alice to Eve: -1 (no path - different groups)

---

Additional Challenges (Optional)

Once you've completed both assignments, try these extensions:

1. Find the Actual Path: Modify BFS to return not just the length, but the actual sequence of people connecting two individuals. For example, not just "2", but ["David", "Alice", "Bob"].

2. Find the Most Connected Person: Who has the most friends? This is finding the node with the highest degree. Can there be multiple people with the same maximum number of friends?

3. All Paths Between Two People: Find all possible paths between two people (not just the shortest). This is more challenging! Hint: Use DFS with backtracking.

4. Six Degrees of Separation: Find the maximum shortest path length between any two people in the same group (the diameter of the graph). This tells you the "width" of a social network.