Graph Paths Explained: Node vs Edge Based, Simple Paths, Cycles and DAGs

Neural Lantern

Hey there, let's talk about paths inside of a graph. We draw a directed weighted graph and compare node-based paths to edge-based paths. Node lists alone cannot tell which edge you took when parallel edges have different costs. Edge-based paths use tuples of start, destination and weight so every route is clear.   We also cover simple paths with no repeated edges or vertices, cyclic paths that start and end on the same node, and how a cycle proves the graph is cyclic. Then we explain DAGs, directed acyclic graphs, with examples that stay acyclic and ones that gain cycles.   This sets up algorithms for later videos. Leave a comment with topics you want next. Thanks for watching and please subscribe.  00:00 Introduction to Graph Paths 00:28 Drawing a Sample Graph 02:25 What is a Path 02:42 Node-Based Paths 03:27 Adding Weights and Parallel Edges 04:34 Example Paths with Different Costs 07:19 Edge-Based Paths 07:35 Representing Paths with Tuples 11:35 Order Matters in Directed Graphs 12:52 Simple Paths 15:34 Cyclic Paths 18:22 Directed Acyclic Graphs DAGs 19:08 Building a DAG Example 21:41 Adding a Cycle to Break the DAG 23:15 Conclusion and Future Videos  graph paths, paths in graphs, node based path, edge based path, simple path graph, cyclic path, directed acyclic graph, DAG, graph theory, graph edges, weighted graphs, graph cycles, edge list, graph algorithms basics  =-=-=-=-=-=-=-=-=  Thanks for watching!  Find us on other social media here: - https://www.NeuralLantern.com/social - Twitter / X: https://x.com/NeuralLantern - Rumble: https://rumble.com/c/c-3696939 - BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt - Daily Motion: https://www.dailymotion.com/neurallantern - Minds: https://www.minds.com/neurallantern/ - Odysee: https://odysee.com/@NeuralLantern:5  Please show your support!  - Buy me a coffee: https://ko-fi.com/neurallantern  - Subscribe + Sharing on Social Media - Leave a comment or suggestion - Subscribe to the Blog: https://www.NeuralLantern.com - Watch the main "pinned" video of this channel for offers and extras

Transcript

00:01hey there let's talk about paths inside of a graph

00:16okay so first thing that I'll say is you probably should have watched my other videos already so

00:21that you understand at least the basics of graphs or maybe you already know and you just came here

00:25for a little extra so let's just draw a sample graph here I'm gonna do like random notes let's

00:32see what am I supposed to do supposed to look full screen that I'm gonna draw some random notes with

00:37some random values inside of them so I'm just gonna do like a three here maybe like a three

00:42yeah like that and then I'm going to duplicate this a few times so I'm gonna go this is a

00:48valid

00:48graph it's just not a connected graph as we talked about in my last video so I'm just gonna do

00:54this

00:56I guess that's okay I'm gonna change all these numbers even though your graph should be able to

01:03support duplicate values in the nodes it's going to be really hard to explain so I'm just going to

01:08change all this stuff nine here and then like a 22 well I think that's probably good so I'm gonna

01:16do

01:18this this okay so still a valid graph but there's no chance that we could have a path anywhere in

01:24this entire graph so that sucks we could by the way do a path with a undirected graph but I

01:33kind of

01:33feel like I want to do direction on all the edges so let's see let's do direction and also weight

01:41I'm gonna

01:43like draw an arrow here and an arrow here and arrow there I'm gonna draw edges first in a way

01:50that it that

01:51kind of makes it feel like I could find a path almost anywhere I want so I'm just gonna like

01:55draw a bunch of

01:56edges maybe like another edge over here nope that's wrong how about this maybe another edge going up here

02:03and an edge going up here and an edge going down there I'm just gonna draw a whole bunch of

02:09edges in the hopes

02:11that we'll have a decent graph with lots of path possibilities okay I guess I've almost drawn a complete

02:18graph already oh no no no this is not a complete graph I've just drawn a graph where you can

02:23kind of get

02:23everywhere okay so uh well I mean what is a path it's just sort of like you know some sort

02:31of a

02:31representation of how do you get from one start node to some destination node like a map so uh the

02:39first thing that we could do is we could say let's make a path based on nodes so I'm going

02:42to say node

02:43based paths um let's start off with actually let me get rid of this and put it on the next

02:50slide

02:52we'll do this duplicate it that way I have the original let's pretend that our path is going to be

02:59just a list of nodes uh that we travel to through so I'm going to say um a node based

03:06and we'll have one path we'll say path one um and then path two maybe we'll do like a second

03:12path

03:13and um well at first we might think this is totally fine but uh later on it'll get confusing in

03:21terms of

03:22which edge did we actually take so let me show you let me show you what I mean I'm first

03:27going to add

03:27weights to all the edges so I'm just going to do like you know a four and a three over

03:31here and then

03:32like a one and a two little one and then like a six and then like a four I'm just

03:37adding random

03:38weights or random costs to all of the edges and um then eventually let's see when I finish doing all

03:46of that eventually we can probably realize that we could add more than one edge going from the same

03:52start to the same destination node but give it a different weight uh so that we have a little bit

03:57more of a choice so uh suppose for the sake of argument that uh we have this six and the

04:03four here

04:03the six can go to the four at a cost of four but maybe the six can also go to

04:09the four uh with a

04:10different cost maybe a cost of one I don't know why it's there I don't know why the four is

04:15there

04:15also we'll just say this is our graph so you can have edges like this that go to the same

04:20uh start

04:20and destination nodes but have different weights so a path that is based on nodes uh doesn't really

04:29have enough information uh to tell us which edge we took let me show you what I mean so suppose

04:34we

04:34want to get from node I don't know node three I'll put an s here for start um

04:44uh and then I guess I'll put a d for destination or donut uh I'll put a d there on

04:49node number 22

04:50so we'll say we're going to go from node three to node 22 so start and destination

04:59um a path based sorry a node based path path one we could say maybe let's go from the three

05:05uh to the one to the six to the four to the twelve to the nine to the 22 and

05:16that tells

05:16you all the nodes that you would hop on another path could be let's see that first path when we

05:22went from three one six four twelve nine uh twenty two when we go from the six to the four

05:29we could

05:30have a second path here that goes from three to one to six to four but takes a different edge

05:36this

05:36is kind of what I'm trying to show you notice uh that we have two different paths I'm going to

05:41do one

05:41in uh uh maybe red so it's going to be three one six four so from three to one and

05:50then six

05:52and then we'll travel along that four edge once we get to the four we'll go 12 and then once

05:58we get

05:5912 we'll go nine and then nine to the 22 okay uh then uh the other path path number two

06:06let's say

06:07that we chose the other edge we chose the six to the four edge that only cost us one so

06:12it would kind

06:13of look the same for the most part except when we finally get to that other uh node we're actually

06:18going to be going this way right and then we're going to go uh up and then to the right

06:24and then down

06:24so if you look at this carefully for a little while maybe pause the video these are actually

06:30two totally different paths with two totally different costs so um you know the cost of the

06:35orange let me write it in orange it's going to be five plus one so six and then uh a

06:45seven there

06:46and then uh eight nine there and then uh then i guess like a 15 there and then a 16

06:53there so the

06:53cost of the orange pass is going to be 16. if we switch to the red path the only difference

06:58is the

06:59choice of edge we took between the six and the four node so we would increase our cost by three

07:04so the red

07:05path would be a cost of 19. but how can you tell the difference in a path that is based

07:13on a node

07:16it doesn't have enough information right so what we're going to do instead is we're going to use

07:20edge based path edge based paths in some places uh you know you can you can use node based paths

07:27that's totally fine but for me i'm going to say let's do edge based paths edge based paths and now

07:34we just have to figure out how to add that extra information into the path so going from the three

07:41to the one we're actually traveling along an edge right we're traveling along that five edge

07:46so let's just stick a tuple in there a tuple meaning just a little collection of values

07:51for those of you in c plus plus if you use std pairs that's really a tuple with two

07:55items we're going to use three item tuples tuples not always limited to three items it could be two

08:01three four even probably one um or much more so i'm going to say let's use a tuple that has

08:07three items

08:08per item or tuple and we'll just say that we specify the start node

08:14and then the destination node so we start at three we go to one

08:18and then the weight of the edge that we choose to travel along so in this case there was only

08:22one

08:22choice for an edge but we're putting enough information into our uh into our hop that this

08:28can be considered an edge based path so when we go to the one node we ended on the one

08:35node sorry we've

08:36gone to the one node we just ended there so we could start on the one node for the next

08:40tuple

08:41because then we're going to go to the uh what are we doing first red i think we're doing red

08:47first

08:47yeah we go from the one node to the six node so i'm going to go comma six and then

08:53we choose which

08:54edge to travel along that's just the one edge and so 161 means start at the one node and at

09:01the six

09:01node and take the one weighted edge then do the same thing again for the next tuple so we're at

09:07the six

09:07now where are we going to go we're going to go to the four and then we choose the edge

09:12that costs

09:13four and then for the next tuple we're on the four and we're going to go to the 12 so

09:20i'm going to say

09:2012 is the destination and which edge did we choose the two even though there's only one choice at least

09:26we have enough information for all edges in our entire path so then again we're at the 12 we're going

09:31to go to the nine so i'm going to put a comma nine there and then we choose to take

09:35the edge that uh

09:36what was that cost six i can't read anymore um let me actually just look real fast

09:44six i guess i overrode it i'm just going to assume that it's a six

09:49um i guess i could erase it real fast or move it or something okay let's see what is that

09:55yeah it's a six

09:56okay so we're on the 12 we're going to go to the nine and we choose to take the edge

10:01that costs

10:01six then we're on the nine and we choose to go to the 22 using the edge uh that costs

10:08two and then

10:08this last thing doesn't need to be done because we have the entirety of the path in our edge based

10:14list

10:16so i'm actually just going to copy paste this entire path

10:20and stick it into the second path because remember the only difference between the first path

10:24and the second path that we chose is when we were going from six to four we chose the one

10:29edge

10:29instead of the four edge so now look at this i can just change that four to a one and

10:33now we

10:34definitely have two different paths and because we're using edges to describe our path we can tell

10:39the difference you know in a in a computer program we would know exactly which edge to travel along or

10:45even just a user moving their finger along a graph or whatever so in my opinion edge-based paths are

10:51a

10:51little bit better they're also better because if you practice writing down edge lists like this

10:57then you get a lot closer to a representation of a graph in your machine called an edge list

11:04so in an edge list oops i put ed light i don't know why i did that and now the

11:10computer's not responding

11:11so my mistake is immortalized edge list a representation of a graph is basically a graph

11:18is equal to a tuple where one item in the tuple is a list of vertices and another item in

11:23the tuple

11:24is a list of edges so if you learn how to do edge-based paths then you're already a step

11:29closer

11:29to being able to represent a graph inside of your computer program in the machine so another thing

11:36that i want to point out is that since this graph has direction the order of the start node and

11:42the

11:42destination node absolutely matters for example uh if we have this three comma one here indicating we

11:49start at three and we end at one well that means there must be an edge that points from three

11:53to one

11:54otherwise this is an invalid path if for some reason if for some reason let me get rid of this

12:01here

12:01there's too much stuff on the screen um we switched the three and the one like if i said

12:06you know one comma three uh this is invalid because it's saying that we have to start at the one

12:13node

12:14and end at the three node but the one node has no has no edge going to the three nodes

12:20so this is totally

12:21invalid does that make sense i hope it makes sense to you if this was an undirected graph where every

12:28single edge did not have direction then the order actually wouldn't even matter uh you would just have

12:34to check in both directions to see if an edge existed um so let's see we talked about uh different

12:42paths uh you know typically you would want to choose the lowest cost cost path but there are algorithms

12:47that we can use in future videos to compute paths um let's see something called a simple path is where

12:56every single edge uh in the path is distinct so for example uh i don't know let's say we had

13:02like a

13:02really gross path here let me get rid of let me get rid of some of this get rid of

13:06the oranges maybe

13:08so that this is a little slightly easier to read um let's see did we choose oh i have to

13:14fix this

13:15let's fix the three and then the one and then we chose the four so this is the red the

13:22red path indeed

13:26so a simple path is nope i i accidentally erased like an extra edge or something so i got to

13:31do one

13:31from the four to the twelve okay let me just do that real fast from the four to the twelve

13:37at a cost of two okay so a simple path is uh something where you don't repeat edges so i

13:42can

13:42also write down simple path here simple path if this was not a simple path then we would just

13:51basically have to repeat an edge somewhere so um uh if any of the edges or vertices were repeated

13:59uh this would not be a simple path so let me just i don't know let me just update this

14:03real fast let's

14:03say we do oh what should we do let's do i don't know when we go from three to one

14:12to six to four

14:14let's go back from four to six and then we'll take the other edge back to four and then we'll

14:20go up to

14:20twelve so this will be like um not a simple path if we say gosh i should have written this

14:28down before

14:28i drew it three to one and then one to six and then six to four and then four back

14:35to six okay so

14:36i'm going to add another tuple so starting at four going back to six and taking that three edge i

14:43think

14:43is what we're looking at and then another tuple to get back when we go from six to four and

14:49then take

14:49the um one cost edge and then once we're at four then we can go four to twelve that cost

14:56a two and

14:56then 12 to nine at a cost of six and then nine to 22 at a cost of two okay

15:02so i mean i'm just saying

15:03you can make a path where you just repeat a whole bunch of the edges and nodes and you're just

15:08like

15:08going in a circle forever like whatever you really want it's not necessarily going to be an efficient

15:13path or something that an algorithm should produce but you can have a path like that maybe your character

15:18is just going crazy in the game and they're just going all over the place um so this is not

15:23a simple

15:23path because we we repeat stuff on the previous slide since we did not repeat anything uh this is

15:29a simple path okay um let's see something else that i want to talk about is a cyclic path

15:38a cyclic path is basically a path where you start and end on the same node being able to find

15:46a cyclic path

15:47uh in a graph is a way that you can prove that the graph uh is itself cyclic let me

15:53try to get rid of

15:54this here yeah there we go okay so just pretend for the sake of argument that i'm just kind of

16:00looking

16:00around and i'm trying to find um you know some path that proves i can start at the same node

16:07and end on that node uh without repeating edges so let's see um all right so i'm gonna do take

16:18the

16:18three and go to the six and then so i want to try if i start on the three then

16:23i want to try to find a

16:24way to get back uh to the three again so i go from three to six and then i can

16:31go from six to four

16:33and then if i go from four to six over here i'm not repeating that edge going from six to

16:38four i'm

16:38using a new edge from four to six and then i can go from six to three again not actually

16:44repeating an

16:44edge now i've started and ended on the same note which means i have found a cycle in the graph

16:50let me

16:51just describe this path real fast in terms of edges so we started on three oops we started on three

16:59and

16:59then we went to six and it cost us three and then once we were on six we went to

17:05four so i'm going

17:06to go from six to four and we chose the edge that cost us four and then once we were

17:12on the four

17:13uh we just went backwards to the six so it's going to be four going to six and we took

17:17the edge that

17:18cost three once we were on six uh we took the six to three edge so six to three whoops

17:26six to three edge

17:29and that cost us three yeah did i do that right when we go from the three to the six

17:36in the

17:37beginning i wrote down a three but i should have written down a two hopefully you cringed on my

17:41behalf right because i was i think that red arrow is like on the left side so my brain was

17:45looking at

17:45the three but we were really taking the arrow that points down from the three to the six so there's

17:50a

17:50two there let me just double check one more time six to four at cost of four four to six

17:55at cost of three

17:56six to three at cost of three so we have started and ended uh on the same node and therefore

18:03we have

18:04found a cycle in this graph which means this graph is cyclic what is cyclic just means it's a graph

18:12that

18:12has a cycle anywhere inside of it so this is a cyclic graph makes sense okay uh why is this

18:22important

18:22well there's kind of like a special type of graph called a dag which means a directed here let me

18:28let me write this down real fast on the next slide so that we don't get confused on the next

18:35slide i'm

18:35going to say we have a dag is basically a uh directed acyclic graph what does a mean when it's

18:46in front of

18:48that thing so acyclic means not cyclic and then graph so in some algorithms you are required uh to

18:56you know like have a dag before you can even use the algorithm or if you're being tested somewhere

19:02so let's just uh start by you know drawing like a little bit of a graph and we'll see if

19:07we

19:07have a graph that uh that qualifies so i have a little graph here if it was if it was

19:12empty i don't

19:14know if you could call it a dag or not i think i would because it's empty it could be

19:17directed um

19:18so we have like a graph here um i would call this a dag because it's a graph uh and

19:25we don't have any

19:25edges but like i could assume that this would be a directed graph but just to make this a better

19:29example let's just say we have like two nodes here and um you could also probably assume that this was

19:35a dag because you could assume that there are no edges in this graph but if we did add an

19:40edge

19:41a second from now then it would be directed not the best example but so let's just add an edge

19:47here

19:48oh actually let's add an edge that's undirected real fast uh from from two to six and then maybe

19:55i'll just kind of duplicate some of these we'll do a couple more so i can just make this more

20:00interesting we'll say 11 we'll say a four here so ask yourself is this a dag directed acyclic well

20:09there are no cycles that i can see in the graph there's no halves that you can find to kind

20:13of

20:13like end where you started but this is a it is a graph and i don't see any cycles but

20:19it's not

20:19directed because these edges don't have direction so that means right away we have to upgrade every

20:24single edge to have direction so i guess i was going to draw a bunch more edges and now i'm

20:29just

20:29going to only draw this one edge so this is definitely a dag if we just sort of do it

20:36like this

20:36maybe another edge like this because i don't know about you but i cannot find any path that allows

20:44me to start and end on the same node let's just double check it um we'll do uh the two

20:49can we find

20:50our way back to the two no because there are no incoming edges to the two all right that's good

20:54let me just do a check here um what about the six if we go out to the six from

21:00the six to the four to

21:01the eleven it would have been dangerous if we could get to the two but we can't even get to

21:06the

21:06two so that's fine that means the six is okay we cannot find our way back there the four um

21:12we can

21:13go to the eleven but we can't go any further we're at a dead end we can't even go to

21:16the six that means

21:17the four can't find its way back to itself where you can't find a path that goes back the eleven

21:22has

21:22only incoming edges so that's automatically you know a dead end so all of the nodes qualify as we could

21:29not start and also end at that node with a single path so that's good that means this is a

21:34dag a

21:35directed acyclic graph if you want to make this into not a dag just figure out how to add a

21:42path

21:43so that you end up with a cycle so what was the first thing we did the two goes to

21:46the six goes

21:47to the four goes to the eleven then it's a dead end we could either add an edge from eleven

21:51to two

21:52to make a cycle but that's a little bit too easy right because if you see any pair of nodes

21:58with arrows kind of pointing back and forth between the two nodes then right away that alone

22:03is a cycle so i'm just going to maybe do an arrow or an edge pointing from four to two

22:08then it doesn't

22:08look so much like a cycle although um it's not too hard to realize that there is a cycle in

22:15this graph

22:15in this graph so this is not a dag let me show you the cycle we could go from two

22:21to six and then from

22:23six to four and then from four to two uh and therefore we would have a uh a cycle so

22:30this whole

22:30graph is not considered acyclic this graph has a cycle and if we want to do an edge based path

22:37we don't have weights on this graph right now so we could describe the path as such we could say

22:42start at two go to six and if your edge list is of a graph that doesn't even have weight

22:49at all

22:49then you don't really need that third item in the tuple you can just do a start node and a

22:54destination

22:54node this does kind of preclude you from having parallel edges you know two different edges that

22:59point from the same start node to the same end node so as i go from two to six and

23:04then from six to uh

23:06four and then from four to two and then we have a cycle and that's it okay i think this

23:14is all i really

23:15wanted to talk about for this particular video in future videos we're going to do algorithms and

23:19then there are some others up already that have graph properties and connectedness and and definitions

23:25and things like that so uh leave a comment uh asking about some algorithm or some property of a graph

23:31that

23:31you might be interested in otherwise thank you so much for watching this video i hope you learned a

23:36little bit of stuff and i hope you had a little bit of fun i'll see you in the next

23:40video

23:42yeah i'm gonna go eat some cookies no i shouldn't do that but i'm i'm still going to

23:49hey everybody thanks for watching this video again from the bottom of my heart i really appreciate it

23:54i do hope you did learn something and have some fun uh if you could do me a please a

23:59small little favor

23:59could you please subscribe and follow uh this channel or these videos or whatever it is you do on

24:05the current social media website that you're looking at right now um it would really mean the world to me

24:10and it'll help make more videos and grow this community so we'll be able to do more videos

24:15longer videos better videos or just i'll be able to keep making videos in general so please

24:20do do me a kindness and uh and subscribe you know sometimes i'm sleeping in the middle of the night

24:26and i just wake up because i know somebody subscribed or followed it just wakes me up and

24:30i get filled with joy that's exactly what happens every single time so you could do it as a nice

24:34favor

24:35to me or you could you could troll me if you want to just wake me up in the middle

24:37of the night just

24:38subscribe and then i'll i'll just wake up i promise that's what will happen also uh if you look at

24:44the

24:44middle of the screen right now you should see a qr code which you can scan in order to go

24:48to the

24:49website which i think is also named somewhere at the bottom of this video and it'll take you to my

24:53main website where you can just kind of like see all the videos i published and the services and

24:58tutorials and things that i offer and all that good stuff and uh if you have a suggestion for uh

25:07uh clarifications or errata or just future videos that you want to see please leave a comment or if

25:12you just want to say hey what's up what's going on you know just send me a comment whatever i

25:16also wake

25:17up for those in the middle of the night i get i wake up in a cold sweat and i'm

25:20like this it would really

25:22it would really mean the world to me i would really appreciate it so again thank you so much for

25:27watching this video and um enjoy the cool music as as i fade into the darkness which is coming for

25:35us all

25:56so

26:05so

26:06so

26:07so

Category

Transcript

Comments

Recommended