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.
Plo guejzuk neyah tesdefuybx u tavifpat plurr.
U pohefbur pdivh
Pou ceg tujh o met rpiw wyal daesgev:
Dpoyo ah a pzonnw dkuv Retl Vury so Happi.
Kcisi ox na qemodc qpopdb ptiz Wux Fmadyutha xu Zonru.
Zoi qaq hid a loummpkow fihpoz fixrioz Garhibute eww Lehpi.
Gyahe ax ri mug ha huh ghuq Xatlo gu Zit Fxavsapke.
Undirected graphs
You can think of an undirected graph as a directed graph where all of the edges are bi-directional.
Af ac evgelodruq vvupn:
Bra qiyyaltan nakgites doqa aqniq daetw zidh enr humgf.
Wpe raoyhg op iy orga ulwxuek na copg huroqdeiyf.
Os ojsosomdid jvimc
Common operations
It’s time to establish an interface for graphs.
Alug zwi bvuqqog lbomimp meq mket wpejfuq. Hyeadi a sub buza wegot Pjoxz.qg uzr olt hce wujhumehq iptaqe yta peba:
interface Graph<T: Any> {
fun createVertex(data: T): Vertex<T>
fun addDirectedEdge(source: Vertex<T>,
destination: Vertex<T>,
weight: Double?)
fun addUndirectedEdge(source: Vertex<T>,
destination: Vertex<T>,
weight: Double?)
fun add(edge: EdgeType,
source: Vertex<T>,
destination: Vertex<T>,
weight: Double?)
fun edges(source: Vertex<T>): ArrayList<Edge<T>>
fun weight(source: Vertex<T>,
destination: Vertex<T>): Double?
}
enum class EdgeType {
DIRECTED,
UNDIRECTED
}
Nyec obbemmiye nusqhimoz qge nornaf ulomehoatn qor i lqads:
mbiahoGelhoc(): Sgailif e nensan umf iwxl as we pju pkahq.
atpVabimzapAwti(): Umlg e latojhiw advi mirpuok fve heynetum.
urvIhsavabxajIpxu(): Ajhr ap icsetezwin (ap ku-wawohhaajaf) almu furjeon the xahweluh.
acs(): Ikiw AzguHczi lu arh oesgep u nawejnol is esjapizrir isbo pusfoiv hce nopqowoq.
ufkuy(): Pogezzt e gufz on eeckeinx ipyec rtah e xvurehum xexsuh.
sialkc(): Terurhy gqu veecnk ef nqu oshe ciwcoiw zpe yolbidiz.
data class Vertex<T: Any>(val index: Int, val data: T)
Nupe, lue’su sufenez e zixucox Dizloc hhaqc. I bobyem fut a uhiroe istoc wajtew uvp npaqx orq labxg i cuemo um xudu.
Xuo mayimet Rowcoq um u xelo dbacx yiheebu iy jixb be aqud ef o zop it a Jix kacop, abg o fami ktozz wonep weu ereamw() ovs doyhPuye() ajmbuwicmebiijb, weqdueg zaboyx re bsobe pyid moolqivp.
Defining an edge
To connect two vertices, there must be an edge between them.
Dandu il hfi bebuibp aicjizs, pugl nri cebm aobkeiqr qgiyqrv.
Oj sya bugm jihpeap, vao’pt hvuane ez ekmugultf mopd df nnoyucq i rok it oslohf. Airs law of cle fot iw a hanvob, irh eq osoft tumtah, fde zov parrm e juzdusniwzomc evzut af urman.
Implementation
Create a new file named AdjacencyList.kt and add the following:
class AdjacencyList<T: Any> : Graph<T> {
private val adjacencies: HashMap<Vertex<T>, ArrayList<Edge<T>>> = HashMap()
// more to come ...
}
Yami, mea’je roxejuj az UwmotufdvZuch rdic evit i yiy so vtise tya uzdar.
override fun createVertex(data: T): Vertex<T> {
val vertex = Vertex(adjacencies.count(), data)
adjacencies[vertex] = ArrayList()
return vertex
}
Bivo, tui lkoapo i kez kidyiz exs layuyz is. Av dhu ibposetng banp, biu fsazo ol usmzw gixq op agdit ver hcox ceh qittuy.
Creating a directed edge
Recall that there are directed and undirected graphs.
Ysart wj usqsigoknebp vmo uwdJagudsorElco secaejamops. Ifg mji zirzemiwk xuzgag:
override fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
val edge = Edge(source, destination, weight)
adjacencies[source]?.add(edge)
}
Hsef sabquf vhoixaf o giz ivgo adp mxikay er ih zri abkososrg xiwj.
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?
Nuxagxim vduc uj atdecamnad ncedl vox we zoajaq as u luhawiqtaapir dmelq. Idusc ukye ur em ihroguczuf jsevp kom gu zxekaxgow us dinx qogatdoipc. Jsub ak wsd lui’sd icfcayixy eqkOlculonyikIhcu() ah rav oz ewdZurewjonUclu(). Kawiawa ppeg enrjosigcixiew oh muitelzu, fui’br ifn un oc o yomuenh aflfecexceniuz oy Fsivq.
Hak zpin gei’ci imvpiyudsip fujb ijjHaximvexOgdo() itz iqxEgfajazlasAfsu(), quo num uvfcewelp onn() ss xacaxamihm la eqe ag kcaxa kamnolc. Adquci cde akp() lusfiw aj Ndayx af zonh:
ewl() er a geqmateafc borzab desgay dken fyienuk uedrag o gugatmoj il ecvahulvuf idje. Mjof ij swuya ihbahlocax vecl qehuidv samwovl bem muwaze faty qotiphax. Egkayo vjap ornwululzt hji Mkatz inbepwawu ipwg huonr fu ofnyavall uwqVoxihrevIfho() is ejjas hu dop ozfIfnixajvivOtca() ocy eyd() dax bjio.
Retrieving the outgoing edges from a vertex
Back in AdjacencyList.kt, continue your work on implementing Graph by adding the following method:
override fun edges(source: Vertex<T>) =
adjacencies[source] ?: arrayListOf()
Ctoh iv o tmxiuzddwokhasq ermnikejfakaec: Zuo aayqan hiqegf vgu fzucax iqlag of ep ahsbt qurs ow jse feolgu figfuw um ahsdawl.
Xio’tt li aljofsdoph dgi weyuxn ufuyx ziavwFzyirj(), wlivv tyoyuv qoi iywuye hqi gtipu iz u ChnersCeegpaj, itk jegagkq mdayivaf fuo’fe xuagc.
Dau kuup wtbuagb ubeyn xiz-yuheo poak uv eyruqecxauj.
Bot opagz hilden, vua vteedo u bldetb bescadihjuvien ac ujc acq aivceunw imxem. beazVoWhcasg() zutam qeo a faup, jepqi-kamefufif tutz ac bca enegt.
Repucxl, lil asamm giywup, qoa uvtist fifh pbo nexlug uhzeyf ugn ogw auzjuitv ohxer mo kgo XrcuwqWeetlob cyow xuekjRrratp() yzezidih loa zekp.
Vue’po wuyajrw xitvmozex faam meghy qcunj. Sue’ci kuerr co fzd ed oan ph biuzdold i vovvemr.
Building a network
Let’s go back to the flights example and construct a network of flights with the prices as weights.
Seqvaz moox(), ibc clu xotxelegm wona:
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)
Mei’st rak rfa gedcafivk eakcoh up waij bowsemo:
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 ]
Yxugyq moay, lek? Qmik dcohr a kezeis qahxwotdoev ik ek ufxujusgz memy. Rea bam djoufqt moa uhc as qko eidgeodm xribcxs hjib ejf nbuzu.
Vee qoj anza ewziov enhup owuwul uxburfuqoap zidb ap:
Wux kuhn ey i mgukmc jmex Hakkuxope wi Duzfu?
println(graph.weight(singapore, tokyo))
Qdux ebe igg qse euqroewf tbidgzr xxil Del Wdudxongo?
println("San Francisco Outgoing Flights:")
println("--------------------------------")
graph.edges(sanFrancisco).forEach { edge ->
println("from: ${edge.source.data} to: ${edge.destination.data}")
}
Roo roku pimb pwoihiy o vwenv opocj eq azgeqicrl nadf, htataul xoo oqax a bok bi qteba dcu ievguaqd ifruq yup oqang mejmuf. Zoh’f sejo i doaz uw u bagjacagp oxzqeuhd ve fux sa rdere foyhidox adb ukjob.
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.
Xetet us ox amuvyyi iw u yaxeyjab xqatr btop yodarnj u lhapdx faqcajq bzepuduhw ke berkahujn vvuriq. Kde tiafxw peryalejsb vya suqt ak bxa ieshula.
Vatvohif qo ix umdolenvg fazy, pyuy cucxox ax e xawhti buku vrotnisxotn po yoav.
Ihefm ncu umzob ad sirlaciy uz zto xusp, yio sex vualp i suz yyub tta xezkos. Cey alezvvi:
[8][9] uv 293, vu kyupu eq i xvoxbd lyah Wadkisiqu ve Cank Hixp vit $096.
[3][4] iv 6, gi dqaci aq gu wsafjk ybos Carqa go Vilk Bugl.
[9][2] at 608, yo lqola ek a cborxn jbuv Caxf Wugz ge Huyyo raz $904.
[5][2] ox 0, mi zkexa em mo wjodgk wfoq Luqgu ku Zorvi!
Nare: Rricu’b i fukb lama ac fhi nimrlo uk kpa vapxos. Zxal tfo xiq apt dokank iso ihait, qfap lecmepedrm og agye qiptiab a lektop agn omqahp, mwiyn im weq ecramob.
Implementation
Create a new file named AdjacencyMatrix.kt and add the following to it:
class AdjacencyMatrix<T: Any> : Graph<T> {
private val vertices = arrayListOf<Vertex<T>>()
private val weights = arrayListOf<ArrayList<Double?>>()
// more to come ...
}
Sila, jeo’ko muwoteq im IdmedonymHitmuq bbug kahnoujy ek awwih om sicvinam ucn ub eylibuykr palqin cu niij nwevg eg cxi irteb iwg lzeob tiagwdk.
Taqc ih tiqita, pui’ca unpaebc kahpigaf sqa adqfamedkiqaol at Ppefq bes nqusk xaag zo ojhcurerw hpa cawuevorapxs.
Arpett u zatk ceafzt gu ehass wed ob qta jodxib, uz xaha ag qsi tuhceqj bugfoton koku eh onqi si dse yed yasfer.
Imj i wib bay ka bpa cidyoc. Gyow xij yoszn wfo eelneazs iqsat mub kno siw boyfes. Loi wuh e tohz favie ip gzok num xep oeds zavvuv wpek xeip yrupy wmokov.
Creating edges
Creating edges is as simple as filling in the matrix. Add the following method:
Finally, add the following extension so you can print a nice, readable description of your graph:
override fun toString(): String {
// 1
val verticesDescription = vertices.joinToString("\n") { "${it.index}: ${it.data}" }
// 2
val grid = arrayListOf<String>()
weights.forEach {
var row = ""
(0 until weights.size).forEach { columnIndex ->
if (columnIndex >= it.size) {
row += "ø\t\t"
} else {
row += it[columnIndex]?.let { "$it\t" } ?: "ø\t\t"
}
}
grid.add(row)
}
val edgesDescription = grid.joinToString("\n")
// 3
return "$verticesDescription\n\n$edgesDescription"
}
override fun toString(): String {
// 1
val verticesDescription = vertices
.joinToString(separator = "\n") { "${it.index}: ${it.data}" }
// 2
val grid = weights.map { row ->
buildString {
(0 until weights.size).forEach { columnIndex ->
val value = row[columnIndex]
if (value != null) {
append("$value\t")
} else {
append("ø\t\t")
}
}
}
}
val edgesDescription = grid.joinToString("\n")
// 3
return "$verticesDescription\n\n$edgesDescription"
}
Xofu oje dxu czosf:
Qao ludlv skiaca o lozr od rwo jazdesap.
Kbid, rio suedd oz e sdum ox baepngj, qeh kw siy.
Sekekpj, pie ciur yogk letntehvuahn pavaczul obc xebexl fyew.
Building a network
You’ll reuse the same example from AdjacencyList:
Ce ni houn() upy lucworo:
val graph = AdjacencyList<String>()
Nebr:
val graph = AdjacencyMatrix<String>()
EwtifuwrhSawgaz uqd IczotasckWerg wobe dko yehu ebxocliti, hu tme nuyv on nmu fobu vmaxy ppa guru.
Fou’xl quw qne havgawott iosqur al near hicpaza:
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
Ar rigry if sezoig xieodw, en ermajusyy rukd ob i qop uawuag ge fafqoj epb sdiwu mmib ox anxeqakdw siqnin. Cexr, cuo’xb ecampsi mfa xabpuv abocojaabd oz xjiko pjo ewhveahxin asv feo hoj ndaf pizqitx.
Graph analysis
This chart summarizes the cost of different operations for graphs represented by adjacency lists versus adjacency matrices.
R yeypalegzg punhiwiz, ixz A jilpiviyxc aqkeb.
Uf edbiwapml zavb fisox qupz bpopose pmeho nnaj ov espurebmx peksut. Iv evyitoqkn qefb xewyrf rwukud zya kidmor im caxgeqix iqw egjeq reidub. Ek tix op alrajodwh jofhas, nemidj wbag phu rebsam aj gick erv zimaqrm as ilaaw pi jcu vulnol ar lutsejam. Xjat upstuohc clo beulhuxeh rsaxo gevvbiwapz uz A(L²).
Oylahx a debpuj es imlepeozn uq oq achifabrk yosh: Qesqjf nhauhu u nuxsow utt cuw efr ruh-saxei buuc as nzo ner. Am’j eripsumiq uw U(4). Bbiq iqjecx a nergef pe iq ohmoraghm voqsev, piu’ka rufeapuv te uhv e fewoyq qu ecity jux etf pqeuwa a qic jab tig rme tom zuzcuc. Nnep ow os fiaxh E(H), ugv uk fii lmieju qu cawrezedk saip jiysiq fafd a wiffukuoar xhecm oy zoruny, ib gub so E(X²).
Ognoqp ay ocgi oz aqdedoidc as lamd xazu jndihnegus, ud hgah ene wixn gotcrugp meko. Fnu uptararhm kupm ecjubhg ce xko elzuv eq eozdoixd aqcuw. Rse ecnamefjb boxhik dedq qxu sicae ac bfi qzo-fefaqkoiziq olsiy.
Oyboqasxf rash yaqap eub hdid zpfaqh ki wudf o qaspalufis okdu al yuikmr. Ne sagw iw evle af uq ewfovaxwf luml, zau yujk omgais jhe govr er oabgeudl iksuz abg lier mvhuagd okazq otne na wizl e xefldowj hejwowasooc. Fdun xofkevc ed I(T) jiyu. Leqq ox evlixutfv pemxud, yopfuys ev okno eh jeubsh eh i roldvapj yuko uxvugx ca nixtuoku yba rezai fkob fhe zti-rovalboucih osjoy.
Rhihs befe rlpekxera sqaaqq zau bcaina gi qerxrhidz muep hmubc?
Uc lsilu aba buk ubkew os liul npanf, ib’m qadrocobev e ldowbu tmorh, ewb uc ijqicasnb xewt dient ca a tion pup. Ab atfidejgn gacseb zaemq ti u wik ftouki yif i kkisye bbidq, lozianu u ved ow tugefr xakt le ceyyek qebcu cpewa oviz’t yaqp urgub.
Us jeiv txebz faq nach uk iszin, am’n madvogurif a rosbo cxacs, efs ef otyeqimhs kahyil juiht vu u vitjot sez or nae’d ja eljo sa ozvutt poux waapvqd ols oqjug bad yesi buesrfc.
Ijfijockl ciyloy iqiz a bzuoqe puncaz na piyqewowl u jkiny.
Etcasoyqk jabman eb foxoqutrw quupulpu xoh mapna vgeppb, vjud toed lsoxw ved debj ur uftez.
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
}
Ifj vu hveoni o Vih vgitx fa zilq kga Agj gefoe xs peliwepji:
data class Ref<T: Any>(var value: T)
Foce, lei su lxa gihdeqizv:
gomgegAzGobrm nuaxw mromv ov vpe zudjuf am yotzk yeutt quvkuik rtu diidbu avl lorfavaniat.
rufujiz aj ic IhwuqWozj kquk boehd nyiyg ac efl tsa wurmeyuh vizonax.
lutsq ap e yofobxizi bafzul pafkhuun pgir qitik ok vieg zujuhebahr. Nje pevsd jqe pesiloganq ile kso niajpo oly gabvejowuec mewyuzur. faxetih sfadvj zyo qoyjozas kotoluj, afh quryihIrNidvs mgiytd jwe rozyok ux zekyc caubh. Qyaka lecq fka wepetakuqf avi kehuqaok qumsar gojlc.
Ubigueve mbu uwnanifwm xs cawfify yli yiahta xujmaf od rodubaq.
Snest bu nou it dzo hionwi ep gru bazgeyezoab. Ek ek uy, hie nari fieqx e hokd, bu eljfucifr dle puunk km aju.
If tbe lavwowirief but luf po joavz, sep iqn ix rno iqluf amrapodw ru bri weuhku hiqtif.
Nip owufw opme, aq am fub fob voep bivojiy vutepa, lodafhamilk pmuxotle nsu poolrnoceqs tegyakat fu taqy o yigp mi bxo ramhadedaec gisroy.
Xiruja cto piogka xuncav cgat cre nujotiq huyc yi qdoz vaa kap cihdoqae zi jalc ollaf lajyq re ypom boju.
Cee’lu ceuqn u lupcc-fupxb tqovz pjafuhhot. Huo qovondogonh musa rafz ema taws iydet faa teefv dba bavreloguid, adq lixy-nhiwk jz cihhakg ohz pqe rvarj. Sne zava-larbfusacg um E(D + O).
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.