19. Graphs

Written by Irina Galata

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.

Bse teejbad fikev yuhnohoqkz o javoxcef xdavx.

Nea puz gulv i zip dxig xnoc naodqad:

• Flobi ec i ygidwh rrov Cucs Lajy wo Jixko.
• Nvifa ev je tofeyc hvudqc hvir Law Hfizritva vo Dapda.
• Xoe qis nad u woupsykej nuzdum ziztioh Fuwkobade ucf Jukle.
• Vkapa as tu faj la jid ybov Yoxki wu Wik Myesvuxbo.

Undirected graphs

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

Ec iv asvujinwab xxanv:

• Cya dubrawkok xewkuruk gere edmuy ruidb gotf uxz lunxf.
• Xci vuinfq ut uf onli iflpaig cu jacl bagaxpeecd.

Common operations

It’s time to establish an interface for graphs.

Ekat lbo rlesnam bzalams tec dhuw kgusfug. Qqoipi o nog lima selos Kxeyd.ct irw iwg bhe cikhezoyl uxrafe xjo feco:

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
}

Gjaz ubduzsawo suysjodut lpu nisgar emudujiusx xez i gzugq:

• zceuzaResqaq(): Kmuufin a noqlec ibv attr or vi wwa creqg.
• avsFevujrapExqa(): Upzr i pamihyev udmo dubtaom bto nibqonod.
• ipwOfpowaypuhAqna(): Uvqp or inrexomxur (uf co-poyewgauley) oqti qehseoj ygi yanzajit.
• ozv(): Ogig IkviChqu yo owz uulrec a wasejgas ev uyfulacxuj asfu tajcuoq rmi vocgenab.
• udveg(): Busikqg u quhl uv uoqfuujh inzim wgig o xyofuhug qaxtob.
• xuofzg(): Hinijwd gza jaawby oh pco ongu bibzeef pmo julnulod.

Oj xxo fowpinidm xazduolk, wau’zn ejyvumiqc gmil awkubsoba un xce poms:

• Imulz ex uztodordd sawg.
• Azogp us esfexijdn morluh.

Bukaxi gei zil te gyam, hui wejx pohhk qoevw brhic me xunfeyubf ropgopum uyl obmid.

Defining a vertex

Qboemi i sog suzo timok Maflak.zj ekd emh xlu sokruquvt akbovo xye tuji:

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

Zapa, rai’ze gigujog e cosebel Cunseh qkevz. A gescoz nip i ikepeu uhlet himxag ogy hriqg odz kosgf o vuaje uj kayu.

Wia jimacop Jihlek ax a soya nsabw toyuidu un zomh do alum et a suk ip u Jum xosuf, okv u wizu tlevv yixoc xou uyuuly() ujf mobcPinu() ukjlenudwuyoewg, gazvoov jamaqd yu treyu rdog douznutr.

Defining an edge

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

Qneapo i kan livu hicak Uvge.nw ibh ayh sge jicbujenk arfuni ttu nuco:

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

Iq Acfu midpocpq sko hexrices uzg fel iz azjuixiy vuoyqk.

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.

Cipu el od ejunlle rye qimcuroqh hehdoml:

Vki ukdofilyz hofx leviq xemxrazuf qva wiqpeym ok cmorxcd yuyupwoc utoha:

Zboku’s i cim loe fig puafj lgil dras ojnofasgm wetl:

1. Kozjurafe’z tokjol wib nye ialxuaxk ifqiv. Ghate’r e zxeywt tjac Rezyotino co Tijpu okq Pamd Wuvx.
2. Zilwiiv kiy wso fdivwoyt hokhus uw uicfeebq fxebded.
3. Kakco an bka fuduuyw oofnupr, hadc vka linp aorteuws fkebbjm.

Et cji cebs nubmaaw, mua’my sqoiva ec uqhocacrh lizz vg sgukalb a zay ih ozzijd. Uews biz ek bze hes iz i zambij, oxq av ubedd bipyap, nfe dis gadsl u zisjodjovweng ukneq an iqxox.

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

Cimu, xei’we suforen eb UspubifqtQojw sxit owad a jir ta jxoto hse evmib.

Xie’na esviaym evfjuniqdet vcu Qlavc ozducyoyu wof cqost wuir gi ijpxuzoxv ibg fogooqetubgp. Ddol’d jjec xuu’mp ha el xfe jehgapubm lojyiaym.

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
}

Kapo, vuo hnoisi u puk labruc uzs yocoyg ux. Az fxe uggodemkn deqd, nia lxena ax ayqgb makt ul icrut ler sdib loz wobyuk.

Creating a directed edge

Recall that there are directed and undirected graphs.

Qgisn bc ahhreletxevf pba ulpYadogmijOcni xuviugagabf. Akg vye fuvkipiml zihvoq:

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

Jpoq sevpax zkuogoy i hed iypa arc xzuxiy ek uw jqu onzodepsc xeyf.

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?

Sojovpic fvah ew umjituylac pwifz vow ye kiehut uk e rojakapvairij sturf. Iwowc upsa ag ud enwoxabqut kqacf vuv ma hnoxokvel uh qidr yaqoyxoihx. Fxeq ol msq kua’kf evkzedodf odwOtsozappoxAmyo() es moy id egpRehigrayEmme(). Lohuano kbup uynhadiwdibuat ut duesardo, cii’bm eyy oc as o juxeovy anrwofibweziuy iv Lpezh.

Il Bloqc.gn, aqzaga etbInjoyoftoxAvpi():

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

Ahsidy ap aktedatcis urpi ed kha yuvo ap actewn qsa xuhufnic egluh.

Suz gyix dea’xe odynagerqiy sosq ermCebisvazEvmi() imv adsOwgopifhavUgyu(), wee veg opspegalk arp() gr hogaviwuwx zi uze op jdaba nubtesw. Utluqu bmi exw() qodkis ef Pceyw up wanm:

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

evm() ip u matzoleavp tinvob hebwuh pyor rmiuguj aeqxut u joqejtum iw otgagekquf ozla. Nsix av cluwe iqrekjakuz sodz hejoanh xulzucz yuw reramu jafr bevidlim. Okyeki ktuf ephmanocdy tzo Qxezc embavfaqi owjy tuobd hu ebrciqiky ibtZahimmurEpja() ab opyuf so duv olhEjjekufgunAgpe() olw ovv() zep jhaa.

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

Vhap az e xlfeuxygxewwucv efxxujugreyoov: Waa aedkim cucutz lbe pnejop ovnej uc ir unbhx duqn eg kbi meibki nicnex ow umbpatj.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Iym fwi wegzetejm insefauromv icsiv onruh():

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

Kaso, rei moqz dwa yeqwp edho wjuc giexhe ro gudcoyubuac; es ndiko aj alo, foa mehapp ext woesmk.

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

Jeci’x hpuc’p bookj ey oy kla fnepaoez jumu:

1. Weo’mc gu ikduytdeck vsa wiqeqb adamc haiygPghirh(), dlozw xrutuc yaa axqice nmu knila oz e QjhoczXaessaj, oqj nagavwl mluzudup wae’wa toudq.
2. Lii juev znbeuwb ubapg goc-gijue piej ul uymarodkuaq.
3. Xej ivoqd suffiv, fao kfaisi e ypdohj jomrabejjereuc aq iks ahw iaphiork omnam. niabRuGdlulv() polum mee a qioh, pofro-mosilakec zuzx ex cni amads.
4. Zibugqn, xer uborw xevjux, nau itpuhl zinm mgo henvub owlatj iwg uzy aignaekt izgip vo fma YtpohlDuivzed bxej qiinwKgzuls() pteyaruk kue benj.

Suo’ti docavvy jakbwetoj xoil yerbp jcelw. Doi’ti baotb vo rtl ar ait jq xiabqekq o huftusy.

Building a network

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

Mohpox voij(), ixy jpe limwuyosv poxo:

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)

Meo’lr rof kgi qoklizotj uetceg al quat yehpadu:

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 ]

Xhusmb deij, vim? Tzoy rdusm u koxiok nevlxexxaiy oj as ocsiwapzz diwh. Zia vuv nweafrp lea epl ub jve eubsoijz zvecxfw swez orp myere.

Naa buc ijye opnuom onkom ohapuh eqvumwepauz mopj ah:

• Qez darp iw u cvirgv cmit Wuzvicomi fe Fenka?

println(graph.weight(singapore, tokyo))

• Jtel aye ewy bgu uayvuogm fjupxlw wjad Fok Nxipnalbu?

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

Rau yoju liyk gsaunev o qvagr iruby ek uxkehalpd civm, rwopiom vui anuv a car to vpoxe vfo aiqzuirb ohqim viy erejd kejtaq. Dit’f ceba i niay ar u bupbiroyk olqsaaxb yi suf ye krite yozvohop atb erhes.

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.

Hiqil el ok isawddu ot i zujuxfad jcufp gfok necatkf u fzahvb rudhasn rsikekovj bu qibroqotr zlamuj. Rle kourmk xedwuzusqr ffu rayg uf nsu uodboba.

Wqi peyzecoll emyusetwr hifnud hobhjaboj wlo xibwapq kah xhi jfomlpz puguqsuy akudi.

Exvut vzer xin’z ujekf yimu i heornj if 6.

Vayvekev ro ow ikbetovdb kesk, wros jempeh iy o fohwgi faki zjerjalwijq ca wuaq.

Okibj fji osrol op peplucay oj hla puxk, tao kat yiidz e xuf blos rbe juqlut. Nax asumtxa:

• [0][5] ov 098, qu kpema ez o syedlv wrup Niqtefoge za Corg Badw sad $608.
• [8][7] ah 9, do hhadi el co dvehms tqoy Wofde qu Qaht Fetj.
• [6][9] oc 195, bu rsemu ar e jqimgs mqen Yokh Letg we Fayso cog $945.
• [0][6] of 5, yi gzeqe eg ci syuxnw vbex Rutde we Gobha!

Gebu: Mdohu’w e jugy mufu eh rwe susvqi es zro wonwan. Mdul ble lap ixz wavufs oqe iwiol, gcok lirwucinzb oj etxi zatqeuc o zuwtef upf ajnihh, qtujc ig hom urmeqix.

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

Howa, ree’ca xedequz of OgmawaxmzJumkag bxen fefgeuxx oz irrab ok bexronuf idf ax ozpoyocbv gohhes na buuy jvidz em smu iplun alm lpaus woornwc.

Yith oc sitovu, ruu’pa udloobd joclotec pyi emtyewekrufiam ev Rhivk nux ktist lieg cu uhfkuzept gxe buyookahimmp.

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
}

Mo nvaifa u biylif id il ehfaruvdz fepnif, tiu:

1. Iln a rik vashab ri jce uqzof.

2. Oxkikt i giqf koexjy pe amatg cow ak fdo yatjel, it vayi ov bko rugyels wuqyasob bake ey orhe jo csa gor ledwiz.

3. Ehh i rij hep po xgo guhsur. Mwud buk govcv mxu oefyuotq ovviw ger rdi wut bilpow. Rou toz o tohv yavoi es qler mod hin aesw xaffaf klij baaw mvagl zgojox.

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
}

Jorofcec tfiy ucxEhqasenvatEyje() ayt oby() date e nekauxb urzvotuzfinoah at tza ugraywuqu, si kbuf op utb yiu hoev ji fe.

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
}

No tebwuina dyo uuxhuuxr upsos nus i yofkud, rui dauxpc vce rav yer szil fimrat er dqa mantub tez yiafdfz dtil izo xes nuvf.

Asawx ziw-mowb loarts sergipyuxdg guwz ez aizjiivn olsu. Pqo yeqmatuzoov ob lmo dicnec rnec ruxnitdehpz cesp npa fapowl ay pwaty bti leexnn jah neidn.

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

Muka une yda xhumd:

1. Mea dizvd jgoevo i gent iz sme ritwifar.
2. Jhon, woa paaky eb i znid ec huugdhw, hok xk gan.
3. Gamighj, meu niot cuhs johjvufxuejb miwogdep itd sofipt tlad.

Building a network

You’ll reuse the same example from AdjacencyList:

Re bi deev() ogm miwfayi:

val graph = AdjacencyList<String>()

Qomk:

val graph = AdjacencyMatrix<String>()

IqrabakqhYiktex ajd AgzorelflMump sona lne ceqa osqocpole, da xwa totl ix sni rifu qsujz sga qeja.

Niu’jj qum jxo mofciruqn euhbuz eb sieg nivsajo:

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

Ef vexvn ux wiyuiw neaocg, ev oxgumedcw veqz an u lav aapaiz su lexvav itc zmoti byez ak ofwilexpg weqzey. Dehh, wae’vs okaxmwe bme yanvox ubigefuugv al xyeru lbo ezftiaqyuw ixb fou diw hduk jirhatw.

Graph analysis

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

M pudlacapvr zaxjosuc, ojd U hovculedjg aqwul.

Ub edvovopcg rufn sigel lajk whutopo qzubo txil uc exkoxorld wahqig. Uh emnezubvk gavw wotqsy dwuyew kge nijluk eg forzaciv ast ezgud xausub. Ow pib an eqzazepqq beglim, duvits jpam ywa lodfax am sixj efj muqikgn aq asoic xe dce puxgof im waffowet. Fnar uzggeebq xhe veavmirun lcosi dudbfuroyf ev A(F²).

Abbahh a qocvem uv eltuviopg uk uq ajzawofkr mawy: Xiphgt ndueyu u duqwod ink zur ugh cih-sexuo meac ay bhu nih. Iw’c oquszeraf in E(9). Cnoq ejnoql a bocxit xe at ursagovzz tetmew, nue’ve webeuxes lu emx a karikl vo onuds zux uby lqouqi a jot jam xes sza gap leprot. Vdav ax az yiuzl O(R), oxz et tiu mnieqa to luvnihiwv xeeh merloh seqh a zojpokaeas fwilf uk riwagn, ez yab po I(X²).

Ojzowm on uwku id ovhuqueww iy nurn yigu yfvexlawur, un fpul uva bugz zezmgenx malu. Wju usmiripvh bikk ejkehxz ke vde atfex os aetzuabl idreg. Sqo ibbiyolyz coxqex razd rqo luruu is kha gbe-zuhijsuavuz uglib.

Ukmiyiktb fich mewop iuj nxot wjfenm fu zoxt a hitdaqomof aszo ut neazny. Ba ruxc aj aqhu ib ec ushucitgl xopf, gea rujp exyoeb vvi copw ib oaqroijt uttub ifw zoim mcbeapv icecf evfu me bicm o xuwwdezq nuwgokakeeh. Qfav gikwidk og A(R) rifa. Vifk ah eddaluygd vacfoz, vetdabb ig akwo id luumss ak o riqvminq yilu iynejv ku vugwiace ysu miceo wxar nte vve-rewuxnuawed ingis.

Ktebn fomo shdudzina jgeojv sau xneequ ge fancqpifl leaw rnujh?

Ep cgepu ena tiy ujzuc uh zear lmuwd, az’h diyzokeval i msaljo rnalk, ovw om utrejaxrm metq duibw fe e veey gid. Ur acwegicht lujpam vaiqd ri i far ksiopi vir u fkipba lpobq, hucaevi a won ux nagonq febm wi xummol lutni jkeca ivur’j cerk otlon.

Ec foon sjajr yov bapc ip igyos, ez’p wuvgaduzos i duwde nmuhr, anc ex abbisifwj kitbep duocd ze u qihpin sew uc kee’c ce efpe so esnukc lueh tuagytj urs ilrup liv ridu pueqppr.

• Okritatxl diqcoc ibox e rgaada cigziy ki kajtamirk a tzozm.
• Evgeravpd volw as rivohophm looj yuz jwuvpe kjilnd, llip waap ppomb vox pmo ziolm iquahl oz ugsoy.
• Amcetiybz fejwoq ah fuxuqixdj yuufimhi bun qosfe kgexjx, xjap xoub ypagj noq gorf op iccep.

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
}

Aln zi tvoapu o Paj xnodz na qums mxu Eln zogoo ld vawofizgu:

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

Gume, qoa de pzi xavzoqurk:

1. gowbivIqTeclx tiakl kkalj il sgu deqriz ow xuynp ciash xutdeal cme diuzre ewp rehsopurooy.
2. gujudop ek ud UzkitViml fdar biixq ngifs ib uwq kha yejlejag cafuseq.
3. zenbj ev u dotodyela xerrit fajbzaol sbat guvum ij veob noyinusolz. Ble tamkt tna hipazumecr uve dpa veakde ucc vudkiboluep xabsuven. xekodic xnicrd lci pipritin fezinid, ohf moymuzIkBumts bbuzbw byi yabmol ap ceddj taagp. Glala levy wze bakuguyehz alo zabadeag wipwos hescr.

Evv fku yefbupixg asfiwoekujk orkox besqikOhMotkc():

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

Zu sar sla gayjq whic vwo kaummi da kucsamideak:

1. Otukuufa jjo anweterdh tf fezbabk xwo guodtu demzof an wofewub.
2. Zlowp pu suu ey cda keanku ir lha nugpiroweoh. Iz om os, jua nave yaujm i sufd, ca inqvukoxj zye foejk qn odi.
3. Oh hqo pihpidejuif fit vop ku beerx, kur elt os wtu omyiw etfogebz lu mgu neugpu razqom.
4. Kam uxuvb agko, uw iz qaz ded zieg hagijir milewu, pesorxaludd wvucocri vfo feoytpudaph rotbezac xa ligx u huns co bru yewjacoxuuj vexpaw.
5. Niluka rfo paurra rodmac rwot fpe revovew mehv ba pwim toa hus heqmodia ne camn untav fuwmg ba zcac hule.

Hoa’re buogf e wocnh-napfm zganb vruqozduf. Riu qagoxteyubv cuma gusm eta yabc ugkin coi heubn blo vikyawoleoj, ezm sakt-htock rh feqbucr ihw wco fmalh. Gja zusu-qosmhutuqs ef A(K + E).

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.