Visualizing Graphs in Python With pyvis | Graph Theory With Python #3

hey there welcome to graph theory with python part 3. in this video you'll learn how to visualize graphs using python along the way you'll learn about special families of graphs and how to write some python functions that will generate those for us before we get started if you haven't seen parts one and two of this series i'll put a link to the playlist right up here i highly recommend you check those out so you'll be caught up and up to speed with what we're going to talk about today and if you'd like to download the code that we're writing in the series you can find it on my github page i'll put a link to the repository on the screen and also down in the video description alright let's get started there are several ways you can visualize graphs using python in this video series we're going to use a package called pi viz it's built on the viz.js javascript framework and it integrates beautifully with jupyter notebooks let's switch to an editor window and i'll show you how to get it installed here we're looking at the terminal windowed in visual studio code i'm in the same directory as the graph.py file that we made in the last video about adjacency lists and adjacency matrices the first thing i'm going to do is create a new virtual environment that will allow me to isolate pi vis and its dependencies and keep them separate from any other packages i have installed on my system to do that i'm going to use the vm module in the standard library i'll start by typing the python3 command followed by the dash m flag then the word vmf and then the name that i'm going to give to the virtual environment directory which i'm going to call dot vm i can also use the prompt flag to give it a name separate from the directory name i'm just going to call it python graphs when i run this it will create a virtual environment in a directory called.vm with a prompt name called python graphs now i need to activate the virtual environment i can do that by running a script that's already been created for me in the dot vm directory i do have to execute it using the source command though now my virtual environment is active and you can see the prompt name python graphs shown here before the prompt in my terminal if you've never worked with virtual environments before or you're a little rusty and need to relearn a few things i highly recommend checking out real python's article or video course on virtual environments i'll put a link to that in the video description now that we've activated the virtual environment the very first thing i'm going to do is upgrade python's pip package manager this is really important using the latest version of pip will help make sure the installation process goes smoothly all right now that pip is updated we can install pi viz to do that we're just going to run a pip install pyvis you can see that pivoz has quite a few dependencies this video was recorded on pi day or march 14 2021. i have no idea what year it is when you're watching this so i don't know what the current state of these packages is in order to make it so that you can follow along and recreate the exact environment that i have here i'm going to freeze all of these dependencies into a text file called requirements.txt i can do that using the pip freeze command that creates a text file called requirements.txt containing all of the dependencies and exact version numbers that i installed in this video here's what the contents of that text file look like okay great we've got pi vis installed now we can actually visualize some graphs let me show you how that works let's start by opening a new python 3 shell the first thing i have to do is import the network class from the pivs.network module the word network here is being used as a synonym for graph that's because graphs are great at modeling networks first i'll create a new network instance let's call it net now that i have a new network instance i can add nodes to it using the add underscore node method let's add two nodes one called zero and one called one to add an edge between nodes zero and 1 i use the add underscore edge method add underscore edge has two parameters one for each of the nodes the edge connects so i'll pass to it 0 and 1. alright so this gives us a really basic graph one with two nodes and one edge connecting those nodes now we can go ahead and visualize it to do that i'm going to use the show method i'm going to pass a string to show that contains the name of an html file that's because pi vis generates a static html file that you can open in a browser to view and interact with the graph let's call it basic.html because it's a pretty basic graph now this doesn't immediately show anything but i can go ahead and quit the reple session and then open that html file to see what it looks like first let's see if the file was actually created yep there it is basic.html let's go ahead and open that when i run the open command it opens up my internet browser and shows me the graph and here's what it looks like we have our two nodes zero and one with the edge connecting them one thing that i like about pi vis is that the default styling looks pretty good i can even interact with the graph by clicking and dragging around vertices pretty cool pi vis even works with directed graphs remember a directed graph is one in which the edges have a direction to them they point from one node towards another one and we usually indicate this by adding a little arrow on the edge that indicates the direction let's head back to the editor and i'll show you how to visualize a directed graph i'll open another python3 shell then i'll import the network class again and create another network instance called net however this time before i create the instance i'm going to set the directed attribute to true now i'll add two nodes 0 and 1. and an edge that connects 0 to 1 starting at 0 and pointing in the direction of 1. finally i'll call the show method and pass to it the same string we did before now i can head back to my browser refresh the page and i should see the directed version of the graph show up look at that nice we can also add multiple edges and loops to a pi vis graph let's head back to the editor again and add a few of those i'm going to continue working with the same network we've just defined i'll start by adding a new edge that starts at node 1 and points in the direction of node 0. now i'm going to add two loops one on the node 0 and one on the node 1. this adds the loop to node 0 and this adds the loop to node 1. i need to show the graph again so i'll use the show method and pass the basic.html string to it again let's head back to our browser and hit refresh to see what that looks like pretty cool one thing to note here is that instead of showing two edges between zero and one it shows one edge but with two arrows on it that's fine okay now that we know a little bit about pi vis let's see how to write a python function that takes a graph object that is of the graph name tuple type we defined in the last video and returns a pivs network instance ready to be shown i'm now looking at the graph.py file we created in the last video we've got our graph named tuple type our adjacency dict function as well as our adjacency matrix function below the adjacency matrix function i'm going to define a new function that allows us to visualize graphs created from the graph name tuple type i'll call that function show let's give the show function a parameter called graph and i'll scroll down to give us a little bit more room on the screen the show function will do two things it's going to create a new pi vis network instance and then call that network's show method in order to create an html file that we can open in a browser to visualize the graph let's start by creating a new network instance and let's call it g we haven't imported pi vis into our file so right now vs code doesn't know what this network thing is let's move back to the top of the file and add the right import all right now that that's imported we're ready to work with our new network instance we need to add all of the nodes in the graph to the network we could write a for loop that loops over each of the nodes in the graph's nodes list and uses the add underscore node method to add them to the network but there's a little bit shorter way that we can do this pi vis networks have a method called add underscore nodes with an s on the end that method accepts a list of nodes to be added to the network let's go ahead and use that now remember graph.nodes is a list of all the nodes in the graph so we can just pass that to the addnodes method to add all of the nodes in the graph to the pi vis network now we need to add the edges just like there's a plural for the add underscore node method there's also a plural for the add underscore edge method add underscore edges let's use that to add all of the edges in the graph to the pi vis network now we're ready to show the graph so we'll call the show method on our pivis network instance since show requires the name of the html file to save the visualization to let's add a parameter to the show function called output underscore file name and we'll pass the argument passed to output underscore file name to the pi vis network's show method now this is already enough for us to show a graph but let's do one last thing let's return the pivoz network instance from this function that way if we want to when we call show we can assign that to a variable that'll allow us to work directly with the pi vis network instance if needed okay we're almost done there's just one thing missing right now this function assumes that graph is undirected so no matter what pi vis is going to treat graph as an undirected graph remember we can control whether or not the pi vis network is directed by setting the directed attribute when we create the network instance the directed attribute should be either true or false and our graph objects have an attribute called is directed which is set to either true or false so we can just assign the value of graph dot is directed to the directed parameter of the pi vis network and last but not least let's document what this function does in a docstring all right let's take our new show function for a spin i'll go ahead and open up my internet browser and put it side by side with my terminal window so that we can see both the code and the output at the same time i'm going to run the graph.py file in interactive mode using the dash i flag that will execute all the code in the file and then drop me into a python shell where i can interact with the code let's create a graph with four nodes 0 1 2 and 3. we can do that by using the range function now let's define a list of 5 edges the first edge will be between the nodes 0 and 1. then we'll add an edge between 1 and 2 an edge between 2 and 3 and an edge between 3 and 0. finally let's add an edge between 0 and 2. now we can create a new graph object using the nodes and edges list we just defined let's call it capital g and let's make this an undirected graph now we can visualize the graph using the show function we just wrote let's name the output file basic.html that way all i have to do is refresh my browser to see this new graph alright we see some output in the terminal that's because the show function returns the pi vis network instance it uses to visualize the graph that's what we're seeing here over in our browser we can refresh the view to see the new graph and there we go we see the four vertices 0 1 2 and 3 and the 5 edges we defined and since pi vis creates an interactive visualization we can drag these edges around a little bit okay now let's check and make sure the show function is working for directed graphs too back in our interactive shell let's recreate the graph g with is directed set to true and now let's pass g to the show function again using the same output file name basic.html when we refresh our browser now we see the directed version of the graph now pyvis gives you pretty extensive control over the style of the visualization you can change the colors for nodes and edges adjust the fill for nodes even give nodes titles for our purposes in this graph theory with python video series we're not going to get into all that what we have here will work just fine for us but if you'd like to see a video explaining in depth how to use pyvis let me know in the comments below actually i'll tell you what if i get 50 thumbs up on this video i'll do another video that explains pi viz in way more depth all right let's stop for a second and take stock of everything we've done so far in this series and if you're enjoying this video please give it a thumbs up it really helps me out and consider subscribing to my channel and clicking the bell icon to get notified whenever i release a new video so far in this graph theory with python video series we saw how graph theory got its start when the mathematician leonard euler solved the seven bridges of konigsberg problem then we learned about the precise mathematical definition of a graph and how to represent graphs as data structures in a python program using an adjacency list or an adjacency matrix and now we've seen how to visualize graphs using the python package pi vis we've developed some tooling that's going to help us investigate graph theory and use python to produce examples and make observations that'll help us discover new things about graphs but before we can get into proving anything about graphs or really going deeper into our investigation it's going to be really useful to have some families of graphs in mind things that we can quickly visualize and work with to get a feel for the kinds of things we're investigating in the rest of this video i'll introduce you to a few families of graphs that'll be really useful to know about the first family of graphs that we're going to talk about are called paths the word path is a really descriptive name here's what the path on three vertices looks like here's the path on four vertices and the path on five vertices now we're going to introduce some notation we call this family p sub n we write it using a capital p with a subscript lowercase n the lowercase n refers to the number of vertices in the path and of course the capital p stands for path we can sort of standardize paths by agreeing to visualize them as a straight horizontal line and we can label the vertices or nodes starting with 0 up to n minus 1 beginning with the leftmost node using the p sub n notation we can also give each of these paths a name for example the first one is p3 the second one is p4 and the third one is p5 i started with p3 but there are two smaller paths p2 for instance is a path on just two vertices and p1 is a path on just one vertex which might seem a little odd because it's literally a graph with just one node and no edges but we still call it the path on one vertex we could also call p1 the trivial graph and you'll hear it commonly referred to this as well it's trivial because it only has a single node and no edges so there's really not anything to talk about another important thing to note here is that all of these are undirected paths that is none of the edges have a direction to them so we're not drawing any arrows on them because paths have such a nice structure we can actually explicitly write out in a general way what the nodes and edges of a path are the vertex set v for a path on n vertices is just the integers 0 through n minus 1. the three dots or ellipses in my set just indicate that every number in between 0 and n minus 1 exists in this set now if n happens to be 1 the path on one vertex then it just contains a single element the number zero for p2 it contains a number zero and one and so on we can also explicitly describe the edge set now for the path on one vertex or the trivial graph the edge set doesn't have any elements it's called an empty set but for anything else it's always going to contain the edge 0 1 and for paths on 3 vertices or more the edge 1 2 all the way up to the edge n minus 2 to n minus 1. that's the edge that connects the last two nodes in the path so these are undirected paths they're a pretty basic family of graphs but there's still a good one to know because when we talk about more complex ideas and graph theory we can come to these very basic examples to see if we can wrap our minds around how it works for something like this family of paths and while we're talking about paths let's head back to our editor and write a python function that returns a graph representing a path on any number of nodes we want we're going to write a function that takes an integer representing the number of nodes in a graph and returns a graph instance representing the path on that number of nodes i'm going to call the function path graph this function will have one parameter the number of nodes in the path i'll call it num underscore nodes and i'll scroll down to give us a little bit more working room like all functions it needs to have a dock string so i'll write one now remember that the vertex set for a graph p n is the set of all integers 0 up to n minus 1. i can create that using a range now remember that the edge set looks something like this i'm using a python list to represent the set but that's okay because that's what edges needs to be anyways the problem is to write this using python code in a way that's clear and easy to understand there are a couple of ways to do it but i'm going to use a list comprehension i'll do this by describing an edge in terms of an index i each edge has the form i i plus one so if i start with number zero the first edge will be zero comma one then when i increments to one the next edge will be one comma two and so on we're going to do this for all numbers i in the range up to num nodes minus one now you might wonder why the minus one the numbers in this range stop at num nodes minus two which means that the last edge in this list will have num nodes minus two here and then num nodes minus 2 plus 1 which is just num nodes minus 1 here that's exactly what we want now that i have that all i have to do is return a new graph instance using those nodes and edges and since this is an undirected path we'll set is directed to false now there's one problem here we talked about the path on one vertex which we would create by setting num nodes to one but what happens when we try to create a range using the number num nodes minus one which in this case will be zero let's open up an interactive shell real quick and see what happens so the range function will take the number zero let's see what that looks like as a list it's actually an empty list that's because the range really starts at zero and ends at one less than zero which is negative one well that doesn't really mean anything so it's an empty list going back to our function let's make sure this is going to behave the way we expect if num nodes is 1 then we will create a list of nodes containing the numbers ranging from zero up to one less than one that has just one number zero that's right for our edges list we're going to create the set of all edges that look like this for every number in the range num nodes minus one which is zero that's an empty range so that means the edges set will end up being an empty list again that's exactly what we want so everything works out just fine and we don't have to worry about setting num nodes to 1 causing any kind of issue but what if we set num nodes to 0 or negative 1. this doesn't make any sense so we'll add a little bit of logic to raise an exception whenever num nodes is strictly less than one okay so here's what we've done if the num nodes parameter is set to zero or less then we're going to raise a value error that says num nodes must be positive this is good practice just to make sure that everything is going to work correctly in the function we're also using an f string which is a python 3.6 and grader specific string interpolation method if you're not familiar with f strings i'll post a link in the video description to an excellent reference for them in fstrings i can include this little bit which when printed to the command line will print num nodes equals followed by the value of num nodes this is just to help in debugging that way we can see what value was passed to pathgraph if anything goes wrong that might help us figure out where an error is there's one last thing that could go wrong what happens if i pass an argument say the string math is awesome or the number 3.14 instead of an integer in that case things are gonna go a little haywire so we need to check that num nodes is actually an integer before we do anything we can do that using the is instance function and if num nodes is not an instance of an integer we'll raise a type error so what we do here is first check whether or not num nodes is an integer and if it isn't we raise a type error that says num nodes must be an integer and displays the type that num nodes actually is again that's just to help us debug in case anything goes wrong the real meat of this function are these three lines here where we create a range containing the number zero up to num nodes minus one and the edges in the path graph directed paths are a lot like undirected paths except that the edges have a direction to them however they can't just have any direction so let's talk about what directed paths look like just like undirected paths we visualize directed paths as a straight horizontal line here's the directed path on three vertices the thing to notice here is that the direction of the edges points from the vertex on the left towards the vertex on the right and that is always the case for example this graph is not a directed path that's because if i start on the leftmost vertex and try to get all the way to the rightmost vertex i can't do it without violating the direction of an edge by convention we're saying the direction should be from left to right however take a look at this directed path in this case the arrows point from the right to the left however these really are the same graph we'll talk more about this idea of two graphs being the same in a later video for now just know that i could turn the graph on the bottom into the graph on the top by just rotating it 180 degrees now i would have to relabel the vertices to make it look exactly the same but you get the idea the code for creating a directed graph looks basically exactly the same as for an undirected graph the only difference is that we're going to set the is directed attribute of our graph instance to true let's head back to our editor encode the function that returns a directed path now we're going to create a function that returns a directed path on the number of nodes we specify we could write an entirely new function but we don't really need to the only difference between a directed path and an undirected path from our perspective is that the graph instance that we create needs to have is directed set to true to handle that we'll add a second parameter to the path graph function called is directed by default we'll have this set to false that way if we call pathgraph without specifying is directed we'll get an undirected path if we do set isdirected to true then we'll get the directed path back but it doesn't quite work as needed right now we need to head down to where we return our graph instant and instead of setting is directed to false pass to it the value of is directed that was passed to the function there we go now we have a nice function that will return both undirected and directed paths for any number of nodes that we want the next family of graphs we're going to talk about are called cycles just like for the family of paths p sub n the lowercase n here represents the number of vertices in the cycle now you might be able to guess from the name cycle what it looks like let's draw an example of a cycle on four vertices the defining feature of a cycle is that i can start on any vertex say this one and walk along an edge say going in the counterclockwise direction and walk across every node and every edge and back up where i started this cycle has four vertices so we'll label it c4 we could also draw c5 and c6 now cycles are in some ways closely related to paths if i remove one of the edges on a cycle i'm left with a path so when we explicitly write out the vertex and edge sets they're going to look kind of similar to paths the vertex set v will always contain the nodes 0 through n minus 1 and the edge set will always contain the edge 0 1 1 2 n minus 2 n minus 1 and that gives us an edge set that looks exactly like the path but we need one more edge an edge between n minus 1 and the node 0. and finally remember we're talking about undirected cycles here now that we know how to describe the vertex and edge sets let's jump back to the editor and write a function that returns a cycle for any number of nodes we want now let's write a function that returns an undirected cycle i'll call that function cycle graph this function will have one parameter the number of nodes like all of our functions we need a docs string that explains what the function does and i'll scroll down so we have a little bit more room to work with here we're actually going to reuse some of the code from the pathgraph function in fact a cycle is just a path that connects the two end vertices with an edge so we can actually start by creating a pathgraph instance let's do that and call it base path now that we have the path all we have to do is add the edge that connects the last vertex in the graph to the first one the last vertex in the graph will have the value num nodes minus one so all we need to do is add the edge num nodes minus one comma zero now all we have to do is return that graph one of the advantages of reusing the path graph function is we don't have to do any type checking or validation on num nodes that will be handled for us automatically when we call the pathgraph function now let's talk about directed cycles just like directed paths directed cycles have every edge pointing in the same direction now it doesn't quite make sense to talk about left and right here but we could say for example that we always draw our nodes in a circle and draw the arrows pointing in say a counterclockwise direction so here's an example of the directed cycle on four vertices now i just drew those edges pointing in the clockwise direction that's all right what's important is that the direction of the edges is always going the same way around in a circle like that here's an example of a directed graph on four nodes that is not a directed cycle the issue here is that if i try to walk along the edges of the graph following the direction of the edge i can't start at one vertex and end up back where i started without violating one of the edge's directions coding the function for directed cycles works just like for undirected cycles we just have to set the is directed property of our graph instance to true let's hop back to the editor and see how to do that rather than writing a new function that returns a directed cycle we can just modify the cycle graph function to handle that for us much like we did with the directed paths we'll add a second parameter called is directed and set it to a default value of false then we'll just pass the value of is directed to the path graph function in order to create the cycle we append an edge to the edges list in the base path the edge that we're appending starts at the vertex num nodes minus 1 and ends at the vertex or points towards the vertex 0. that fits the definition of a directed cycle so we don't need to modify anything here and there we go we now have a cycle graph function that works equally well for undirected and directed cycles the next family of graphs we'll talk about are called complete graphs the notation we use for this family is a capital letter k and a lowercase n subscript the easiest way to describe a complete graph is where you take a set of nodes and add every possible edge between them excluding multiple edges and loops for example here is the complete graph on four vertices every single vertex like this one here is adjacent or has an edge connecting to every other vertex like these three here and that's true no matter which node i picked to start with here's what the complete graph on five vertices looks like just like paths and cycles the vertex set for the complete graph contains the elements 0 through n minus 1. the edge set might be a little bit trickier to describe we can start by adding all edges connected to the first node 0. that would include the edge 0 one zero two all the way up to zero and minus one now we can describe all the edges connected to node one we've already included the edge connecting one to zero so we don't need to write that again remember complete graphs don't include multiple edges so we'll start with the edge one two then we would have to include the edge one three if we had a vertex labeled three and so on up to the edge one and minus one now we have to add all of the edges that are connected to vertex 2. we've already got the edges connecting 2 to 0 and 2 to 1 so we don't have to write those again we would start with the edge 2 3 all the way up to the edge 2 n minus 1. we would continue doing this until we finally get to the node n minus two and when we get there there would be only one edge left that we have to add because we would have each other edge connecting to n minus two already included in the lists above it so the only edge left to add would be n minus 2 and minus 1. so the edge set for complete graphs looks a little bit complicated but really all it is is every possible edge between every node excluding multiple edges and loops one thing to remember here is that we're focusing on undirected graphs a directed complete graph is called a tournament unlike paths and cycles there are many ways to orient or direct the edges in a tournament so we won't be able to write a function that returns a tournament or the tournament on n vertices for us because there could be multiple tournaments on that number of vertices we will talk about tournaments in later videos and when we get there we'll talk about ways to describe orientations that is the directions of the edges and how to write some functions that'll allow us to create tournaments but for now let's just focus on the undirected version the complete graph let's jump over to the editor and write a function that returns a complete graph for any number of nodes we want now we're going to write a function that returns the complete graph on any number of nodes we'll call the function complete graph this function will have one parameter the number of nodes and as usual i'll give it a doc string now we'll just scroll down to give us a little bit more working room and in this case we don't have an existing function we can call that will also handle validation for us so we need to repeat that validation we need to check that num nodes is an integer and also that its value is greater than one we've already got that logic in the path graph function i could just copy and paste it into the complete graph function but we really shouldn't repeat ourselves i'm going to write a new function that checks whether or not some value is acceptable for representing the number of nodes in a graph i'll scroll up and put that above the pathgraph function and i'll call it validate num nodes the reason that i'm using this leading underscore is to indicate that this is a quote-unquote private function that is this function will be used by other functions in my graph.py file but it's not something i expect to be used anywhere else this function needs to have one parameter the number of nodes and of course it needs to have a dock string the code for the validatenum nodes function i'm going to just copy and paste from the pathgraph function and now in my path graph function all i need to do is call the validatenum nodes function and there we go now pathgraph is still validating whether or not num nodes is correct and now we can reuse validate num nodes in our complete graph function great so now we're checking whether or not num nodes is a positive integer the next thing we need to do is create the set of nodes for the graph just like paths and cycles that's the set of all integers from 0 up to num nodes minus 1 so we'll just use a range next we need to create the set of edges and this is where it gets a little bit tricky let's write a for loop that loops over each integer in the range from 0 to num nodes minus 1. you can think of this loop as representing each row in the set of edges we defined when we were explicitly writing out the edges in a complete graph earlier when i is equal to zero we'll build all edges containing zero when i is equal to one we'll build all edges containing one except any edge we already created previously when i is equal to two we'll build all the edges containing two except for any ones previously defined and so on and so forth in order to do that we need to write a second nested for loop now here we have to think a little bit the second index j needs to start at one more than the index i that's because when the index i is zero this for loop is going to create the second element of each edge containing zero the first one will be zero comma one so it needs to start with one now when i is equal to one we need to create each edge containing one that hasn't already been created before but when i was zero we created the edge zero one so we don't need to create that edge again here there's also no loops so we don't need to create the edge one one so we need to start with j equal to two or i plus one which i have a one here and need to fix this range needs to extend all the way up to the number num nodes minus 1 so the second argument to range will be num nodes and finally inside this nested for loop we're going to append the edge i comma j now writing the for loop this way may look a little bit confusing but it kind of mimics the way you might draw a complete graph first you start at node zero and draw every edge connected to zero then you move to the vertex one draw every edge connected to one but there's one you don't have to draw because you already drew it then you move to vertex 2 and draw every edge connected there but there's two that you don't have to draw because you already drew them so in a sense this is kind of an intuitive way to define it but it is not the most efficient nested for loops are pretty slow and if we're looking at a complete graph with millions of nodes this might take a while to create there's a better option and it requires understanding a little bit more about math see there's something called a combination if i have a set of four things and i want to create all possible combinations of two things out of that set those are called two combinations now i could talk forever about what combinations are how many there are and things like this but none of that is really relevant to us here the point is there's a function in the itertools module in the python standard library called combinations we give it a set or a list of things in this case the nodes in the graph and tell it what size we want the combinations to be in this case two because we want every edge every possible pair of two things in the set of nodes that will generate all of the edges for us in a single line of code and much more efficiently than this nested for loop so we'll head up to the top of our graph.py file and import the combinations function from the intertools module now i can head back down to my complete graph function and replace this entire for loop with a single line we'll call the combinations function the first thing it needs is an iterable or a list of things we're going to take the combinations from that's going to be our list of nodes the next thing it needs is the size of the combinations to make since we're making edges which are pairs of nodes the size needs to be 2. that's going to generate all the edges for us pretty nifty huh the only downside is that it doesn't return a list but that doesn't really matter we can turn it into a list by wrapping this whole thing with the list function and there we go we've just replaced a nested for loop with a single line of code i'm a huge fan of the itertools module if you're not familiar with it or you're a little bit rusty i'll post a link in the video description to an article that i wrote for real python on theater tools module now that we have our nodes and edges list all we need to do is return a graph instance built from those nodes and edges and since complete graphs are undirected we'll set is directed to false the final family of graphs we're going to look at are called stars we use the notation capital s and subscript lowercase n minus 1 to denote the star on n nodes this might look a little confusing but remember this n is still the number of nodes you'll see why we use this notation in a little bit here's an example of s3 the star on four nodes there is one node which we're always going to label zero that's in the center and n minus one nodes in this case three that are all connected to the central node zero and nothing else here's an example of s4 the star on five nodes once again we have a vertex in the center which we label zero and four other nodes that are all connected only to zero as usual our vertex set v is the set of all numbers zero to n minus one it's also easy to describe the edge set the edge set contains the edge 0 1 0 2 up to 0 and minus 1. it's important to remember that we're talking about undirected graphs here just like directed complete graphs which are called tournaments there's a number of ways to orient or direct the edges for a star some edges could be pointing towards zero and others away from zero there's lots of things that can happen so there's not really an easy way to generate the directed star it doesn't exist for undirected stars though we're just fine let's hop back to our editor and write a function that returns the star on any number of nodes we want now we're going to write a function that returns a star graph i'll call the function star graph and it'll have one parameter the number of nodes as always we need a docs string and i'll scroll down to give us a little bit more room to work with here the first thing we need to do is validate num nodes that way if anyone tries to do anything silly like pass a string or a floating point number we catch it and nothing goes haywire next we'll create our set of nodes or list of nodes which again is just the range num nodes and then we'll create our set of edges now for a star every edge is connected to the center vertex which we agreed to always label zero so every edge is going to start with zero and end with something else i'll call that something else i that number i is gonna range from one all the way up to num nodes minus one in python that's just the range one to num nodes so we can write this using a list comprehension by looping over every i in that range now that we have our nodes and edges we'll just return the graph instance built from those and since these are undirected we'll set is directed to false and that's it now we have a function to return the star graph on any number of nodes we like okay so now that we have a bunch of functions that can create special families of graphs for us it'd be pretty cool to visualize them wouldn't it let's hop into an interactive shell and see what these graphs look like when we visualize them with pi viz okay so on the right hand side of the screen you can see my terminal window and on the left hand side i've got a browser tab open ready to load up the html file we create with pybiz i'm going to run the graph.py file in interactive mode and let's start by creating a path on five vertices i'll call it p remember to visualize the graph we use the show function so i'll type show p and i'll call the output file name graph.html all right i'm going to quit the repl and open up that file and there we go we've got the path on five vertices now the way that pi vis works it doesn't exactly draw it as a horizontal line but that's okay we still see that it's got five vertices zero one two three and four and it's got the edges going from zero to one 1 to 2 2 3 and 3 to 4. it's exactly the path graph let's open up that interactive session again and try looking at the directed version let's create a new path graph called p and call the path graph function again on 5 vertices but this time with is directed set to true now i'll show p and save it to the same graph.html files before now all i should have to do is refresh my browser to see the directed version of the path there we go we could do the same thing for cycles or complete graphs or stars let's look at the star on four vertices i'll call it s now when i refresh my browser i get the star on four vertices pretty sweet so now you've seen how to visualize a graph data structure using pi vis you saw how to create a pi vis network instance add some nodes and edges to it and then show it by saving it to an html file and opening it in a browser you also learned about several different families of graphs including paths cycles complete graphs and stars we wrote some python functions to generate those for us and we took a look at what some of those look like by visualizing them in pipe is in the next video i'll show you how to integrate pi vis with jupiter notebooks jupiter notebooks are a great tool for doing exploratory programming we're going to use them throughout the rest of the series in order to actually do some graph theory and now that we have several families of graphs that we can create on command we're in a great spot to actually start learning some graph theory so you'll definitely want to stay tuned and check out the next video if you enjoyed this video please give it a thumbs up it really helps me grow my channel and consider subscribing if you haven't already and hit the bell icon to get notified whenever i publish a new video thanks so much for watching i'm david amos i'll see you in the next video

Channel: David Amos

Views: 1,653

Rating: 5 out of 5

Keywords: graph visualization python, python graph theory, graph theory in python, python graph visualization, pyvis network visualization, how to visualize graphs in python, visualizing graphs in python with pyvis, python pyvis tutorial, using pyvis to visualize graphs, how to use pyvis to visualize graphs in python, visualizing different graphs in python, can you visualize a graph in python, how to use pyvis to visualize networks, python network visualization, using pyvis in python

Id: 7MQ19mADAV8

Length: 45min 42sec (2742 seconds)

Published: Tue Mar 16 2021