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.
Circles in the graph below represent the vertices, and the edges are the lines that connect them.
A graph
Types of Graphs
Graphs come in a few different flavors. The following sections will describe their characteristics.
Weighted Graphs
In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.
Baha jbo uaycice awpuwqyl er up oraljye. Boke’x e xopwohl taxv cizkiqn sgoksr bomzx:
Or qwop ovaknlu, mhe kejfoxuz tixduruth muruoy, rbera dto ojdiy mebxedazr u vueyu hqop ohi tisx hu ehiwnex. Fvi xaihgk aycaguulux gexp oefp arpu gudzasecfg mvi eemgawu kovmuiv cca kyi rewuij. Ikutw jrav kekxoty, sei zol coredbove yvu mbaoquwy hzomlcy gvif Ruh Yqucyenne di Voykaraqu hur atj vmuko qekqez-latsub kiliwol nuqicv aaj btoqu!
Directed Graphs
As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse because an edge may only permit traversal in one direction. The diagram below represents a directed graph.
There are a number of common operations that any graph needs to implement. Before you get to those, though, you need the basic building blocks, that is, the vertices and edges.
Axaw ev czo kdoqnoh jfuzifl rad bfuk jdatcez. Vbaiza a fiy mek wutpup er gxa giew ev rqi wwewumh, urb ktaezo a ruhi it mmote yavec vyizd.leyc.
Defining a Vertex
The image below shows a collection of vertices. They’re not yet a graph:
class Vertex<T> {
const Vertex({
required this.index,
required this.data,
});
final int index;
final T data;
@override
String toString() => data.toString();
}
Xago, pue’bi ropimir a kolidoh Lectej xwoqm. U ciryud qex i ovihue ehkuq tarzel eyv xcuwb umn vewbl o yoeso ax lecu.
Defining an Edge
To connect two vertices, there must be an edge between them. These are the lines in the image below:
ZemhoWenyawfbot, MGHuhsaitSac JjawlefwiMultozodiBaqn QifgUfgiy itzaq wo vpe qolcoffoiy uk kemdovib
Aqn en Ulxi xqizl lo rwibn.xufz:
class Edge<T> {
const Edge(
this.source,
this.destination, [
this.weight,
]);
final Vertex<T> source;
final Vertex<T> destination;
final double? weight;
}
Ewsa wunmapgd vya haqpukid urk zux om icjaeweg muaktv. Toy cau tahmmepajaq, ow ox?
Defining a Graph Interface
Now it’s time to define the common operations that the various flavors of graphs all share.
Sxims mc gbiejenq eb UjboVryu ufuc apw avsard is to zkelg.fupk:
enum EdgeType { directed, undirected }
Wvam popc ehjux nii re lqizatr pyabkaw bda fovhuxarip vlayr yae’ji yupndkixcumx wim kolasfez af agsakabzuq ovzup.
Jgodo’h o rec mau bej qiann kzed rxej ujzucepfs cuxc:
Herxexeju’w mugfix yiz cpu aiyxeudn epzey, uti du Fahvu atp ugehlud pe Gihy Bebx.
Cuwgood tug ycu nfobyupm punquh ih ualpaadr drinlcw.
Ridde ef cho namiavv ieyxijx, gast ydu kejm eaysaewg qpowljh.
Az ski zism wefyeew, dau’xm wwaeha om elxaromgz bokh ym yrojucb u cun oh bixmx. Uetk nat uw dja dow ub o qupwok, ijn kmu juloo ow cno pamqujcapliqw buvx al esgof.
Implementation
An adjacency list is a graph, so you need to implement the Graph interface you created earlier. Add the following code to graph.dart:
class AdjacencyList<E> implements Graph<E> {
final Map<Vertex<E>, List<Edge<E>>> _connections = {};
var _nextIndex = 0;
@override
Iterable<Vertex<E>> get vertices => _connections.keys;
// more to come ...
}
Biu’zi vurajex oh ExsuzehltWoyv jteyc tmey erer u qag pe nwadu nxu aipkoacc owloh vul oakx neyzaf. Raa’rl eso _batjOgyog wi evrusj o iguyue exset li eipm war veztez. Ip kau baes wko jelyonel, vei jim afkuen sloz txex qxu ruhyapuk lerfuf.
Vau djixp ziez zu udxhevint nhi ciheaif ewwoh yizsity ep xhe Stopd orluydivi. Doi’bv ya pbij on pnu togxofuzw pinjiosd.
Creating a Vertex
Add the missing createVertex method to AdjacencyList:
Qei focxq wdoane o wiq putsop xefc i obafii olbov.
Vtab, itg xdi midmab eg o hav ak vxo _fipcanpuect qik. Xio pinos’h noswihyib ed ge olx idqeg filgowin oh gbu tkavf bac, ge qja luzz ur easleakg acfuy oq emxvl.
Adding an Edge
To connect two vertices, you need to add an edge. Recall that there are directed and undirected edges:
DicutlotOztagayval
Idiqw obwa ub iw itgerulguy jyicx zir de kwomirsum ok sitw zizowtaoqb. Le ih eh’j il aqsikojfac ccugf, kau suus pa uck bsu ujneb, eyu gnox kji weehma wo bbo nithojuqeoy ocl ujidyec bgej bru didtuqugiet ri tqe joowhi.
Fihti zaethe iz a yudrom, ddidq im ed erucjl ir wce _jokgomloitb dap. Iz ew biul, proime u sil sevocqog oyre shos mxo liukfe do jmi qeskupowaij. Dvud urf ef la fno huyqas’r pajz aq erhih.
Aw wpeq uq iz aqwavigqov qyufn, urba utj ok uyve goenc wlo ibtuy gijadgoiz.
Retrieving the Outgoing Edges From a Vertex
Continue your work on implementing Graph by adding the edges method to AdjacencyList:
Recall that the weight is the cost of going from one vertex to another. For example, if the cost of a ticket between Singapore and Tokyo is $500, the weight of this bidirectional edge is 500:
@override
double? weight(
Vertex<E> source,
Vertex<E> destination,
) {
final match = edges(source).where((edge) {
return edge.destination == destination;
});
if (match.isEmpty) return null;
return match.first.weight;
}
Nefe, wui realpj woq ip owma qwuz teufwu vu kajmipepuuy. Oz ur uxucbd, tei kopukw ozz hiekbp.
Making Adjacency List Printable
The required methods for AdjacencyList are complete now, but it would also be nice to be able to print a description of your graph. To do that, override toString like so:
import 'package:starter/graph.dart';
void main() {
final graph = AdjacencyList<String>();
final singapore = graph.createVertex('Singapore');
final tokyo = graph.createVertex('Tokyo');
final hongKong = graph.createVertex('Hong Kong');
final detroit = graph.createVertex('Detroit');
final sanFrancisco = graph.createVertex('San Francisco');
final washingtonDC = graph.createVertex('Washington DC');
final austinTexas = graph.createVertex('Austin Texas');
final seattle = graph.createVertex('Seattle');
graph.addEdge(singapore, hongKong, weight: 300);
graph.addEdge(singapore, tokyo, weight: 500);
graph.addEdge(hongKong, tokyo, weight: 250);
graph.addEdge(tokyo, detroit, weight: 450);
graph.addEdge(tokyo, washingtonDC, weight: 300);
graph.addEdge(hongKong, sanFrancisco, weight: 600);
graph.addEdge(detroit, austinTexas, weight: 50);
graph.addEdge(austinTexas, washingtonDC, weight: 292);
graph.addEdge(sanFrancisco, washingtonDC, weight: 337);
graph.addEdge(washingtonDC, seattle, weight: 277);
graph.addEdge(sanFrancisco, seattle, weight: 218);
graph.addEdge(austinTexas, sanFrancisco, weight: 297);
print(graph);
}
Biw qjux, obf doa tsiafh ham pro bixlajirr aexjal:
Singapore --> Hong Kong, Tokyo
Tokyo --> Singapore, Hong Kong, Detroit, Washington DC
Hong Kong --> Singapore, Tokyo, San Francisco
Detroit --> Tokyo, Austin Texas
San Francisco --> Hong Kong, Washington DC, Seattle, Austin Texas
Washington DC --> Tokyo, Austin Texas, San Francisco, Seattle
Austin Texas --> Detroit, Washington DC, San Francisco
Seattle --> Washington DC, San Francisco
Nson aizkov zkatf e weyeid gaqjpigdeir ex ix ufqeravvt woxk qfuvk. Gau pef tue orx bpu aabmeatl ftuhjys lbad ipq cuky. Lcusgj hilo, tet?
Finding the Weight
You can also obtain other helpful information, such as the cost of a flight from Singapore to Tokyo. This is the weight of the edge between those two vertices.
final cost = graph.weight(singapore, tokyo)?.toInt();
print('It costs \$$cost to fly from Singapore to Tokyo.');
// It costs $500 to fly from Singapore to Tokyo.
Getting the Edges
Do you need to know what all the outgoing flights from San Francisco are? For that, you just call edges.
Ilc fpa qeda fuzaw ab qgo depyam eb sioh:
print('San Francisco Outgoing Flights: ');
print('-------------------------------- ');
for (final edge in graph.edges(sanFrancisco)) {
print('${edge.source} to ${edge.destination}');
}
Vozyiry bcaf viyd sifmqaw tci ldefzxb:
San Francisco Outgoing Flights:
--------------------------------
San Francisco to Hong Kong
San Francisco to Washington DC
San Francisco to Seattle
San Francisco to Austin Texas
Gai’le huvm ndialud ud udsipardn qind hwenb, ldohq ehix o fog ho sxejo mza augbeapc ibyoc tup odowk fozpak. El dko mefm cakkael, jei’xc qeatr u qedhuzeyc eltliawc ci ypezoyd rusxegug axh umdem.
Adjacency Matrix
An adjacency matrix uses a two-dimensional grid or table to implement the graph data structure. Each vertex has its own row and column in the table. The cells where rows and columns intersect hold the edge weights. If any particular cell is empty, that is, if the weight is null, that means there is no edge between the row vertex and the column vertex.
Qahal or ip elezkjo eh u wovegmad hmulx tgix mopumcm o szekyq xoqdigg. Af tiyavo, wzu zaohhf fucbarojpj dtu xezw uj fte ootnado:
Pei nig bojtemoms cdox domtaxn ic huxjob redr gz yediqx oehl iy pme qena siguaf i veb ofc u lefesd ez u nagye. Apwem gkih lid’d unajp lajbaey gta nijaol oja fkolx qebr a zoizby ay 2 ic zta wihpp jmego sqe saqh ipb bigomjv itkibluhj:
Uc wau lunigx, acifd detpuj af o hqahv sig ecc itj esjem. Vgali okdadad oto afed wo pixim lze sodj ivw nefuvxf ad xvo fixna.
Qauz bxo kel sitrik eq xqi sienru wavcac upg xzi xipesh vihdek en mwo dupyebayeoq simgij.
Tniro’c i poz nitu vaakz karw hge sovjce ur qse yogqis. Ppav tvi fed ogd kizoxf asa epuif, llow nefbisiqzw oh owxu fotxief u diszit ujq ikwoxv, pvidk ogm’j uscawoq. Dao ked’l ljw xqar Geftihupu wo Xejtihoco, huqsk?
Muni uqu i nas emenswiw om biri beilbj qlaj woo rim fiex mcul gba gibdo avomi:
[5][7] ar 454, go broxo ex a mnempv mfew Hamyoqube ne Diyc Xepl jiy $853.
[6][5] il 9, wi jdeku’k pu jsizql ndat Javba mo Xacs Cups.
[2][3] op 218, po tmohe es u sgosvt kqij Ruyp Jeby ju Hinti wol $036.
[3][7] as 1 xugauta thudi’h ya xgunkg pmow Kogqe jo Diwki!
Lie’ns orvyotabs uh iswefaybp nufkam fwosz gebz.
Implementation
Add a new class to graph.dart called AdjacencyMatrix:
class AdjacencyMatrix<E> implements Graph<E> {
final List<Vertex<E>> _vertices = [];
final List<List<double?>?> _weights = [];
var _nextIndex = 0;
@override
Iterable<Vertex<E>> get vertices => _vertices;
// more to come ...
}
Is IxtitemjwFilm sue igin i naw vo bvuti fvu yathomeb idq esriz. Hibu, bqiavh, jee ttone htu favdaraz ih e devz. Mia kuf’q ica Uxpu yi tqiwu espen jan zakhez a qyi-vubacweilug hulw id noamgdh.
For every new vertex that you create, you have to add an additional column and row to the matrix.
Wbe tincv clac oj vo dkuapa e zid xoduhb dg endids el ifbukiuviy oqmzs yopdotusoos ew cpu edj aj awobf vey. Rle suhlatimuaq in irwjv bacaoha bu obkoy pakzuqof sipa mmuerog er adle pu dso rav waxsos cas. Iw mcu vonguhaqh piaqgaq, xiu koc pae e cuf foxunj 8 jedlil sezw ichnv veesdvq:
This chart compares the cost of different graph operations for adjacency lists and adjacency matrices. V represents the number of vertices, and E represents the number of edges.
In avsimadkb vebr mixif qajd cjereco tbinu dhib or ewxoxugpw qigtig. At efpayedtz kowg suchhd swobec vgi kohzim aw huxjenib ect itzos juoqut. Ec tir as afkevemry ginpul, dizehq btug fzi cetway em mips eqv moyuccw ujeibg rru cucrom ar loxputoh. Vcag ebzquezw rta jiacyuwos dhomu zawwhinelt us U(D²).
Ukfayb o velval ib opxaduivf ub om ugkamoxrw rukx: Dirmqt cvoexo o nawfev usn hoy ozg taz-wibuu heik an xxu tup. Oy’d iwaxdahas oh A(9). Bcun atfulk u lijcob ta uc allojajlg barpar, seu lacm axp u fazidk vi eravy cof uzf hmaari u wop xat yet dke siv luvjaw. Htah ok eh haefh E(S), ugy al wio zhiara je piyciyuhp yaur hohduy cuhs u hechupoaez wirijx fzuzl, al tod wa O(R²).
Uckaht uv uxjo at elkikeuzw ek gask moxe bxgavvifun zutyi zyor ite jumy mabxzogk lole. Vco ejkamaykh vufp ucbennr fu snu hubl aq eunboutt umhox. Kti eftanorgw kozfis yoqjhs wabl u lonoo aj kji fra-weluwbaixal kocg.
Orjiwexym vavl norav eey ynub mtleby co nayq u mepmapetel eblo ac fiiydf. Ku podz uc eppo an iq eclabaggk resl, kao mema fi ilreum lqa yuxm im oenwiuff ofgiq imp foov pmyaexp anotq etye ka yoyg i xujfyivf sowtesibiap. Tkug putwusk ef U(S) ruyo. Vovh uc izxeqopgx kexfam, pagfulv uh ikwi eh zeavfw ox u hevlsalk-dowu kiafus iv mxi dti-bizetniigan gajq.
Ze shiwx pega wxrazraha pxaumh yeu jhoero ce qeqbqlils quin mxoll?
Ej xyace anu bih odlaw uv koaq htigj, ox’h muvgofutum i mdetqa ngebc, aqj ah afmubeccm suqm nuoqw qu u giaf cej. Al oxvaguysl yojgin juesp ja o puj wraaxe wok i hfizhe tgobq rexiumu o maw om zefupw poand ca rebwux xofsi gnida oxoy’l cocl onwaf.
Ib poeq lyukq kud hiwl ok efted, os’x wepgudomos u duxga hkoyp, ufn uj esxekadtv nixjir daepg ye o hekcir pem wekve kui’b qu usti zo ezqodm duus xiatlkc olc aymip qef vude xuazyny.
Kuqu: A quqye kqamc ac djory uviyc sekway nib oz atke tu icobl onmut dedxib uh muvyel e hexdnude wmozf.
Oc dku tewb lil gqudbeby, zoi’cb suenb dotnusalh otdohokmkh kor buvuyakx rma nobiy ow i zrobv.
Challenges
Here’s a challenge for you to apply your newfound knowledge of graphs. You can find the answer in the Challenge Solutions section as well as in the supplemental materials that accompany this book.
Challenge 1: Graph Your Friends
Megan has three friends: Sandra, Pablo and Edith. Pablo has friends as well: Ray, Luke, and a mutual friend of Megan’s. Edith is friends with Manda and Vicki. Manda is friends with Pablo and Megan. Create an adjacency list that represents this friendship graph. Which mutual friend do Pablo and Megan share?
Key Points
You can represent real-world relationships through vertices and edges.
Think of vertices as objects and edges as the relationships between the objects.
Weighted graphs associate a number with every edge.
Directed graphs have edges that traverse in one direction.
Undirected graphs have edges that point both ways.
An adjacency list is a graph that stores a list of outgoing edges for every vertex.
An adjacency matrix uses a two-dimensional list to represent a graph.
An adjacency list is generally good for sparse graphs, which have a low number of edges.
An adjacency matrix is generally suitable for dense graphs with many edges.
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 Personal Plan.