1 00:00:00,610 --> 00:00:03,160 In the previous video, we discussed the privacy. 2 00:00:03,160 --> 00:00:09,370 All parts of the occupancy grid may be a bit of a stretch and instead opted for identifying the regions 3 00:00:09,370 --> 00:00:12,910 that are actually calling for the robot to make a change in this direction. 4 00:00:13,420 --> 00:00:18,640 Now, once we know what points are the points of interest, how do we store this information? 5 00:00:19,300 --> 00:00:25,810 One very useful method of storing information and the connection between those information is cross. 6 00:00:27,740 --> 00:00:33,560 Now graph formula are data structures that is used to represent connection between pairs of elements. 7 00:00:33,860 --> 00:00:39,850 For example, the social network like Facebook can easily be represented using jobs. 8 00:00:40,490 --> 00:00:43,940 Now graph primarily are divided into two components. 9 00:00:44,360 --> 00:00:49,900 Starting with the first component that is the nodes, which is any entity like a person, object or 10 00:00:49,910 --> 00:00:50,270 belief. 11 00:00:50,900 --> 00:00:55,160 Then we have the edges, which represents the connection between these nodes. 12 00:00:55,730 --> 00:01:05,750 Now if you look right here, we have a simple graph that has four nodes A, B, C and D, and as you 13 00:01:05,750 --> 00:01:08,780 can see, it does have a connection with B. 14 00:01:09,920 --> 00:01:13,700 And see what it does not have a connection with. 15 00:01:13,700 --> 00:01:16,850 Dee Dee does have a connection with it. 16 00:01:17,780 --> 00:01:20,840 So this is how of a simple graph is it presented here? 17 00:01:21,560 --> 00:01:27,590 Now let us discuss the different types of graph, starting with the first type that is known as the 18 00:01:27,590 --> 00:01:30,080 directed graph or directed graph. 19 00:01:30,500 --> 00:01:34,040 Here, the edges show connection in a specific order. 20 00:01:34,670 --> 00:01:41,030 For example, if we have Instagram followers when they follow you, it is their connection to you and 21 00:01:41,030 --> 00:01:42,470 you haven't followed them back. 22 00:01:43,460 --> 00:01:49,130 The next step is known as the undirected, where the connection between nodes is mutual. 23 00:01:49,580 --> 00:01:55,430 By example, when you accept a friendship request on Facebook that friendship is mutual and not one 24 00:01:55,430 --> 00:01:55,910 sided. 25 00:01:56,360 --> 00:02:03,710 Hopefully now this can be represented by simply drawing a line between adjacent nodes or two opposite 26 00:02:03,710 --> 00:02:05,540 arrows between edges and nodes. 27 00:02:06,110 --> 00:02:08,270 Both representations are correct. 28 00:02:09,020 --> 00:02:12,080 Speaking of representation, how do we represent a group? 29 00:02:13,080 --> 00:02:18,150 There are two ways to represent a graph, starting with the first that is known as the ID just since 30 00:02:18,150 --> 00:02:18,840 The Matrix. 31 00:02:19,320 --> 00:02:25,920 Now this is a sequential representation as the nodes and the connection are represented by an end cross 32 00:02:25,920 --> 00:02:26,790 and matrix. 33 00:02:27,710 --> 00:02:35,180 So for example, if you look right here, we have an undirected graph, A, B, C, D, here is A has 34 00:02:35,210 --> 00:02:42,890 connection with B, C and D, and this can be represented in and just in time matrix by simply writing 35 00:02:42,890 --> 00:02:50,600 a one against each adjacent nodes for A, B, C, D, and because D does not have a connection. 36 00:02:51,550 --> 00:02:53,620 Connection with DH. 37 00:02:53,800 --> 00:02:56,080 So you can see we have a zero. 38 00:02:57,050 --> 00:02:59,510 For B, for B against D. 39 00:03:00,260 --> 00:03:04,640 And if you look at the second type of representation we have, that is the adjacency list. 40 00:03:05,120 --> 00:03:10,940 This representation is a linked representation because it uses a link list to represent the connection 41 00:03:10,940 --> 00:03:11,750 between nodes. 42 00:03:12,440 --> 00:03:17,150 For example, if we look at the same example that we were studying earlier of an unattractive girl, 43 00:03:17,690 --> 00:03:24,140 he had the connection of beer with B, c, d can be represented as follows in next is b. 44 00:03:24,500 --> 00:03:26,240 B next is C and C. 45 00:03:26,240 --> 00:03:27,080 Next is D. 46 00:03:27,560 --> 00:03:32,150 So this is how a list keeps track of all the neighbor nodes of each particular node. 47 00:03:32,780 --> 00:03:36,770 Now the question arises how do we represent graph for our kids? 48 00:03:40,070 --> 00:03:42,440 Now we will be using adjacency list. 49 00:03:44,380 --> 00:03:50,110 Primarily because of the reason we have a sparse crowd, meaning we have less points of interest to 50 00:03:50,110 --> 00:03:50,560 store. 51 00:03:50,920 --> 00:03:56,980 So adjacency list would be ideal, and it only stores the adjacent neighbors of each particular node 52 00:03:57,400 --> 00:04:00,130 that's causing less overall spatial cost. 53 00:04:00,850 --> 00:04:08,050 The second most important reason is that it just senseless provides a false iteration over all the neighbor 54 00:04:08,050 --> 00:04:09,490 nodes of each particular note. 55 00:04:10,180 --> 00:04:16,660 This property would be particularly useful in pathfinding if we are looking to find an efficient solution. 56 00:04:17,480 --> 00:04:22,240 So this is the reason we'll be using adjacency list reputation for our graphs.