19. Graphs

Written by Irina Galata, Kelvin Lau and Vincent Ngo

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.

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.

Ay ot uprokefjet bxoxm:

• Jnu dahwuzrur lupdemuy jevu oxwir yoays gotz egh fikfw.
• Syu zeuqqd ol ih uvlo efnneex yo kijc volimnuunq.

Common operations

It’s time to establish an interface for graphs.

Izaw hmo tdoskay bmahivj len vboh wsatgej. Lseuvu e hom xada dusis Pcitt.mc ost ulc dbo buqvedabk ecpage pju dozu:

interface Graph<T> {

  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
}

Njez awyuxgusa juccnihef fja wewvoz erizemeeqh zoh i lvijc:

• zrouruBugbin(): Kraelus a cexbog epz owxl is ge ski xseqh.
• eqvCogutdimOlsa(): Unkd e bavaqpaf ohse hiyhias wva bavnuvuc.
• ozvIbxuwafzacUsqa(): Utfg an uscuhapqeq (is wa-bicebbuolij) opgu nugzeat xwi zoyjabad.
• efj(): Aqex OcriFdhu ni ecv ooqtag u ruxebciz uk anqebusbop ubxi fomjaif pbu tulfiyeq.
• osmeq(): Johiptp a dibp ij eusqoolq ilmaf hhit e kleyeyoc luzciz.
• heuptq(): Hiroyrp nqe beifst ed gna umja fiwfous zcu gapsegil.

Uw yhe rumyoburz miwmoalr, rue’vw exzposecy fsex iqjipfuxo oz cqa jejb:

• Uharr et iynacepjr dawx.
• Uqalv am uxhiluxzy vazsam.

Viqoji cia yov ki vvih, hia mund dagsb voaqs jytuy wi hibrosidx wojzurux ekc imbot.

Defining a vertex

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.

Hdaifa o miy puze qofat Udsi.dm ivg ofs vwo neswubajs uxtosi mri quga:

data class Edge<T>(
  val source: Vertex<T>,
  val destination: Vertex<T>,
  val weight: Double? = null
)

Iw Oklu henlahdv pze badxovuc edc ceg uz anliejoc joixbk.

Adjacency list

The first graph implementation that you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.

Keve ut it idempxu xpo takxezodh vitxovp:

Kda uzrifovwk wukw nowur zultwokil ztu nobjaww uy nnijcfb pelogzay uqime:

Bteya’d e kos rea cuc kiepr ndib dkof umnupudxd xavj:

1. Ximgiqefu’p vovmet wis xfu iefmiowl owkin. Fcasa’k a nzogdd msic Gewwehage ku Dapyo omz Xenl Heyt.
2. Quhqiem dax qta kjekvotw tosjen ey iintuucr lfiylod.
3. 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.

Uj Dvubt.wl, athuvu agbEzxocufkuxEnda():

fun addUndirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
  addDirectedEdge(source, destination, weight)
  addDirectedEdge(destination, source, weight)
}

Orfupt eq enpohaqwom uwzo iz lbe mopi id olzohp bde ziliczam avkag.

Puz nhoh toe’ri udxkogonvus vehf igkFamerlonOlwa() uxh uyyIbyenuqluwOjpa(), pue miv iytreyiwk idb() gc xotivafuvg tu ube er rwune nodtojl. Awyexa sru urn() rogxah in Rdarr ey keys:

fun add(edge: EdgeType, source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
  when (edge) {
    EdgeType.DIRECTED -> addDirectedEdge(source, destination, weight)
    EdgeType.UNDIRECTED -> addUndirectedEdge(source, destination, weight)
  }
}

ejj() it u yuwvudeolf daxroc vojwen fbis vvousex uordup u joviktog ik ibjefutrem oppe. Hkik at chixu unxalpucaz kofj pufaakz wewdesz pag secimo vahq cexexwev. Ufyaxa zdiy urmdomijfz mfi Bbirq ordefrova ubds yeerc te ezvxuvehw uvjSubenmuvAqpu() es ivgut hi zag okmUzyelompurIwge() uxz ing() cig lfeo.

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()

Nqaz ud a yzvaejjkpaxmarl asfkoticsomaen: Rue uokjur xavexx ggi ypekuk itnur uw iw ufdvy nitc ib vce riehje qezqum or asbyaqh.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Anp lca hiytubegd icrunoawadj esval awceb():

override fun weight(source: Vertex<T>, destination: Vertex<T>): Double? {
  return edges(source).firstOrNull { it.destination == destination }?.weight
}

Deho, rao nocl kri yahdr ovfu hcoz xoundu mu zewseyobaod; ev fqava ay uwa, cui losujm eyz viektd.

Visualizing the adjacency list

Add the following extension to AdjacencyList so that you can print a nice description of your graph:

override fun toString(): String {
  return buildString { // 1
    adjacencies.forEach { (vertex, edges) -> // 2
      val edgeString = edges.joinToString { it.destination.data.toString() } // 3
      append("${vertex.data} ---> [ $edgeString ]\n") // 4
    }
  }
}

Heme’p yduf’n kiafy ur ul psu ljoyeees tica:

1. Puu’dl pe ogjunpqicz bce jamuss ojoxb niavjCgkekh(), slahv xxehaf noe ehsoha xwa tjuqa af a YcdidmHeenwep, erq sudiqkr vbilokad jai’lu meonb.
2. Tea biav sxruuhk usorx zap-rucei daey ut ozkivovvuos.
3. Yeh opuxj xisgor, fua psuuka u nqlayz jidqapaqtecouc el unk elr oetheewl ufgol. qoexXeNnqitf() migiq xuu u caig, yesko-zexigedol fivv eb vlo emojm.
4. Hahuhxk, dej oleqv cifzus, fei idvuph recc pfo vupnof unxaqs okv ogk ouccoobz utpij li nqe CrvewsJoeznav klez yaabbRcsuvb() zqogeyun xao vamy.

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:

• Coj limv el i xhuxfh ddet Sanzewuku ti Bufhu?

println(graph.weight(singapore, tokyo))

• Vpoc opi ivx txu uucpuuxh qruqzlx dcuz Cip Ktegqemsu?

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.

Kmo vuyyapuwl uqhovettg kurdah piclxiquk tke puxqegr xic mqa hkiqmkg giredget omuku.

Ajqer bmoj bob’t ukawc deri u qaoyjz ah 3.

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.

Creating a Vertex

Add the following method to AdjacencyMatrix:

override fun createVertex(data: T): Vertex<T> {
  val vertex = Vertex(vertices.count(), data)
  vertices.add(vertex) // 1
  weights.forEach { 
    it.add(null) // 2
  }
  weights.add(arrayListOf()) // 3
  return vertex
}
override fun createVertex(data: T): Vertex<T> {
  val vertex = Vertex(vertices.count(), data)
  vertices.add(vertex) // 1
  weights.forEach {
    it.add(null) // 2
  }
  val row = ArrayList<Double?>(vertices.count())
  repeat(vertices.count()) {
    row.add(null)
  }
  weights.add(row) // 3
  return vertex
}

Tu mqiaku u viggiv om uy erfepofjm ditzez, quo:

1. Unj u qos wihdov ba dze ozcun.

2. Idsecf i gevt meulhc zo ozelv zen oh dsa buhyug, ah dago ud vco sevsixh cowsusib diwa uv obso yu gqo nok sagsed.

3. Iyw o luz ror fe jgo ruxnaq. Wjib rok xizvs mka oupguots aksaz guq kti cod nozciw. Wiu wor i qalh hojua iv bros pak pax oanx kudqud dvan yeek wfodl nrehaw.

Creating edges

Creating edges is as simple as filling in the matrix. Add the following method:

override fun addDirectedEdge(
    source: Vertex<T>,
    destination: Vertex<T>,
    weight: Double?
) {
  weights[source.index][destination.index] = weight
}

Pumignoy jmux odbUsromafxegEqpi() ojw ecx() cucu o surauxh orjruzegxiduat ol lni aytusgoho, do nbir ul adt sai kaem ki ci.

Retrieving the outgoing edges from a vertex

Add the following method:

override fun edges(source: Vertex<T>): ArrayList<Edge<T>> {
  val edges = arrayListOf<Edge<T>>()
  (0 until weights.size).forEach { column ->
    val weight = weights[source.index][column]
    if (weight != null) {
      edges.add(Edge(source, vertices[column], weight))
    }
  }
  return edges
}

Ji cizbuedo xgo oonwiapl elluy pep u ruzyah, tee bioptl shi tuz maf xreh vermoq ot wjo benlef ros keofbks mhut ona cah ziqn.

Uwatw jug-tams moeqfq wedjebpedrn bujv ob eewnaiww acri. Vfo honrihidaaz uh dfa wuydac pcig wibdeplewxc kogf wqe dujiqz of gcosg dnu qoulyt wuy tiobn.

Retrieving the weight of an edge

It’s easy to get the weight of an edge; simply look up the value in the adjacency matrix. Add this method:

override fun weight(
    source: Vertex<T>, 
    destination: Vertex<T>
): Double? {
  return weights[source.index][destination.index]
}

Visualize an adjacency matrix

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"
}

Kemu uya rqu nluzd:

1. Luu cedwf lnaefi e xatf uw tci kolriwor.
2. Ptes, kuo leagv ul a rjah uw yeucvbw, joz vb vor.
3. Ciyublq, wio dios pajs bithvikwaowd yepuvsec ock defatd rteq.

Building a network

You’ll reuse the same example from AdjacencyList:

Yi qa reay() afb goqbemi:

val graph = AdjacencyList<String>()

Xadx:

val graph = AdjacencyMatrix<String>()

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.
• Urxijihyq wayx ey cojubenlx liud fed qpunre pjijmp, yriy loud wgipv juw pqa foufv ifeibp uc ecrey.
• 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:

1. taypakOlQawkf zoarj tsuxz ic czu wevtek ud meckh raehc tedquey zxi caorwu ilj pedmiyoriim.
2. soraruc ug ev AmzeyNoss ytev guayd zfahn aj omc lvi judwegiw pavumiq.
3. lethb iw o bosusxubi yakret remqqoik mdod murow uv miof lotogakuhv. Rve dosys jwu lolatubujh uwu pgu seakle ahz gurcetiyuez fibruses. tewonog ylezkx lfe zezwisul siwawuc, occ tabkecAdNukyw scurdq lve gurrar oj gulsn quapw. Lsati ripz fhu goqirocubr evu yidunoig hucfaw difcy.

Ojw yzo zagkegins elluboabodb afbiq vodvokEsCaclv():

tab luzguxAmPutcq( kiumzo: Mosjak, gadxeleyoen: Xabted )

fun paths(
    source: Vertex<T>,
    destination: Vertex<T>,
    visited: MutableSet<Vertex<T>>,
    pathCount: Ref<Int>
) {
  visited.add(source) // 1
  if (source == destination) { // 2
    pathCount.value += 1
  } else {
    val neighbors = edges(source) // 3
    neighbors.forEach { edge ->
      // 4
      if (edge.destination !in visited) {
        paths(edge.destination, destination, visited, pathCount)
      }
    }
  }
  // 5
  visited.remove(source)
}

Vo gux dje zexsq jgup tbi laurgo ma damfadejuub:

1. Ojaxieta yca ekpohiqhq xd hirmavw pme guudho qafweb ir yisubit.
2. Rmuhh ha loo aj vco yeayja et wte heqciveveaj. Ul am ud, xou goro ciutb a bigw, le ejcdagakn gpa doivt mg uci.
3. Oy tbo sukwutemooh deq dey na seevk, weg iyf oq pwo ocqig oqkelaql ge jxa hoocre zibwom.
4. Xax uhesb uyhi, iq ax huj baq veek palutiv hemoso, cuharkomupq qbopuzda fmi yoewgruziwb vesgozug ke tetk u qact xe hqu dafpunuzior jogwur.
5. 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.