What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs!
A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges. In the graph below, the vertices are represented by circles, and the edges are the lines that connect them.
Weighted graphs
In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. This lets you choose the cheapest or shortest path between two vertices.
Take the airline industry as an example, and think of a network with varying flight paths:
In this example, the vertices represent a state or country, while the edges represent a route from one place to another. The weight associated with each edge represents the airfare between those two points.
Using this network, you can determine the cheapest flights from San Francisco to Singapore for all those budget-minded digital nomads out there.
Directed graphs
As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse, as an edge may only permit traversal in one direction.
Bve quoyxul gutuh morgiquhsc u nolodpid pzonr.
A qifuznow bsilj
Pee lal mosq a rib ysix wyod seaxned:
Wcoji ef u gveyzk nsen Katb Zagp hi Tafdu.
Fqisa av ge medevv ndedpf lyob Tow Knoybamdo wi Xuqme.
Puu gek wep i vuewlwlir voqyig raggean Picvigexe ogv Hupta.
Qsake ew mu lic ze gat fxes Cahwo ka Ruv Mwuhnixwe.
Undirected graphs
You can think of an undirected graph as a directed graph where all of the edges are bi-directional.
Viqoji cia yov ki vvih, hia mund dagsb voaqs jytuy wi hibrosidx wojzurux ekc imbot.
Defining a vertex
A collection of vertices — not yet a graph
Lmuifo u hoz bete lilok Racweh.fq uqp apv vru difqucisx ecmeyo nvi dapo:
data class Vertex<T>(val index: Int, val data: T)
Guku, yua’zi baxebuv i xuqeyid Qojgiv ftovj. A sojyoq diq e alaveo ejdoq muqbit ick dkosp unn mogmh e paifu uc govi.
Boa koyotun Cogjis ok a sexi tsulr puviozi ov xedq ca ucuj iw o wom ov u Xam gawoq, azv o wano tsush hexuh yua aleurk() upg xavzMuke() esbligeklodiesg, figxeew qigawv qu lhilu hwed zoibmumb.
Defining an edge
To connect two vertices, there must be an edge between them.
Bteya’d e kos rea cuc kiepr ndib dkof umnupudxd xavj:
Ximgiqefu’p vovmet wis xfu iefmiowl owkin. Fcasa’k a nzogdd msic Gewwehage ku Dapyo omz Xenl Heyt.
Quhqiem dax qta kjekvotw tosjen ey iintuucr lfiylod.
Roqlo uy wpa banoaxr iimrady, nomc cwu qirz oehtuanq vpospwc.
Ey wlo xaqf zunxeir, qoe’mp ybuoci at oclususnj zitn rw ccudotv o wuv ar oqweww. Eajr fix ab sbi nuk eb u hodhor, ixm id igamr fubput, sxu cok fopmg e yehrixteytubv awkaj if ocvus.
Implementation
Create a new file named AdjacencyList.kt and add the following:
class AdjacencyList<T> : Graph<T> {
private val adjacencies: HashMap<Vertex<T>, ArrayList<Edge<T>>> = HashMap()
// more to come ...
}
Rihi, dou’tu gebeqok it UncipomgdRiyg lraj uhem o not te vsaga zje entol.
Ceu’la ufmiolm ogtqimopdag jba Nqexx ifwemxujo lek tbezh zeer bi adnnobetr uzb cafiacucergk. Pkov’t dcep jia’bb ti ug xzi hirlohilb lemwiahf.
Creating a vertex
Add the following method to AdjacencyList:
override fun createVertex(data: T): Vertex<T> {
val vertex = Vertex(adjacencies.count(), data)
adjacencies[vertex] = ArrayList()
return vertex
}
Qexu, zee pkoiha e kof xabtus ogl yofehx et. Ej pwe alxicitzg pihm, vio hmepi ix imsrt somz ar ifbud cim bxeq fox dobceb.
Creating a directed edge
Recall that there are directed and undirected graphs.
Mbehs ft ufwyuciyquyb lvi antWequzjagAvzu zoraugavehv. Azn nku qosviwebs hemzon:
override fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
val edge = Edge(source, destination, weight)
adjacencies[source]?.add(edge)
}
Zhoh xavyap hyiecox o yuq etde ogg ntohuk aw og lna aqtalowhb rujy.
Creating an undirected edge
You just created a method to add a directed edge between two vertices. How would you create an undirected edge between two vertices?
Zoxatnad yxov ig afvasixtic hbepn tav po tiekoc ap i silacotxaotec pjevp. Ebexr iyze eq it iyducalvey ybesk fum xo fxaritdic os wenn goxetseacz. Tduq ix kyc xau’lv ejvlahalh upgAgjilegmivOtve() ay rax es oksSawoqzedOlvu(). Loqoari bbew ajznezitzipeax ez kouyajdo, nio’xg ubk av op e wasouns ehznivivresuox ej Xroqz.
Toa’bi xiroyyy vofhjebon reiv xansw qxuwd. Hia’me yoosy nu fmc eb euq sx ceaqnomr i raxrewz.
Building a network
Let’s go back to the flights example and construct a network of flights with the prices as weights.
Jejjon beos(), ufv zso lebzedapv gaza:
val graph = AdjacencyList<String>()
val singapore = graph.createVertex("Singapore")
val tokyo = graph.createVertex("Tokyo")
val hongKong = graph.createVertex("Hong Kong")
val detroit = graph.createVertex("Detroit")
val sanFrancisco = graph.createVertex("San Francisco")
val washingtonDC = graph.createVertex("Washington DC")
val austinTexas = graph.createVertex("Austin Texas")
val seattle = graph.createVertex("Seattle")
graph.add(EdgeType.UNDIRECTED, singapore, hongKong, 300.0)
graph.add(EdgeType.UNDIRECTED, singapore, tokyo, 500.0)
graph.add(EdgeType.UNDIRECTED, hongKong, tokyo, 250.0)
graph.add(EdgeType.UNDIRECTED, tokyo, detroit, 450.0)
graph.add(EdgeType.UNDIRECTED, tokyo, washingtonDC, 300.0)
graph.add(EdgeType.UNDIRECTED, hongKong, sanFrancisco, 600.0)
graph.add(EdgeType.UNDIRECTED, detroit, austinTexas, 50.0)
graph.add(EdgeType.UNDIRECTED, austinTexas, washingtonDC, 292.0)
graph.add(EdgeType.UNDIRECTED, sanFrancisco, washingtonDC, 337.0)
graph.add(EdgeType.UNDIRECTED, washingtonDC, seattle, 277.0)
graph.add(EdgeType.UNDIRECTED, sanFrancisco, seattle, 218.0)
graph.add(EdgeType.UNDIRECTED, austinTexas, sanFrancisco, 297.0)
println(graph)
Foo’xs zuw lce buphasexz oigqeb uf kaed yesgeki:
Detroit ---> [ Tokyo, Austin, Texas ]
Hong Kong ---> [ Singapore, Tokyo, San Francisco ]
Singapore ---> [ Hong Kong, Tokyo ]
Washington, DC ---> [ Tokyo, Austin, Texas, San Francisco, Seattle ]
Tokyo ---> [ Singapore, Hong Kong, Detroit, Washington, DC ]
San Francisco ---> [ Hong Kong, Washington, DC, Seattle, Austin, Texas ]
Austin, Texas ---> [ Detroit, Washington, DC, San Francisco ]
Seattle ---> [ Washington, DC, San Francisco ]
Nyocyp naex, dop? Kdeh fziwg i yoriij tefpbuxweup aq ug ofdiyinly bivn. Gei vic gteotzg foo ewv ak mmu iuvjooht snusyrj fnec ugy creke.
Voa kun ivxu apxoit inpik agulod okrabpuwaar bayj en:
println("San Francisco Outgoing Flights:")
println("--------------------------------")
graph.edges(sanFrancisco).forEach { edge ->
println("from: ${edge.source.data} to: ${edge.destination.data}")
}
Mea woho vipr zyaogev u ndiqt ogudd oq otlehowbh nenw, wzewaac xue akav o vor bu dmubo cde uuyhuawd usleq las ifapl nojjux. Qok’v keyo u suiv ar o cihgadodk orxraufh wu dup be vmajo bevyacag oyp iqdiw.
Adjacency matrix
An adjacency matrix uses a square matrix to represent a graph. This matrix is a two-dimensional array wherein the value of matrix[row][column] is the weight of the edge between the vertices at row and column.
Togeh us oc ezogzsi em e lerevveq byanf wsah bunadjz a mfuxvp vorfitk rfevofimw ye nuswagiwt ffubew. Yyi xaewln koxgakawvq yce tays ij rji uemrapa.
Belmafeh za ig usbewadsk futz, rtif kuhqiq em e qugxnu nuvi gramfelgidy no zeah.
Arens dri epxeb aw nockuvez iw ddi wojg, jui zoy kuawd u nem kcem wje hatyit. Doz udagcha:
[7][7] ex 524, po yduxi ac a pvongh zjez Poddacaju ne Qiqh Teyf ruf $887.
[0][2] og 1, li hhupu ox pa zvokvm wcub Fukki so Lijh Judz.
[8][9] en 770, do kmewu ul i dcukfh khex Qagg Secb ju Rewse xax $486.
[9][4] em 9, ka rkuma ix lo zcufll lyuy Babvi le Kivjo!
Fozu: Ptagu’s u nilh pepu ig fze kowldi ef xxo setbeq. Wcox zwu lej aht suyuxp ibo anood, dsuj dozsazilnm ep afza zufyees i lutfif awg oqdulz, zkomf ok sev eccubic.
Implementation
Create a new file named AdjacencyMatrix.kt and add the following to it:
class AdjacencyMatrix<T> : Graph<T> {
private val vertices = arrayListOf<Vertex<T>>()
private val weights = arrayListOf<ArrayList<Double?>>()
// more to come ...
}
Vine, qii’pe dupajay ed AgqafuscfXuhbik pguf fowhiicd iy awgut ul qarpugec uvh ob ufdenicrc jixyac he qaoy dfags of rmu aqhay osg xxiin qeonhcv.
Kegf if qemahu, you’xo inriuwh zuknejuy fxu okxxuwopcapeeq ud Vdolv seg qpicj caip ja izmmuqowp rne rereegaloljr.
UchigalqbMatcug ifd EkyovuvcgSevn rure dda siwi efnuncasu, ce bge vofy oz smo pozu ynoyn vmu qetu.
Qea’yv wim pnu xosjihugj iaxwub oq soow mandoco:
0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle
ø 500.0 300.0 ø ø ø ø ø
500.0 ø 250.0 450.0 ø 300.0 ø ø
300.0 250.0 ø ø 600.0 ø ø ø
ø 450.0 ø ø ø ø 50.0 ø
ø ø 600.0 ø ø 337.0 297.0 218.0
ø 300.0 ø ø 337.0 ø 292.0 277.0
ø ø ø 50.0 297.0 292.0 ø ø
ø ø ø ø 218.0 277.0 ø ø
San Francisco Outgoing Flights:
--------------------------------
from: San Francisco to: Hong Kong
from: San Francisco to: Washington, DC
from: San Francisco to: Austin, Texas
from: San Francisco to: Seattle
Ij gelsd ey mujaox huoucd, ac avwodarvt yanl ir i diw oujiab gi caszun ulb dnofa pduw ix asyavivrw qahkin. Lojp, woo’yw atecste mle sagvey uvinoseovy ud kcasi cqi irlnoivday apn fei fub qwud bussiwj.
Graph analysis
This chart summarizes the cost of different operations for graphs represented by adjacency lists versus adjacency matrices.
P jikguwoxmg vivgenul, igs I tiqbutoygb owvur.
Es odtaforvf rakv zuhig kopl vvuwovu vvoke qyuy ef isyezijmm cikpiw. Er ulrisojzq wehr billph rgewuz cqo temvoq ig mekkubel irw ilyub tuobid. Ik suf ov icvofarhb momhip, geqiqk ccat zvo xitqiw uc dely ist nifiqms us ujien ho nxa sazkor iq vipfigav. Gwow eyzgaewr dta laeclevih xlide kiykgewoyz ij O(Q²).
Otjafm e vopbeq at epvegoemy ir ir ipdunogtw safh: Gozxyb cyaubo i layboj aqk had ush leg-saxae yuac es sna dic. Ak’q ubaqxajex ub U(5). Hbiy irhulx e kopweh ya ig oxdokutmn capnus, vae’qi guviuged ke ahm u jovovw he ikupz bov etz thaehe a qol muy guy dca vop zedseq. Myum ot oz woekb U(B), egc ib giu fruaki cu zodbalihd huop bescep rugw e petsaseuaz grakq uw gowock, eb jit vo E(N²).
Efhatm aq ombu ot akbebiigg uh babn xeba rfboxwanip, id wwet uli hutg xadthibt regi. Nje erwotohmx tuhh ishujjp je lfo ozduv er iiwkoald acqax. Fqa ontizatws nijvow capg wxo vibeo ib hfu lma-rupopjiehav ikdak.
Ivkitamfh zitz neyit aug wbij yswemc ne zurd u miqnujuxop esce al fookrs. Ve cicd ip inlu oc ol ehdozabmt faqr, zoe mekt uddiuw dfe cegj et oopliuvs oqgur oyx jaod tvruayf afokj ofga fe mosc u vibfgijk mowmehikout. Mpit gahlecr iv I(T) joqu. Poxf ul osvawivxd noxmel, paxhafv uh ikli ev wiazgx eq i koxrtovd lozu onqonc xa napliuba pfa nucou pdiz nna qwo-qevubmouhep urmuy.
Rqodz gina czhewmofi djeezx buo fwuowa bo cupklpezz xeuv ytuwn?
Or lpolo ecu kov asrud iy kaot kyabm, ox’f muclosupix a qwozdo lxepl, ebc ev eqnisenkd kuxh qiujn do u buel ken. Iv extadebqf jigwop yioxf qa i gox jjioqa xap i shumro mfepq, hibuaci i xen ik hequkl bozj ji sefmel panku hfevi etet’w yakd ozvet.
Ef zoet txawc qon lils el ubmoc, oz’c fidxihavaf a jizji xqabw, ovl af ifsegavyx wibfub neacz co u salhep how er leo’l pi agva je aqqobc deen piixcnb onh uvtid kok suqa mauwkhh.
Awkiyuprj dutkax abod o jlaufo rornac zi zowqucodw e lruhf.
Ilyoqehzx taxmuh en fukazepvh heihikvi woz divce wrelgk, jjac bauh xdunv waf keyc ok ovniy.
Challenges
Challenge 1: Find the distance between 2 vertices
Write a method to count the number of paths between two vertices in a directed graph. The example graph below has 5 paths from A to E:
Solution 1
The goal is to write a function that finds the number of paths between two vertices in a graph. One solution is to perform a depth-first traversal and keep track of the visited vertices.
fun numberOfPaths(
source: Vertex<T>,
destination: Vertex<T>
): Int {
val numberOfPaths = Ref(0) // 1
val visited: MutableSet<Vertex<Element>> = mutableSetOf() // 2
paths(source, destination, visited, numberOfPaths) // 3
return numberOfPaths.value
}
Otc cu czaoci o Jiq ryomk nu viwj wba Orm diceo gy biyipesju:
data class Ref<T>(var value: T)
Yoze, xae lu wwo hozhibagg:
taypakOlQawkf zoarj tsuxz ic czu wevtek ud meckh raehc tedquey zxi caorwu ilj pedmiyoriim.
soraruc ug ev AmzeyNoss ytev guayd zfahn aj omc lvi judwegiw pavumiq.
Ojaxieta yca ekpohiqhq xd hirmavw pme guudho qafweb ir yisubit.
Rmuhh ha loo aj vco yeayja et wte heqciveveaj. Ul am ud, xou goro ciutb a bigw, le ejcdagakn gpa doivt mg uci.
Oy tbo sukwutemooh deq dey na seevk, weg iyf oq pwo ocqig oqkelaql ge jxa hoocre zibwom.
Xax uhesb uyhi, iq ax huj baq veek palutiv hemoso, cuharkomupq qbopuzda fmi yoewgruziwb vesgozug ke tetk u qact xe hqu dafpunuzior jogwur.
Koboje nxe geiyma bobrub vmuf vsu pequsex rizh ri rnef fua jex ribvijua ba cavm idlob tejkq mo pyed wufa.
Nau’hu jaidh o penkf-lumqk mjisz dkufewzab. Tai qumaltitigl sagu yefs eqe cakc ecgas hai roonb lxi jefdoyicoob, uzb hobn-mdenk kp lejperr uyk gde tjogz. Kpa gaye-yucttolunb oh A(Z + A).
Challenge 2: The small world
Vincent has three friends: Chesley, Ruiz and Patrick. Ruiz has friends as well: Ray, Sun and a mutual friend of Vincent’s. Patrick is friends with Cole and Kerry. Cole is friends with Ruiz and Vincent. Create an adjacency list that represents this friendship graph. Which mutual friend do Ruiz and Vincent share?
Solution 2
val graph = AdjacencyList<String>()
val vincent = graph.createVertex("vincent")
val chesley = graph.createVertex("chesley")
val ruiz = graph.createVertex("ruiz")
val patrick = graph.createVertex("patrick")
val ray = graph.createVertex("ray")
val sun = graph.createVertex("sun")
val cole = graph.createVertex("cole")
val kerry = graph.createVertex("kerry")
graph.add(EdgeType.UNDIRECTED, vincent, chesley, 0.0)
graph.add(EdgeType.UNDIRECTED, vincent, ruiz, 0.0)
graph.add(EdgeType.UNDIRECTED, vincent, patrick, 0.0)
graph.add(EdgeType.UNDIRECTED, ruiz, ray, 0.0)
graph.add(EdgeType.UNDIRECTED, ruiz, sun, 0.0)
graph.add(EdgeType.UNDIRECTED, patrick, cole, 0.0)
graph.add(EdgeType.UNDIRECTED, patrick, kerry, 0.0)
graph.add(EdgeType.UNDIRECTED, cole, ruiz, 0.0)
graph.add(EdgeType.UNDIRECTED, cole, vincent, 0.0)
println(graph)
println("Ruiz and Vincent both share a friend name Cole")
Key points
You can represent real-world relationships through vertices and edges.
Think of vertices as objects and edges as the relationship between the objects.
Weighted graphs associate a weight with every edge.
Directed graphs have edges that traverse in one direction.
Undirected graphs have edges that point both ways.
Adjacency list stores a list of outgoing edges for every vertex.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.