# Praktikum 1

## Deskripsi

Pada percobaan ini akan diimplementasikan Graph menggunakan linked list untuk merepresentasikan graph adjacency. Struktur data linked list yang digunakan merupakan package / library dari Java.

## Langkah Percobaan

* Buatlah kelas `Graph`.
* Tambakan atribur `vertices` dan array dengan nama `list` bertipe list. Jangan lupa import package LinkedList kedalam kelas `Graph`.

{% code overflow="wrap" lineNumbers="true" %}

```java
import java.util.LinkedList;

public class Graph {
    int vertex;
    LinkedList<Integer> list[];
```

{% endcode %}

* Tambakan konstruktor didalam kelas `Graph`.

```java
public Graph(int vertex) {
    this.vertex = vertex;
    list = new LinkedList[vertex];
    for (int i = 0; i < vertex; i++) {
        list[i] = new LinkedList<>();
    }
}
```

* Tambahkan method `addEdge()`. Jika yang akan dibuat adalah graph berarah, maka yang dijalankan hanya baris pertama saja. Jika graph tidak berarah yang dijalankan semua baris pada method `addEdge()`.

{% code overflow="wrap" lineNumbers="true" %}

```java
public void addEdge(int source, int destination) {
    // add edge
    list[source].addFirst(destination);
    
    // add back edge ((for undirected)
    list[destination].addFirst(source);
}
```

{% endcode %}

* Tambahkan method `degree()` untuk menampilkan jumlah derajat lintasan pada suatu vertex. Di dalam metode ini juga dibedakan manakah statement yang digunakan untuk graph berarah atau graph tidak berarah. Eksekusi hanya sesuai kebutuhan saja.

{% code overflow="wrap" lineNumbers="true" %}

```java
public void degree(int source) throws Exception {
        // degree undirected graph
        System.out.println("Degree of " + source + " is " + list[source].size());

        // degree directed graph
        int k, totalIn = 0, totalOut = 0;
        for(int i = 0; i < vertex; i++){
            for(int j = 0; j < list[i].size(); j++){
                if(list[i].get(j) == source)
                    ++totalIn;
            }
            for(k = 0; k < list[source].size(); k++){
                list[source].get(k);
            }
            totalOut = k;
        }
        System.out.println("Indegree of " + source + " is " + totalIn);
        System.out.println("Outdegree of " + source + " is " + totalOut);
        System.out.println("Degree of " + source + " is " + (totalIn + totalOut));
    }
```

{% endcode %}

* Tambahkan method `removeEdge()`. Method ini akan menghapus lintasan ada suatu graph. Oleh karena itu, dibutuhkan 2 parameter untuk menghapus lintasan yaitu source dan destination.

{% code overflow="wrap" lineNumbers="true" %}

```java
public void removeEdge(int source, int destination) throws Exception {
    for (int i = 0; i < vertex; i++) {
        if (i == destination) {
            list[source].remove(destination);
        }
    }
}
```

{% endcode %}

* Tambahkan method `removeAllEdges()` untuk menghapus semua vertex yang ada di dalam graph.

{% code overflow="wrap" lineNumbers="true" %}

```java
public void removeAllEdges() {
    for (int i = 0; i < vertex; i++) {
        list[i].clear();
    }
    System.out.println("Graph is cleared");
}
```

{% endcode %}

* Tambahkan method `printGraph()` untuk mencatak graph ter-update.

{% code overflow="wrap" lineNumbers="true" %}

```java
public void printGraph() {
    for (int i = 0; i < vertex; i++) {
        if (list[i].size() > 0) {
            System.out.print("Vertex " + i + " is connected to: ");
            for (int j = 0; j < list[i].size(); j++) {
                System.out.print(list[i].get(j) + " ");
            }
            System.out.println();
        }
    }
    System.out.println();
}
```

{% endcode %}

* Buatlah kelas `MainGraph` dan tambahkan main method seperti berikut.

{% code overflow="wrap" lineNumbers="true" %}

```java
public static void main(String[] args) throws Exception {
    Graph graph = new Graph(6);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 0);
    graph.printGraph();
    graph.degree(2);
}
```

{% endcode %}

* Compile dan jalankan main class. Amati hasilnya.

```
Vertex 0 is connected to: 3 4 1 
Vertex 1 is connected to: 4 3 2 0 
Vertex 2 is connected to: 3 1 
Vertex 3 is connected to: 0 4 2 1 
Vertex 4 is connected to: 3 1 0 

Degree of 2 is 2
Indegree of 2 is 2
Outdegree of 2 is 2
Degree of 2 is 4
```

* Tambahkan pemanggilan method `removeEdge()` sesuai potongan code di bawah ini pada main method. Kemudian tampilkan graph tersebut.

{% code overflow="wrap" lineNumbers="true" %}

```java
graph.removeEdge(1, 2);
graph.printGraph();
```

{% endcode %}

* Amati hasilnya.

```
Vertex 0 is connected to: 3 4 1 
Vertex 1 is connected to: 4 3 0 
Vertex 2 is connected to: 3 1 
Vertex 3 is connected to: 0 4 2 1 
Vertex 4 is connected to: 3 1 0 
```

## Pertanyaan

1. Sebutkan beberapa jenis (minimal 3) algoritma yang menggunakan dasar graph, dan apakah kegunaan algoritma-algoritma tersebut?
2. Pada class `Graph` terdapat array bertipe `LinkedList`, yaitu `LinkedList list[]`. Apakah tujuan pembuatan variabel tersebut ?
3. Apakah alasan pemanggilan method `addFirst()` untuk menambahkan data, bukan method add jenis lain pada linked list ketika digunakan pada method `addEdge()` pada class `Graph`?
4. Bagaimana cara mendeteksi `prev` pointer pada saat akan melakukan penghapusan suatu edge pada graph?
5. Kenapa pada praktikum langkah untuk menghapus path yang bukan merupakan lintasan pertama kali (perhatikan main class) menghasilkan output yang salah ? Bagaimana solusinya ?


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://polinema.gitbook.io/jti-modul-praktikum-algoritma-dan-struktur-data/struktur-data-non-linear/job-sheet-10-graf/praktikum-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.