This Java program models a directed graph to represent course...

April 3, 2025 at 09:50 PM

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
import java.lang.reflect.Array;
import javax.sound.sampled.BooleanControl;
import javax.swing.text.Position;

class Result {
    public class Vertex {
        public int courseNum;
        public ArrayList<Edge> outgoing, incoming;
            
        public Vertex(int courseNum) {
            this.courseNum = courseNum;
            incoming = new ArrayList<>();
            outgoing = new ArrayList<>();
        }
    }
        
    public class Edge {
        public Vertex[] endpoints;
            
        public Edge(Vertex prerequisite, Vertex course) {
            endpoints = new Vertex[]{prerequisite, course};
        }
    }
        
    private ArrayList<Vertex> vertices = new ArrayList<>();
    private ArrayList<Edge> edges = new ArrayList<>();
        
    public Vertex insertVertex(int courseNum) {
        Vertex newVertex = new Vertex(courseNum);
        vertices.add(newVertex);
        return newVertex;
    }
        
    public Edge insertEdge(Vertex prereq, Vertex course) {
        Edge newEdge = new Edge(prereq, course);
        prereq.outgoing.add(newEdge);
        course.incoming.add(newEdge);
        edges.add(newEdge);
        return newEdge;
    }
    
    private Vertex head;
    private int numCourses;
    
    public Result(int numCourses) {
        Vertex newVertex = new Vertex(0);
        this.head = newVertex;
        for (int i = 1; i < numCourses; i++) {
            insertVertex(i);
        }
        this.numCourses = numCourses;
    }
    
    public Vertex opposite(Vertex v, Edge e){
        if(e.endpoints[0] == v) return e.endpoints[1];
        else if(e.endpoints[1] == v) return e.endpoints[0];
        else throw new IllegalArgumentException("v is not incident to this edge");
    }
    
    

    /*
     * Complete the 'addPrereq' function below.
     *
     * The function accepts following parameters:
     *  1. INTEGER prereq
     *  2. INTEGER course
     */

    // Add prerequisite
    public void addPrereq(int prereq, int course) {
        Vertex prereqPtr = vertices.get(prereq);
        Vertex coursePtr = vertices.get(course);
        insertEdge(prereqPtr, coursePtr);
    }

  
    // Complete the 'isPossible' function below.
    public boolean isPossible() {
        return false;
        
        
        
    }
    
    public HashMap<Vertex,Edge> CycleDetectionWrapper(Vertex v){
        HashMap<Vertex,Edge> record = new HashMap<>();
        HashMap<Vertex,Edge> ancestors = new HashMap<>();
        record.put(v,null);
        ancestors.put(v,null);
        CycleDetection(record,v,ancestors);
        return record;
    }
    
    public boolean CycleDetection(HashMap<Vertex,Edge> record, Vertex u, HashMap<Vertex,Edge> ancestors){
        for (Edge e: u.outgoing){
            Vertex v = opposite(u, e);
            if(ancestors.containsKey(v)) return true;
            if(record.containsKey(v)==false){
                record.put(v,e);
                ancestors.put(v,null);
                if (CycleDetection(record,v,ancestors)==true) return true;
                ancestors.remove(v);
            }
        }
        return false;
    }
  
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int numCourses = Integer.parseInt(firstMultipleInput[0]);
        int numPrereqs = Integer.parseInt(firstMultipleInput[1]);

        Result result = new Result(numCourses);
        IntStream.range(0, numPrereqs).forEach(numPrereqsItr -> {
            try {
                String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
                int prereq = Integer.parseInt(secondMultipleInput[0]);
                int course = Integer.parseInt(secondMultipleInput[1]);
               
                result.addPrereq(prereq, course);
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });
        if (result.isPossible())
            System.out.println("possible");
        else
            System.out.println("IMPOSSIBLE");

        bufferedReader.close();
    }
}

This Java program models a directed graph to represent course prerequisites and determines if it is possible to complete all courses based on the given prerequisites. Here's a detailed breakdown of what the code does:

Classes and Structure:

Result class:
- Represents a directed graph where:
  - Each course is represented as a vertex (Result.Vertex).
  - Each prerequisite relationship is represented as a directed edge (Result.Edge).
- Tracks vertices (ArrayList<Vertex> vertices) and edges (ArrayList<Edge> edges).
Inner Classes:
- Vertex: Represents a course.
  - courseNum: The ID of the course.
  - incoming: A list of edges directed into this vertex.
  - outgoing: A list of edges directed away from this vertex.
- Edge: Represents a directed edge connecting two vertices.
  - endpoints[0]: The prerequisite course.
  - endpoints[1]: The dependent course.
Functions in the Result class:
- insertVertex(int courseNum): Adds a course (vertex) to the graph.
- insertEdge(Vertex prereq, Vertex course): Adds an edge (prerequisite relationship) between two courses.
- opposite(Vertex v, Edge e): Returns the other endpoint of an edge e given one endpoint v.
- addPrereq(int prereq, int course): Adds a prerequisite relationship between two courses using their indices.
- CycleDetection and CycleDetectionWrapper: Identify cycles in the graph by doing a depth-first traversal and using a map (ancestors) to track visited vertices on the path.
- isPossible: (Unfinished logic) A placeholder method that is supposed to determine if it is possible to complete all courses (i.e., check for a cycle using the CycleDetection function). It currently always returns false.

Solution Class:

Purpose: Drives the program.
Reads input for the number of courses (numCourses) and number of prerequisites (numPrereqs).
Builds a Result object representing the course graph by repeatedly calling result.addPrereq(prereq, course) for each prerequisite relationship.
Invokes the result.isPossible() function to determine if course scheduling is possible:
- If a cycle exists (indicating circular prerequisites), outputs "IMPOSSIBLE".
- Otherwise, outputs "possible".

Mechanism and Execution Flow:

Input Parsing (Driver Code in main):
- Reads the number of courses and prerequisites.
- Reads prerequisite pairs (prereq -> course) line-by-line.
- Dynamically builds the graph using addPrereq.
Graph Construction (Result Class):
- For each prerequisite pair, adds a directed edge from the prerequisite course to the dependent course.
Cycle Detection:
- A directed graph can represent circular dependencies (e.g., A → B → C → A). If such cycles exist, completing the courses is impossible.
- The CycleDetection method performs a Depth-First Search (DFS) traversal to detect cycles:
  - Tracks all currently visited/recursed vertices (ancestors map).
  - If a previously visited vertex is found in this map, it represents a cycle.
Output:
- If CycleDetection detects a cycle, the graph contains circular prerequisites.
  - Output: "IMPOSSIBLE"
- Otherwise:
  - Output: "possible"

Unfinished Code:

The isPossible method is currently incomplete and always returns false. For the program to function correctly, this method needs to:

Use CycleDetectionWrapper(Vertex head) (or similar logic) to check all vertices for cycles.
Return true if no cycles are detected, and false otherwise.

Use Case:

This program essentially solves a topological sorting problem or a course scheduling problem. It checks whether it's possible to finish all courses given the prerequisites by verifying acyclic dependencies in a directed graph.

Key Observations:

Graph Representation: The code uses an adjacency list approach (via incoming and outgoing edge lists) to represent the directed graph.
Cycle Detection Algorithm: Implements DFS-based cycle detection with efficient use of hash maps to track traversal state.
Limitations:
- The code's isPossible() method is incomplete, making the solution non-functional without additional logic.
- Could benefit from improvements in initialization (e.g., streamline vertex insertion logic).

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr