PENUGASAN 9 -- GRAPH

 Implementasi Graph Java

1. Adjacency Matrix

The situation where our nodes/vertices are objects (like they most likely would be) is highly complicated and requires a lot of maintenance methods that make adjacency matrices more trouble than they're worth most of the time, so we'll only provide the implementation of the "simple" case.

Source

public class Graph {
 
    private int numOfNodes;
    private boolean directed;
    private boolean weighted;
    private float[][] matrix;
 
    /*
     This will allow us to safely add weighted graphs in our class since
     we will be able to check whether an edge exists without relying
     on specific special values (like 0)
    */
    private boolean[][] isSetMatrix;
   
    public Graph(int numOfNodes, boolean directed, boolean weighted) {
 
    this.directed = directed;
    this.weighted = weighted;
    this.numOfNodes = numOfNodes;
 
    // Simply initializes our adjacency matrix to the appropriate size
    matrix = new float[numOfNodes][numOfNodes];
    isSetMatrix = new boolean[numOfNodes][numOfNodes];
    }
   
    public void addEdge(int source, int destination) {
 
    int valueToAdd = 1;
 
    if (weighted) {
        valueToAdd = 0;
        }
 
    matrix[source][destination] = valueToAdd;
    isSetMatrix[source][destination] = true;
 
    if (!directed) {
        matrix[destination][source] = valueToAdd;
        isSetMatrix[destination][source] = true;
        }
    }
   
    public void addEdge(int source, int destination, float weight) {
 
    float valueToAdd = weight;
 
    if (!weighted) {
        valueToAdd = 1;
        }
 
    matrix[source][destination] = valueToAdd;
    isSetMatrix[source][destination] = true;
 
    if (!directed) {
        matrix[destination][source] = valueToAdd;
        isSetMatrix[destination][source] = true;
        }
    }
   
    public void printMatrix() {
    for (int i = 0; i < numOfNodes; i++) {
        for (int j = 0; j < numOfNodes; j++) {
            // We only want to print the values of those positions that have been marked as set
            if (isSetMatrix[i][j])
                System.out.format("%8s", String.valueOf(matrix[i][j]));
            else System.out.format("%8s", "/  ");
            }
        System.out.println();
        }
    }
   
    public void printEdges() {
    for (int i = 0; i < numOfNodes; i++) {
        System.out.print("Node " + i + " is connected to: ");
        for (int j = 0; j < numOfNodes; j++) {
            if (isSetMatrix[i][j]) {
                System.out.print(j + " ");
                }
            }
        System.out.println();
        }
    }
   
    public boolean hasEdge(int source, int destination) {
        return isSetMatrix[source][destination];
    }
 
    public Float getEdgeValue(int source, int destination) {
        if (!weighted || !isSetMatrix[source][destination])
            return null;
        return matrix[source][destination];
    }


public static void main(String[] args) {
 
        // Graph(numOfNodes, directed, weighted)
        Graph graph = new Graph(5, false, true);
 
        graph.addEdge(0, 2, 19);
        graph.addEdge(0, 3, -2);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3); // The default weight is 0 if weighted == true
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
 
        graph.printMatrix();
 
        System.out.println();
        System.out.println();
 
        graph.printEdges();
 
        System.out.println();
        System.out.println("Does an edge from 1 to 0 exist?");
        if (graph.hasEdge(0,1)) {
            System.out.println("Yes");
        }
        else System.out.println("No");
    }
}

Output

If we constructed a graph based on this matrix, it would look like the following:

2. Adjacency List

Adjacency lists are much more intuitive to implement and are used a lot more often than adjacency matrices. We use lists to represent all nodes that our node has an edge to. Most often this is implemented with Hashmap and Linkedlist

Source

import java.util.HashMap;
import java.util.LinkedList;
 public class Node {
    int n;
    String name;
 
    Node(int n, String name){
        this.n = n;
        this.name = name;
    }
}

class Graph {
 
// Each node maps to a list of all his neighbors
private HashMap<Node, LinkedList<Node>> adjacencyMap;
private boolean directed;
 
public Graph(boolean directed) {
    this.directed = directed;
    adjacencyMap = new HashMap<>();
}
 
public void addEdgeHelper(Node a, Node b) {
    LinkedList<Node> tmp = adjacencyMap.get(a);
 
    if (tmp != null) {
        tmp.remove(b);
    }
    else tmp = new LinkedList<>();
    tmp.add(b);
    adjacencyMap.put(a,tmp);
}
 
public void addEdge(Node source, Node destination) {
 
    // We make sure that every used node shows up in our .keySet()
    if (!adjacencyMap.keySet().contains(source))
        adjacencyMap.put(source, null);
 
    if (!adjacencyMap.keySet().contains(destination))
        adjacencyMap.put(destination, null);
 
    addEdgeHelper(source, destination);
 
    // If a graph is undirected, we want to add an edge from destination to source as well
    if (!directed) {
        addEdgeHelper(destination, source);
    }
}
 
 
public void printEdges() {
        for (Node node : adjacencyMap.keySet()) {
            System.out.print("The " + node.name + " has an edge towards: ");
            if (adjacencyMap.get(node) != null) {
                for (Node neighbor : adjacencyMap.get(node)) {
                    System.out.print(neighbor.name + " ");
                }
                System.out.println();
            }
            else {
                System.out.println("none");
            }
        }
    }
 
public boolean hasEdge(Node source, Node destination) {
    return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null && adjacencyMap.get(source).contains(destination);
}
}

Output

In more concrete terms, if we had a graph with N nodes and E edges, the space complexity of these two approaches would be:

Referensi

https://stackabuse.com/graphs-in-java-representing-graphs-in-code

http://fajarbaskoro.blogspot.com/2021/06/graph.html

Adelia Hasna Surya Putri/5025201200