Graphs. Terminologi Graph

12/23/2014

Graphs

Terminologi Graph • Graph terdiri dari kumpulan vertex V, dan edge E yang menghubungkan pasangan vertex. – Edge e = (vi,vj) menghubungkan vertex vi dan vj. – Self-loop adalah garis yang menghubungkan vertex ke dirinya sendiri. Diasumsikan graph yang digunakan tidak mempunyai self-loop.

Vertex = {v1, v2, v3, …, vm} Edge = {e1, e2, e3, …, en}

1

12/23/2014

Terminologi Graph (lanj.)

Terminologi Graph (lanj.) • Degree dari vertex adalah jumlah edge pada vertex. • Dua vertex dalam graph adalah adjacent (tetangga) jika terdapat edge yang terhubung vertex • Jalur antara vertex v dan w adalah edge dari v ke w. Panjang jalur adalah jumlah edge dalam jalur • Jalur dikatakan sederhana jika edge berbeda. Siklus pada jalur sederhana mulai dan berakhir pada vertex yang sama • Connected graph jika jalur antara semua pasangan pada vertex yang berbeda • Complete graph jika jalur yang terhubung pada setiap pasangan vertex terhubung oleh edge

2

12/23/2014

Terminologi Graph (lanj.)

Terminologi Graph (lanj.) • Undirected graph adalah graph dimana hubungan antar vertex terjadi 2 arah • Directed graph, edge mempunyai arah. Misalnya edge dari v ke w tetapi tidak sebaliknya dari w ke v

3

12/23/2014

Terminologi Graph (lanj.) • Dalam directed graph (digraph), directed path (jalur) yang terhubung antara vertex vs dan ve adalah urutan garis berarah yang dimulai dari vs dan berakhir pada ve. • Jumlah edge yang keluar dari vertex v disebut outdegree dari vertex. • Jumlah edge yang masuk ke vertex v disebut in-degree dari vertex. • Digraph dikatakan strongly connected jika terdapat jalur dari semua vertex ke semua vertex lain • Digraph dikatakan weakly connected jik setiap pasangan vertex vi dan vj, terdapat jalur P(vi, vj) atau P(vj,vi).

Terminologi Graph (lanj.)

4

12/23/2014

Terminologi Graph (lanj.) • Acyclic graph tidak mempunyai siklus • Setiap edge pada weighted digraph (graph berarah berbobot), mempunyai biaya yang terhubung dengan edge

Membuat dan Menggunakan Graph • Interface Graph mempunyai operasi graph dasar termasuk menyisipkan dan menghapus vertex dan edge

5

12/23/2014

Membuat dan Menggunakan Graph (lanj.) interface GRAPH

ds.util.Graph Methods

boolean addEdge(T v1, T v2, int w) Jika edge (v1, v2) tidak di dalam graph, tambahkan edge dengan beban w dan return true. Return false jika edge sudah ada dalam graph. Jika v1 atau v2 bukan vertex dalam graph, throw IllegalArgumentException. boolean addVertex(T v) Jika v tidak di dalam graph, tambahkan ke dalam graph dan return true; lainnya, return false. void clear() menghapus semua vertex dan edge dari graph.

Membuat dan Menggunakan Graph (lanj.)

interface GRAPH

ds.util.Graph Methods (continued)

boolean containsEdge(T v1, T v2) Return true jika terdapat edge dari v1 ke v2 dan lainnya return false otherwise. Jika v1 atau v2 bukan vertex dalam graph, throw IllegalArgumentException. boolean containsVertex(Object v) Return true jika v adalah vertex dalam graph dan sebaliknya false Set getNeighbors(T v) Return vertex yang adjacent (tetangga) dengan vertex v dalam Set object. Jika v bukan vertex dalam graph, throw IllegalArgumentException.

6

12/23/2014

Membuat dan Menggunakan Graph (lanj.)

interface GRAPH

ds.util.Graph Methods (continued)

int getWeight(T v1, T v2) Return beban dari edge yang terhubung pada vertex v1 ke v2. Jika edge (v1,v2) tidak ada, return -1. Jika v1 atau v2 bukan vertex dalam graph, throw IllegalArgumentException. boolean isEmpty() Return true jika graph tidak terdapat vertex dan edge dan false jika sebaliknya. int numberOfEdges() Return jumlah edge dalam graph.

Membuat dan Menggunakan Graph (lanj.)

interface GRAPH

ds.util.Graph Methods (continued)

int numberOfVertices() Return jumlah vertex dalam graph. boolean removeEdge(T v1, T v2) Jika (v1,v2) adalah edge, hapus edge dan return true; sebaliknya, return false. Jika v1 atau v2 bukan vertex dalam graph, throw IllegalArgumentException. boolean removeVertex(Object v) Jika v adalah vertex dalam graph, hapus dari graph dan return true; sebaliknya, return false.

7

12/23/2014

Membuat dan Menggunakan Graph (lanj.) interface GRAPH

ds.util.Graph Methods (continued)

int setWeight(T v1, T v2, int w) Jika edge (v1, v2) dalam graph, update beban edge dan return beban sebelumnya; sebaliknya, return -1. Jika v1 atau v2 bukan vertex dalam graph, throwsIllegalArgumentException. Set vertexSet() Return a set-view dari vertex dalam graph.

Membuat dan Menggunakan Graph (lanj.)

8

12/23/2014

Class DiGraph • Class DiGraph mengimplementasikan interface Graph dan menambah metode lain yang berguna dalam aplikasi – Constructor membuat graph empty (kosong) – Method inDegree() dan outDegree() adalah method khusus yang mengakses properti yang unik ke graph – Method static readGraph() membangun graph dimana vertex adalah string.

Class DiGraph (lanj.) • Method readGraph() menginputkan nilai vertex dan edge dari textfile. – Format file:

(Number of Edges n) Source1 Destination1 Source2 Destination2 . . . Sourcen Destinationn

Weight1 Weight2 Weightn

9

12/23/2014

Class DiGraph (lanj.) • Method toString() merupakan representasi dari graph. Untuk setiap vertex, string memberikan daftar tetangga vertex dengan beban pada edge. Informasi untuk setiap vertex termasuk in-degree dan out-degree nya.

Class DiGraph (lanj.) File samplegraph.dat 5 // data for the vertices A B C D E 6 // data for the edges A B 3 A C 2 B C 6 C B 4 C D 1 E B 5 // input vertices, edges, and weights from samplegraph.dat DiGraph g = DiGraph.readGraph("samplegraph.dat"); // display the graph System.out.println(g)

10

12/23/2014

Class DiGraph (lanj.) Output: A: in-degree 0 Edges: B(3) B: in-degree 3 Edges: C(6) C: in-degree 2 Edges: B(4) D: in-degree 1 Edges: E: in-degree 0 Edges: B(5)

out-degree 2 C(2) out-degree 1 out-degree 2 D(1) out-degree 0 out-degree 1

Program 1

11

12/23/2014

Program 1 import java.io.FileNotFoundException; import ds.util.Set; import ds.util.Iterator; import ds.util.DiGraph; public class ProgramGraph { public static void main(String[] args) throws FileNotFoundException { // construct graph with vertices of type // String by reading from the file "graphIO.dat" DiGraph<String> g = DiGraph.readGraph("graphIO.dat"); String vtxName; // sets for vertexSet() and adjacent // vertices (neighbors) Set<String> vtxSet, neighborSet;

Program 1 (lanj) // output number of vertices and edges System.out.println("Number of vertices: " + g.numberOfVertices()); System.out.println("Number of edges: " + g.numberOfEdges()); // properties relative to vertex A System.out.println("inDegree for A: " + g.inDegree("A")); System.out.println("outDegree for A: " + g.outDegree("A")); System.out.println("Weight e(A,B): " + g.getWeight("A","B")); // delete edge with weight 2 g.removeEdge("B", "A"); // delete vertex "E" and edges (E,C), // (C,E) and (D,E) g.removeVertex("E");

12

12/23/2014

Program 1 (lanj) /* add and update attributes of the graph */ // increase weight from 4 to 8 g.setWeight("A","B",8); // add vertex F g.addVertex("F"); // add edge (F,D) with weight 3 g.addEdge("F","D",3); // after all updates, output the graph // and its properties System.out.println("After all the graph updates"); System.out.println(g); // get the vertices as a Set and // create set iterator vtxSet = g.vertexSet(); Iterator vtxIter = vtxSet.iterator();

Program 1 (lanj) // scan the vertices and display // the set of neighbors while(vtxIter.hasNext()) { vtxName = (String)vtxIter.next(); neighborSet = g.getNeighbors(vtxName); System.out.println(" Neighbor set for " + "vertex " + vtxName + " is " + neighborSet); } } }

13

12/23/2014

Program 1 (lanj) Number of vertices: 5 Number of edges: 8 inDegree for A: 1 outDegree for A: 3 Weight e(A,B): 4 After all the graph updates A: in-degree 0 out-degree Edges: B(8) C(7) D(6) B: in-degree 2 out-degree Edges: C: in-degree 1 out-degree Edges: B(3) D: in-degree 2 out-degree Edges: F: in-degree 0 out-degree Edges: D(3)

3 0 1 0 1

Program 1 (lanj) Neighbor Neighbor Neighbor Neighbor Neighbor

set set set set set

for for for for for

vertex vertex vertex vertex vertex

D F A B C

is is is is is

[] [D] [D, B, C] [] [B]

14

12/23/2014

Algoritma Breadth-First Search • Breadth-first search mengunjungi vertex sesuai jalur dari vertex awal. Kemungkinan tidak mengunjungi setiap vertex pada graph • Algoritma Graph membedakan vertex selama algoritma dengan menggunakan warna PUTIH, GRAY, dan HITAM.

Algoritma Breadth-First Search (lanj) • Warnai semua vertex dari graph contoh dg PUTIH dan push vertex (A) ke queue visitQueue. • Pop A dari queue, warnai dg HITAM, dan insert ke visitList, yaitu daftar vertex yang dikunjungi. Push semua tetangga PUTIH ke queue. Warnai dengan GRAY

15

12/23/2014

Algoritma Breadth-First Search (lanj) • Pop B dari queue dan tempatkan pada visitList dan warnai HITAM. Hanya tetangga vertex untuk B adalah D, yang masih berwarna PUTIH. Warnai D dg GRAY dan tambahkan ke queue

Algoritma Breadth-First Search (lanj) • Pop C dan tempatkan dalam visitList. Tetangga vertex G adalah GRAY. Tidak ada vertex yang masuk ke queue.

16

12/23/2014

Algoritma Breadth-First Search (lanj) • Pop vertex G dari queue dan tempatkan dalam visitList. G tidak mempunyai vertex tetangga, sehingga pop D dari queue. Tetangganya, E dan F, masuk ke queue.

Algoritma Breadth-First Search (lanj) • Lanjutkan sampai queue kosong

17

12/23/2014

Implementasi Breadth-First Search • Define public enum VertexColor { WHITE, GRAY, BLACK }

Implementasi Breadth-First Search (lanj) • Class DiGraph mendeklarasikan 3 method yang mengakses dan mengupdate atribut warna dari vertex class DiGraph (color methods)

ds.util

void colorWhite() Set warna setiap vertex ke PUTIH. VertexColor getColor(T v) Return warna vertex v. Jika v bukan vertex pada graph, throw IllegalArgumentException. VertexColor setColor(T v, VertexColor c) Set warna vertex v dan return warna sebelumnya. Jika v bukan vertex pada graph, throw IllegalArgumentException.

18

12/23/2014

Implementasi Breadth-First Search (lanj) • method bfs() return daftar vertex yang dikunjungi selama breadth-first search dari vertex awal.

bfs() // perform the breadth-first traversal // from sVertex and return the list // of visited vertices public static LinkedList bfs( DiGraph g, T sVertex) { // queue stores adjacent vertices; list // stores visited vertices LinkedQueue visitQueue = new LinkedQueue(); LinkedList visitList = new LinkedList(); // set and iterator retrieve and scan // neighbors of a vertex Set edgeSet; Iterator edgeIter; T currVertex = null, neighborVertex = null;

19

12/23/2014

bfs() (lanj) // check that starting vertex is valid if (!g.containsVertex(sVertex)) throw new IllegalArgumentException( "bfs(): starting vertex not in the graph"); // color all vertices WHITE g.colorWhite(); // initialize queue with starting vertex visitQueue.push(sVertex); while (!visitQueue.isEmpty()) { // remove a vertex from the queue, color // it black, and add to the list of // visited vertices currVertex = visitQueue.pop(); g.setColor(currVertex,VertexColor.BLACK); visitList.add(currVertex);

bfs() (lanj) // obtain the set of neighbors for current vertex edgeSet = g.getNeighbors(currVertex); // sequence through the neighbors and look // for vertices that have not been visited edgeIter = edgeSet.iterator(); while (edgeIter.hasNext()) { neighborVertex = edgeIter.next(); if (g.getColor(neighborVertex) == VertexColor.WHITE) { // color unvisited vertex GRAY and // push it onto queue g.setColor(neighborVertex,VertexColor.GRAY); visitQueue.push(neighborVertex); } } } return visitList; }

20

12/23/2014

Testing Breadth-First Search

// create a graph g and declare startVertex and visitList DiGraph<String> g = DiGraph.readGraph("bfsgraph.dat"); String startVertex; List<String> visitList; ... // call bfs() with arguments g and startVertx visitList = DiGraphs.bfs(g, startVertex); // output the visitList System.out.println("BFS visitList from " + startVertex + ": " + visitList);

Testing Breadth-First Search

Output: Run 1: (startVertex = "A") BFS visitList from A: [A, G, B, C, D, E, F] Run 2: (startVertex = "D") BFS visitList from D: [D, E, F, G] Run 3: (startVertex = "E") BFS visitList from E: [E]

21

12/23/2014

Algoritma Shortest Path (Jalur Terpendek) • Breadth-first search dapat digunakan untuk menemukan jalur terpendek • Dimulai pada vertex sVertex dan mengunjungi tetangga (panjang jalur = 1) diikuti vertex dg panjang jalur berikutnya yang terpanjang. • Algoritma mengunjung dari sVertex ke jalur tetanggany sampai semua vertex tercapai dari sVertex

Algoritma Shortest Path (lanj) • Setiap vertex harus menyimpan catatan parent dan panjang jalur dari sVertex. Class DiGraph menyediakan method yang memungkinkan programmer untuk menghubungkan dua field informasi dengan vertex. – Satu field mengidentifikasi parent dari vertex, dan field lain adalah integer dataValue yang berhubungan dengan vertex. Method initData() berisi ∞ untuk setiap field dataValue field pada vertex graph

22

12/23/2014

Algoritma Shortest Path (lanj) class DiGraph (dataValue and parent methods)

ds.util

int getData(T v) Return integer data value yang berhubungan dengan vertex v. Jika v bukan vertex pada graph, throw IllegalArgumentException. T getParent(T v) Return parent dari vertex v. jika v bukan vertex pada graph, throw IllegalArgumentException. int setData(T v, int value) Set integer data value yang berhubunjgan dengan vertex v dan return nilai sebelumnya. Jika v bukan vertex, throw IllegalArgumentException. T setParent(T v, T p) Set parent dari vertex v menjadi p dan return parent sebelumnya. Jika v atau p bukan vertex, throw IllegalArgumentException. void initData() memberikan nilai field data Value untuk setiap vertex berupa ∞.

Algoritma Shortest Path (lanj) • Breadth-first search mengunjungi vertex yang merupakan jalur terpendek dari vertex awal • Field parent dari vertex menentukan urutan vertex dari vertex awal • Mulai algoritma dengan sVertex = C. Dalam vertex, set dataValue (panjang jalur) ke 0 dan buat sVertex sebagai parent. Inisialisasi queue dengan menambah C sebagai elemen pertama

23

12/23/2014

Algoritma Shortest Path (lanj) • Pada setiap step, algoritma mengubah data value (panjang jalur dari vertex awal) dan parent me-referensi sebelum vertex masuk ke queue. Alkhir dari algoritma (queue dalam kondisi kosong), data value dari vertex adalah path terpendek dari vertex awal

A B C D E F

Pop C

Pop E

Pop F

Pop D

Path [empty] ∞ ∞ 0 ∞ ∞ ∞

Path C - E ∞ ∞ 0 ∞ 1 ∞

Path C - F ∞ ∞ 0 ∞ 1 1

Path C - E - D ∞ ∞ 0 2 1 1

Pop B Path C - E - D - B

∞ 3 0 2 1 1

Algoritma Shortest Path (lanj) • shortestPath() mencari jalur terpendek dari vs ke semua vertex dalam graph. Nilai ∞ jika vertex tidak dapat dicapai dari vs.

24

12/23/2014

shortestPath() // use the breadth-first traversal algorithm to // determine the minimum number of edges in any // path from sVertex to all vertices in the graph // reachable from sVertex; upon return, the dataValue // field of each vertex in g is either the shortest // path length to the vertex or is INFINITY if the // vertex was not reachable from sVertex; call // path(g, sVertex, v) to find the shortest path // from sVertex to v public static void shortestPath(DiGraph g, T sVertex) { // BFS uses a queue to store adjacent vertices LinkedQueue visitQueue = new LinkedQueue(); Set edgeSet; Iterator edgeIter; T currVertex = null, neighborVertex = null; int currentPathLength;

shortestPath() (lanj) if (!g.containsVertex(sVertex)) throw new IllegalArgumentException( "shortestPath(): starting vertex not " + "in the graph"); // set each vertex data value to INFINITY g.initData(); // sVertex is its own parent and the shortest path // to itself has length 0 g.setParent(sVertex, sVertex); g.setData(sVertex, 0); // insert starting vertex into the queue visitQueue.push(sVertex); // process vertices until the queue is empty while (!visitQueue.isEmpty()) { // delete a queue entry currVertex = visitQueue.pop();

25

12/23/2014

shortestPath() (lanj) edgeSet = g.getNeighbors(currVertex); // sequence through the edge set and look // for vertices that have not been visited; // assign each such vertex a dataValue of // currentPathLength + 1 currentPathLength = g.getData(currVertex); edgeIter = edgeSet.iterator(); while (edgeIter.hasNext()) { neighborVertex = edgeIter.next(); if (g.getData(neighborVertex) == INFINITY) { g.setData(neighborVertex, currentPathLength + 1); g.setParent(neighborVertex, currVertex); visitQueue.push(neighborVertex); } } } }

path() // returns the path computed by a graph algorithm // from sVertex to eVertex public static LinkedList path(DiGraph g, T sVertex, T eVertex) { T currVertex = eVertex; LinkedList path = new LinkedList(); if (g.getData(eVertex) == DiGraphs.INFINITY) return path; while (!currVertex.equals(sVertex)) { path.addFirst(currVertex); currVertex = g.getParent(currVertex); } path.addFirst(sVertex); return path; }

26