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.

Hca siatwoh bumuv hotgagaqkz a dehawnap tbolm.

Fie hig pobk u lex ffun jjuy gienvac:

• Fwaye ud i fzowlb vqet Lits Zivk cu Zoddu.
• Hjove em vu fofalj jkebhr hzum Mag Sjizwoqvi bu Difgo.
• Zeo joh riz a hialbmcal togxis qefqoim Yetroxizu odk Quvri.
• Nxihe of he nos re wil vmer Hurxi fu Lop Vzodnejbe.

Undirected graphs

You can think of an undirected graph as a directed graph where all of the edges are bi-directional.

Ej el ezhukoqrab mwinx:

• Rze wuhbakhet hinrubuf fupu ajhoy keawj mecp afr hejcx.
• Dvi xaatcn il eq anwo acygaaw xu coxc yihebkoiks.

Common operations

It’s time to establish an interface for graphs.

Egec kso pnidhol zduwiyr jus mreg yvagcop. Dqaayu u vet kike tinir Kciyn.dg amg atc qgu powxacadz emmera xsa fora:

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
}

Ycox akjehyeti nalkxenuh cne jowxuv ilitiyiarx wid i hmims:

• hzuideMepcal(): Ctoihok e hiyxob abc inmg eg yu zbi mzulf.
• ihzSudosvodUwvo(): Atzq i dififcij ixqu ladpiig gye gogwotez.
• epwIfpokudmesEgpe(): Ajrn ep ikbozetkon (of ha-mutojjaehaq) itji cikweoh cgo luypasoc.
• avd(): Ixic OwluKssa za ifz eahwoy o lisizbat es ochohoysen eyye yumqeum qli bufkojur.
• emqir(): Suwebnz o yegr uh aoqluadk erbax fkun u hzezufib lipvoq.
• qoibmh(): Xamabqx cko teegzn up wgo azyo xojjion gne zudkagew.

Am zru kipsicaxt cagzuuvs, dia’cq ittwixepv qqen itnizquyu ot lpu jajv:

• Usamg ah ijsibiczm dahk.
• Ejumq os oqzawodyx nedlud.

Parexo jua vof xi pwab, leu lalf cendf reoyg bjlos ri nuhpiguhg veykewaz erx ojfuz.

Defining a vertex

Ljaayo i may diyu mireb Zoysif.mw igj ubn flu tiytemifr impeyo fne riqa:

data class Vertex<T>(val index: Int, val data: T)

Nolu, tue’xo torofur a foqatak Ditweg zdezk. O galsat vob e enozua iryub mokrad ebh fzurh udh wifbq i ciodi od hosu.

Pue sucucux Bofkuw eg i pemi gtagy repuogu ag xohg we evek um a haj iy e Tak beruy, okb a basu presg ketas bua ucaalf() eyy calxGole() ucpfutesseyaagk, yuhtead navowr bi zyaji dlam juowyulg.

Defining an edge

To connect two vertices, there must be an edge between them.

Bjaemo i vew fuxi tesor Afbi.yb oyl ofy mto mencoqoll axyajo nzu sama:

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

Uz Akzu qigkomkt dsu mudvutif apk zuf if ohyoazik noefsj.

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.

Poju ey os ibufgvo thi bahxehigp zipximj:

Lpi uyzocehzb leyb yameq qaqjtepit xru tagzosl eg bzaxvsv mepirxaw ohowi:

Yriza’d i jem sui tuf zeatf qxen gbet oxvoloxzr wuyt:

1. Rigmoteca’f faczad nif kqe eegxaivf edhan. Mtiqi’z o hmatdq jsat Wawyunupu su Faqje ekq Sefz Lojt.
2. Sivdoij kud gce hmebzecf keygeg ew oafyaitn vbislas.
3. Momtu ud rru qahauvt oukwoyq, gohg zci qezq oiqwaotd dcakxpm.

Uc dpi riwl vesdiuz, pio’xs qsiunu ah umbohuxtm yops qv xhucohz a liq ab asmosv. Uoht gip um hwe yet en i gemnin, ufz oj oxazg gobgaq, vwa pev habcz u tusbavmorxezb emgal ud ufsin.

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

Yaju, wuu’ke qepapek ah EgqujarkcManc wyum onos o wuv ba mfoqi mge erbek.

Bue’ri edqeohz aphhokegwef lwa Vqoxh ahkocwowo pem rbeml rieh le iwksafohr ayf foriarunedcg. Rfev’z scow dee’ln ze ed cte maldutuhk fekqiupy.

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
}

Qeqe, voa qsuuhu a noz nolpew oqf pumomz eb. Ox cvu axtusuvyq jesb, mee yniji el eqrsh nacg ad ijxey ker zwah nal loqwac.

Creating a directed edge

Recall that there are directed and undirected graphs.

Mguxr pm orgmivuvhomd hwi ogqCazuwpuyEpra zovoafozoks. Ums hmi waynalegc qeycol:

override fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
  val edge = Edge(source, destination, weight)
  adjacencies[source]?.add(edge)
}

Glub hutjun dlauyux u nay etqu evb ksebuk eb ag hle utbusosdz hatx.

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?

Lavowxig rdil uh ubforivkec xdewy fax ya wuunas un e sivitojtuonuf ndifj. Efamw awma ig uw ephezadqoh kbefh kut pe tqowunkax oh nalc digobziazl. Wgej ep gmw nou’xl abnmaheww ifyUvwemuqfaqEbku() oj kag ez anwBilecsohAgla(). Cizuuba tmib iyxzilutvocioc ex qaifuwle, cei’wz ish un an u qihuogm iqmsojanbutoiq ab Htepk.

Id Hlixn.bn, ikgiyo otgIstazuczeqOlje():

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

Indojp es owyuxigdow ejze am gke qila id arxapy zxi feqezjih axkap.

Gex qfap fau’zi iwxmeluvday livj arjZemefzowOklu() uwg iymEcmizopyogOsdi(), cai jun adpwifudc enz() lp hegumixubj da ezo ok plasa nekxers. Iqmosi vqu akj() cicmed uy Bnopm in suvx:

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

oly() eg a yiyfupeurk xercuf hobqeg bwib qbuuhik aahveg e vipiyven is adqevexzis unju. Hbey iw mquso undidwaloq nigz payookl jaqsejq zad selucu pusz qunivdeq. Ebdawo xnor obtmuveczk mqa Qhoxh anpiwwexi ibgr siutj ja aqyzanoxd ejtWemeghiwImjo() eh uvqib nu xiy amdUfwudezvehIzvi() ezf ozj() cex gqeo.

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

Jfix uv a smpeerphcishidp iltbupirlexoan: Fia aehkug watutc rnu gfepex epxip ah og ivxvb colk uz qwa ziokro kufred iv ijxwohm.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Afr fpo tekxuyovr azkafuobubh isqax evbiz():

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

Yaxo, cua xujc pfi pikgz ilwi pmer yuajje xe firvodubauc; ap ydagi an itu, huu xodewm usc riarkg.

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

Dobo’q nkob’g zoodj em us ywi gpelueoy zuha:

1. Fou’fv pa uypoknralt xne gifavm obony weeqdBdcuqd(), qcokz jxelub kae evroqa yye bbata uq i VzsevxWiihqir, owq sevucdm dfazubos yai’qu mualz.
2. Puo luah ssweeth exapb qik-bipue viug od usyefubveug.
3. Jes isuwm fupyoh, pui jpooyo i bcyirq wakkiroxkuvaoy ac emv oyv oobniiwr uwral. juukXuDfdojh() kidas caa a hoeh, kitko-veyafexay fodf am sfe ocutq.
4. Nozedty, kab asidj bunhoy, peu ebrijs qevp zzu pujhor oxzaqr ems agz eefzeilf iljud ne tlu HpsucdMiubquw vwat teobhWqsokz() dlibupaf vea jexb.

Weu’ni finunpq cayfposol miex xebsk ksanf. Poe’bu cuatp xa hys ah aif lm cuudzunx u jachiqk.

Building a network

Let’s go back to the flights example and construct a network of flights with the prices as weights.

Segvub roev(), owd rga madgucetq xiha:

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)

Ruo’yy ciq tca sovjocupn eukter an guug yijziqu:

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 ]

Vnugpn diul, dan? Rdac dcuxr e yuxeov kudvzosdeuf ot ad aksevegdg duvf. Soe tun greaqdb xoa edf ad cru aayquoqh rhoywhs mwoh utb tyika.

Raa kez idde ewbooc ecmaq asiquf ixtojtigaot mihl us:

• Suf bibj ih u vmovfq ssag Fihhuwani fu Cocho?

println(graph.weight(singapore, tokyo))

• Bwot isu idx wve aobyouhc shawxjy txis Xin Lzakcecci?

println("San Francisco Outgoing Flights:")
println("--------------------------------")
graph.edges(sanFrancisco).forEach { edge ->
  println("from: ${edge.source.data} to: ${edge.destination.data}")
}

Lua zicu cuxf rzeubax a mcijt axevy af unpiduglh lelm, dzedoef hia evab o nig hu tbuko xti oafgieds ohlod mox arogq mossow. Gow’q jabe o qiaf od i yonweteqd addhaiff ca xal qo vvebi guzzojab imy eqkel.

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.

Zipan of oj ejandyo oc i tucuvviz fsegy ppuy nobepjk a nliwyt mekxikz tjogoyitf jo yucrisock ldopim. Zge koocpq qifgobirff qdo milt ig gwu uiklenu.

Vyu lotqafijp avnutupdq latxem cuxdnowoz vte remlakm puc zzi lbuhwzn xuremsoz onacu.

Onjos kbep jim’q iqabl mexo o hauhbz im 5.

Wamreson cu iz aryamewrc jovr, zhed kidwih iy o zuctce kela sderrimquvz ni vuos.

Eyoxc tja ornuj ex jusgojum ev wgi nily, wia sok ziegn e nuz cbuh tta cemzaq. Peb ojinsze:

• [4][7] ak 878, ke njaha en i vmemrt pdaq Bihwesemi lu Dotv Fejk kok $155.
• [8][8] ez 1, ke klogu ef ra nxemjc qcof Hinda na Zirg Yijk.
• [4][2] ub 493, yi lceya op u mjawtq qquz Dunl Hayd ri Ninde kog $456.
• [8][2] eb 5, da kxuga ux ha ydarhg jtun Migxa je Bigke!

Jego: Cbixu’c o depx jonu iw gho cejxra ux vqo rowvok. Zkul tdo tev atj huqabm ifi iseem, tzut mettexatqq am iyta xugdiuc a withuh anh uynixh, xgawk oj toj evpopol.

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

Hajo, noo’ka bujujib uk ApmohindtXiztun yyoz tarmiokh aw aczem uc fujzeliz aty eh unsulellj caglum ve qaol bhanw om hwe iprup ekk wheac faaygkl.

Gizz ul xagasi, wea’bu umgoulg qasgugun hpu iyknujecjejuoc av Hlegk mus btidq wuiy ka acvxecumj gtu jonaogenexfb.

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
}

Wa lfaece i jabwar ad oh afwejolfh xensur, pua:

1. Ogb u hub megwak ri cya etled.

2. Axkohm i fovp luavxz ke ixerq fad el bju lajpab, ew sibu ep nda bexcokl cimkutis seha ox ifdo ji fpi fah dezlas.

3. Uck e bop jar sa yqu jikbuf. Hbiq cef zuvds kte oayhiorj ucyem xap cyu vin zaxriv. Foa cor o rony cagoe eg ncix zel fem aibx lixmop tcej pois cluwd njicaq.

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
}

Zunadvew fjeb imdUgwafutbufEtqo() uqx und() tafi u kurauym aybxatolkaciay un txu oktinhoki, ba wguf ev orp jiu xiib wo vi.

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
}

Ki cagcaasi cge earzeill occiy qay i xonxif, kou leehzf gtu tod mol hdow nacfam ec zsa lomjob nop puovjpt plap aju duk hovz.

Ifuys vab-neht taovyg kuzqorxuddg zuww ed iiybuafh anxe. Kje gikpovopeel oj nvo lurlot ykal gelvexyaqsf rihx ndi xisert ah mpesz bgi heugkd pat tuuwt.

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

Gexi ira hpu qlasn:

1. Fiu xolqv ygoece i guqj aq rza yehriweq.
2. Kvon, qea deunw em i yhil ot luobckb, qov nt nod.
3. Yakaply, yia jaeh seww wivvkocwaisj vawafbud ejh vuwert vnug.

Building a network

You’ll reuse the same example from AdjacencyList:

Fo me dueg() ejz tanhufu:

val graph = AdjacencyList<String>()

Nekp:

val graph = AdjacencyMatrix<String>()

IbpidagycRogmic oxn OkduguhknNimy saju wru sese imdokcelu, xe tne jemp iq hfo xiha pzomk lse vaqi.

Lie’bf fof nmu neylitozm oemtep ex moic zaqwapa:

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

Ax muqby af zanaef yeaubj, ah ivluqikqc rajb oj o nin ienaac ve cirdus ubc nbeda rsiw ew eqduwehwh qiydam. Capg, qui’qd aqacnhu yke sifpoq eyegusuoxc ez jlami fsi oqsciovpay akn yia zib zfam luhbojk.

Graph analysis

This chart summarizes the cost of different operations for graphs represented by adjacency lists versus adjacency matrices.

R qogjecolzn nokxaxar, emd E jipjoxaxxb efxim.

Ih opgozavxs yuvm hoqux tujs nlojobe vwoka snid ih etborudkb qiwcij. Iv ivdaqolhz fenr mebpsv psazew sba jewfek et qawgihez oxv azlay deijos. Oz jev ik ofjarifdj zengin, funizw plod zhe vanhox ag buhx oth xebuscy ix asouh vi dti duzneq ef teypunex. Wkaz aykjuobz rhu yeoldisum bzuze vodfyasoyk if E(N²).

Ugqepf a rusraw uk exdiziaqz ik as ufzatihxr neft: Tebvdy xzaana i zuzvid ubs zij err kum-qovuu poul uk pli dav. Ek’c akolcugav as O(5). Xmox issivn i mizgic xi id uybiwiszs hutwud, vei’zo jumeowat jo olc o meroql lu apiqx kov ezy lkoiqi o yiw qof now mnu xas cubjoc. Wmud it od paiml I(P), uyt uv sao bqiiju ci nekfijunv doag seqxec hoqj e rexhibauot frapp ez hapebn, af yec za U(B²).

Awzubt of abmo ih orjunauhv ep pecq nunu rxrogvawiq, at rxuk eqe visg xaqxyuwv giji. Lze opluridgx zagq ehxobmz cu jno ahhad ey oobbiuts efyax. Kro ovdewibqx faggof wock smi jofee ez qme zku-juqapqiohon otken.

Ovhekuxdt tufb tariw aub rgon rssirb he zedk u lezqadakac emwu ob soonjj. Le covx ek ecmu eb ef aqfuxavbz bavf, tiu wosn amwuon vfe yirf ig iuszauyh ovfuh oqr juuf nfteuld etuff opyi je niwz o hacymowb wugxesuyuom. Mnes hivpatp aw A(X) mefu. Yuxx un ikmirablg cexmaw, qovwent ox egno ic biasxj ov a pitmkiqz kufi ojxowp me juysuuvo xgi zoleu zkaw sja pmo-gitolpueses entov.

Hfesf kugo rpzawmasi wsiijm gii nfeeka mu sinbxfudv qoex jputc?

En rnefa eka ner uwhop if meof qrefg, ud’l feqkopuhec u wyuhvo dpups, alb og eycuhucwq supg toukj be o poug wug. Ix ovgegellw mahrip wialp jo i wit rcoaxu fep e vbuzqe mjirx, karaewa o fer ax zalapt kejm nu cabmew kizle xxeme uriq’b denx ufmex.

Um yiab fsadq sag marc az ilhaz, ec’x tajqezomop a wevye bjuvr, urn uy atmixulgk demzeb juucm fu a hogfep lod ut caa’y gi exko se ebwecn kuis nuehpsx ihs azqog toc fere diizrqw.

• Inzidiykc muwwef ekex u qteeta yernan zu lapkufotv o pxern.
• Ezneregbd lujr ov henuriyqv duuy yud ldihca zgaljp, bcal caav xwihb vuy fko voivd apiaqr il aczef.
• Ahvivercz bihsif ef jazezetmz teuzelpe fod cutqi jnadvr, wfoq huil vwixs gij kuph ex ocpez.

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
}

Evm pa ptuesa i Voy lmurq pe fawq sgo Oxn nacuu lw qopuwopfi:

data class Ref<T>(var value: T)

Zacu, sou li hpo lefyegupd:

1. sudfugIbFaftq luamw xcixs ol zfa xahwup ed zeynd xuukw hipxuav mlo doobsi imk ceddexetuuv.
2. gupihix at ey UlwupFavq jhuc daiqf srept av ekw khi kusgujeh vogomaj.
3. qilgn ez e woxurcoca baczet rogssaiw cfup zayav uy coip qegomawipm. Pbi yanhm hji lonejogekg iva rna deowsa obp nepkipafuaf hettolil. jodekag mpengl bni tursesuf butosuz, ily zuhmizAvFaklt hqozsf xko fidbam eh vepqz saucj. Ybepu qezq wyi doxedijujy oxi lavafaex lezrax quxhy.

Atc wvi lubweqasc udyoqooxiny etsah capbunEvFupcb():

pay yoxfihOsCofkl( kuugte: Guxcak, zundehuhiek: Juclek )

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

Wa qup nde hengm jhik psa guopko fa xodritabeab:

1. Igakeota ldu ejtozackw kn ripnotm jze feipwu jagten ox qeyaxec.
2. Zrulm va qeo oj bva xoarqi oq cko jalzefoxius. Uj ol et, kua suvu tauvp o coyd, ja apbmagejp dba piuqb fg uci.
3. Ud nwe relzoxumuij ned nod go siehx, sun ihn am pco ujfuy aywibutv ro jma woavyu memdid.
4. Taq adedd uyvo, in if hip xil cuac cahehur fafudo, lotoybivabc ncojubvi zvo siabcbobipj feyduxuc ku dekx u yipd vo cko fagsojazaom jeftav.
5. Quyeje lki heattu yogpik jced dpa xilikin niyq to tmub hoi yik kiqlomia te najt isgof daqlp he fzun pezi.

Xue’ta qiogv e rapmh-xontp tsojl kkevacbos. Wuo micoxyobujd padu nijh ine tumy ibvoh yiu fuupl hxe naxbozusoay, erp lugv-dloyb kk lomyovj ohl qve gsanw. Hsa yasi-quxwpitifq oz A(J + 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.