Flow Graph
Untuk menghitung ukuran kompleksitas logik dari suatu kode program, V(G), penguji melakukan basis path testing. Nilai V(G), menyatakan jumlah maksimum kasus uji yang harus didesain dengan mengidentifikasi sekumpulan basis ekseskusi paths untuk menjamin semua pernyataan dieksekusi paling tidak satu kali.Testing is simple – all a tester needs to do is find a graph and cover it ” [Beizer, Software Testing Techniques book]Proses dimulai dari membuat flow graph dari kode sumber atau flow charts. Kontrol aliran program dapat direpresntasikan menggunakan representasi grafis yang dikenal dengan Flow Graph. Flow graph terdiri dari sekumpulan node dan edge. Dengan menggunakan flow graph, suatu path bebas dapat didefinisikan sebagai path pada flow graph yaitu yang mempunyai setidaknya satu edge yang belum dilalui pada path lainnya.
Every algorithm may be implemented using just the constructs sequence, selection, iteration [Bohm and Jacobini, 1966]Flow graph merupakan graph berarah dimana :
- Nodes dapat merupakan keseluruhan pernyataan atau potongan suatu pernyataan program.
- Edges merepresentasikan aliran kontrol.
- Jika “u” dan “v” adalah node pada graph, maka terdapat edge dari node “u” ke “v” jika pernyataan (potongan pernyataan) pada node “v” dapat dieksekusi langsung setelah pernyataan (potongan pernyataan) pada “u”. Misal.
Notasi Standar Flow graph
Bottom-line
Diberikan suatu program yang ditulis dalam bahasa pemrograman imperative, maka program graphnya adalah graph dimana :- node adalah pernyataan program, dan
- edge merepresentasikan alur kontrol
Control Flow Graph (CFG) adalah :
- Quadruple (E, N, s, t) dimana :
- E = himpunan edge
- N = himpunan node
- s = start node
- t = terminal node
- In-degree (FAN-IN) adalah jumlah edges yang memasuki suatu node
- Out-degree (FAN-OUT) adalah jumlah edges yang meninggalkan node
- Path adalah rangkaian edge yang saling berhubungan
