Bestand wählen
Merken

Optimization using Flow Networks in NetworkX.

Embed Code
Video lizenzieren

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
hello everyone my name is fish about and I am a student at IIT lines see the topical to distort population using phone and books on the talk and is seen as in 2 parts in the 1st part we have take basic introduction to network x like the it's celebrity the useful for dealing with jobs in 2nd but arguably discussed the thing about what are the flow networks what is the maximum flow or what is the minimum got these things out the mathematical concepts but we will see how we can use this concepts for dealing with some optimization problems are for adults are generally used for their own getting optimized solution was something I and these days there also used for an approximate solution like in emergency evacuation planning and all that so and in the tub but we discuss a problem called project selection problem and we we discuss how we can model the problem in peripheral network and rule that the minimum cockroach problem gives us the solution and the 5 to 6 lines of called our ideas so the problem in that protects so 1st the are so a network acts we have 4 types of graphs for Steve the simple graph undirected graph is do not have any palate edges and that is directed graph which have their ladies and an undirected graph bad alleges and similarly adopted by lasers are so 1st of all is a bit of basic functions like had no no convening easier and then there are of begin at some attributes the nor to let go of the the the usual of these algorithms and when booting is the node will not need to be I can be any hashable object like or it can be staying it can be a mathematical function or unit can you got so like I added the goblet cells as and what takes into the draft and some pretty basic function like due to most uses the nodes beginning to go the notes on the merits of their and for adding as is there is an edge it would be it would be would not was newly added as a vertex in the graph but it will automatically add them as but that's and in the graph and read some collars and all that of for x the edge you can access them just like you access MIT dimension so G proof I N G 5 2 of the same thing because we are dealing with undirected graphs and you can add that as is from a list as well some them you can add notes from a list as well and some previous function like number of phase is number of nodes number of cell tools that x a lot of this function which come very handy Red writing small script when you're dealing with gasses and this is the thing I like more like you can draw the GOP it is easy becomes very handy when you're dealing with very last last are like the you are fine and trying to find some relationship between the population and all that and it can be customized easily you can change the the Icelanders Stella and everything like that but so did now the nodes noting Jesus like our the when 1 was a mathematical function sign 1 was the Gothic says when strings somewhat engages so you can just and want them to end users if you want and keep them all the labels too so like here the order nor that was a mathematical function sign is now number 5 so the Gotham the same just the labeling is changed it's pretty easy to do there is is print information and something like that and just some algorithms that gives us 1 good year I wouldn't that and discussing a lot of all almost all the gravitons are available at the network acts like the connected components are is the set of vertices that are connected to each other means you can use to each other just by 1 more edges so you know 1 2 inseminator out in different connected components so if I your 7 there and they will be in the same connected component you can the nor to create a new graph and you can get union intersection of the graphs the shortest part is just a bit stand using 2 D Shadow them target Fatah between 10 and produce an Arabic because the and produce not have anybody and then and ensure the spot and injuring created you disseminate and then is dominating set like if you know about the dominating center I'm just showing you the simple algorithms so this is just a simple and of interaction like complicated to golf added and and Nolde had an edge in the network acts no we will use the CIA something about the floors and the cut in the graph so 1st of all I are
legit see about the history of the flow network flows so around
in 1955 some US Air Force on such a published that classified as search in in this study the 40 reasons all Soviet Union and the Soviet Union was connected to East aside like Eastern European countries within the networks so they studied for P of the reasons 105 entities so as is just that really the network between 2 regions so they were studying it and they they give a very eat at each has and the rate was how much material you can passed from 1 season to another what their intention was just
like this guest the 1 that won the in networks they wanted good disconnect the Soviet Union with its European countries and there was a cost littered with each but there was costly Likud bonding these billion network so so the phone a set of edges so that bombing them was the cheapest and the quot cheapest to disconnect the Soviet Union redo from its European countries and they were successful so let's see what they embody the use so what's a flow
network flow network is a directed graph we generally do not have a as is and we have 2 very distinct what's in it when is the source and another is the same source is from there the floor starts and scene is very the flow pants and for each as in the flow network each other capaci city attached to it like the capacity is the maximum amount of material that you control through that much so this is an example from the like as is the source of these this thing and you're not the capacities of the order as is is like for our camps if your dead as before this 15 minutes you can 15 unit of material to batch as to so so you can support to the display origin so the flow from the source as to since the is a function which satisfy store them chance like the floor on any as is decadent dual obviously and it should be less than the capacity of the that is the object edge and for every vertex that is not the source and the sink we have attenuation of through like that for every vertex other than source and sink this flow that is coming is equally good for that is going out of the vertex and the total flow is how much we're getting at the same that this is an example of floor so here we are pushing arm for unit of material from source S to cool then from group T T 2 6 and 6 2 4 this is a valid for because we are not making any of the junction the flow is less than the captors again every time and all the vertex had the conservation of the so this is the maximum flow that we can get from this from work soviet pushing the flow value of 28 from the source getting the at the sink and all that as is as satisfying the function like the floor opened is less than the capacity of the flow and for each vertex the conjugation of Freud's working you be cannot last more than 20 unit of flow through this network just remember the number if you can so this is the maximum flow and nobody John to the guts of so lava discussed but at what is the maximum flow in a graph number we discussed what to the top of a graph so and cut of a graph V Di to partition the graph into 2 subsets the and B generally we say that source belongs to a and sing belongs to be so the idea here is to be like this book cut some as this says that the maximum flow from source as saying the becomes due just like the it forces such as wanted they do not want it any shipment any material flow from some Union to the Eastern European countries so they just wanted to cut some really networks in between the capacity of the partition is calculated as the sum of the capacities of the edges that are going from Sec III to the 2nd B we are not conceding that is that going from set B the set the because they will not participate in the flow so the capacity of the fact is that that the city of that as is that we got that are going from set III was set B Our
the pretty simple got all the jobs will be to disconnect the source from the graph like here we had just disconnecting the source from the graph Soviet but in all the the edges that are connected to the source which have kept city then 5 and 15 so the price cap city of the sky is type but this is not the optimal case that we want to find the minimum but this will be the this is the TV gets like we can order separate the source from the network so you want to find the minimum cut and this is the minimum cut
like if we destroyed as from x to cool 2 2 6 and 7 to the the sink then the cap city of the country began to perceive the standard which is 28 and are the max rule was also currently so this is another story that some guys from 2 Soviet Union also studied the same network at different time they wanted a good team divot calculating how much material they can actually passed from Soviet Union to European countries and the Air Force such a wanted to cut the network so they actually found the same number if you give them the same thing so in every metric flow the max flow
is falling is equal to the minimum cut so this is the right word for for question
be this term that many network the value of the max flow is always equal to the minimum cut they can of all the floors and cut of the graph are shown in the same from network so you can see that some of the deficit is of the current flows of God and the floors as seen it and is equal to 20 so
but other application of network flow metaphors are used in Napa connectivity by part matching use them to find the minimum number of please then need to so all the flights used in you may select segmentation cool anymore unintercepted that background the foreground of an image it's use in project selection the true discussed it using based what initial like they eliminated the deems bit which do not have any chance of going further now we go to the project
selection problem there will be a little bit of mathematics and more so you have a company which need to carry out some projects and let's say you have a set of projects the and it at the project is associated a value the revenue of the project so it the PAS get Bengio than the project is a profitable project like you are gaining some new clients and if the a smaller than dual then it is a losing project like unit but has some new eyes and just like India last NATO the projects are interdependent but you need to do some project fondling another so some projects IP the because it often other projects
so we are dealing with a graph G there it as from K to be show was that you need to complete the project before going project 8 so now we need to find a subset of project which gives us the maximum profit like a subset of the project which is complete in itself like be arguing all the PD preserve the projects that appear in more and more the profit is maximum so just like
this that they're looking for the maximum profit and projects we need to do so
hot how we would reduce the problem to a network flow so 1st of all the problems discussed right now and and this is in a set of projects we want to go there is no potential source and sink in this problem so 1st of all we will make a source and a sink for the problem and now we need to add as more as more as is more conditions between which in the projects so for every project that have a project what you do have a new baby add an edge between source and the project the cap city of the revenue of the present and for every project that have a negative revenue vivid add an edge from the project Buddhist saying the negative revenue like the body via doing it for the projects with negative revenue so it means that city of the as humans for and and so on the and
as is that word given us in the graph like the edges that he presented the relations between the project the project of the Museum of 1 another we will send the capacity of these as is with the high number of because why do out the of finding that that set of the network we do not want to cut those as because if you cut those as is the view nor objective feasible project I'm feasible set of projects at the at that in a pity because it as it means we have missing somebody quiz it for some project that we are taking so will make the capacity of these as is will be really high numbers so that they are not included in the so if you make it would be equal to the sum all boys did avenues it fine so now we have presented the graph inbred metric flow we have the types of edges when he's going from the source the projects which have course the revenue the other type of as is odd the interrelated and is like this some predicts that the it off now the project and the type of tied by professors art as is going from the project with negative revenue for the same so not so let's see what we but the
text but would be the expected value of this graph so this bit of mathematics so are we have 2 types of is in our graph and the absolutely of you know because in that the because it as is because they have the duty city so we will be cut included surprise is 1 that is going from the source to the project and 2nd which is going from the project with the same so when we have that in a on a editors going from source to the project Dick undervalued contributes to the there is the 2nd element in the fire in the 1st line and then if they're including a project with negative revenue due to the PDQ's new then the cut in from it from the the same site so it will be but it will be contributing the 1st hour of the that so I'll give you can expand the 2nd on like the summation of all the i man i does not belong to set the we can expand the a summation of IEEE when I belong to the whole project subject summation of PA than I belonging to a the subset so it lead user today days the summation of PA when I belonging to complete set the minus profit of the so because this is the profit of the that are like if I take the summation of all the PIC in us so subset that is the profit dating from the so the cut value is reduced the summation of the of each the is get NGO and I belonging to art set B minus profit of 8 note since the 1st term is a constant for a given set of project we see the effect of dark is a constant minus profit of the so if you minimize the cut we really maximizing of profits so but now you're that the minimum cut of the graph gives us the site of projects that have the maximum now we will
just go for an example like this is it there are some projects with some approach was given you some have negative revenue and there is indeed a better interdependence between these projects now we need to select projects which have the highest 7 new and debt and that is it feasible set so I this it's not what you would do it by hand reminded just like by just saying it so we will just silly but in the whole world out in natural and use the mean and the function of medical text to find a solution so for the net
control are really be creating a director got the land for the full I can point you so Langford for we will be getting it directed graphs and they're like the image as shown here I'm adding
that as is Amen really I mean if each of you will be using that with them skip it will you will not be adding the as is manually
so added as is the pairwise all that is and our the needed to send the capsid city of these as is to really high number and networks goodbye before like I'm not mention the capacitance these as is so we could consider that the capacity of these as is is infinite to 946 and calculated the sum of all the PI that are greater than dual and that are present in our set let be so that is the cost and that we found in the form of everyday life and so if we find the minimum cut and next of minimum power from source to sink we see the value of the country's 21 and we get 2 sets forward at any level above 14 minus 30 minus the read the source so the 2nd the source is the set we should choose it is the feasible set which has the maximum profit and to the subjective accepting the problem but if is something that minimum got from the constant review get out of a new life 40 T is the total revenue you can get choosing projects
from this the out like if you choose all the projects on the left side of minus 1 we have lot OK this standard of slant
Grand questions yes at Vanderbilt any versions bit if without yes we have time for a very long time it and again in the unit of time to move through this report on the In the
Subtraktion
Bit
Extrempunkt
Hausdorff-Dimension
Hochdruck
t-Test
Automatische Handlungsplanung
Zahlenbereich
Interaktives Fernsehen
Zellularer Automat
Computeranimation
Homepage
Knotenmenge
Einheit <Mathematik>
Algorithmus
Software
Vorzeichen <Mathematik>
Datennetz
Trennschärfe <Statistik>
Datentyp
Abschattung
Skript <Programm>
Schnitt <Graphentheorie>
Peripheres Gerät
Phasenumwandlung
Attributierte Grammatik
Funktion <Mathematik>
Einfach zusammenhängender Raum
Lineares Funktional
Approximation
Booten
Graph
LASER <Mikrocomputer>
Globale Optimierung
Optimierungsproblem
Mailing-Liste
Schlussregel
Arithmetisches Mittel
Menge
Beweistheorie
ATM
Mereologie
Projektive Ebene
Information
Graphentheorie
Zeichenkette
Beobachtungsstudie
Software
Datennetz
Globale Optimierung
Bitrate
Dialekt
Computeranimation
Partitionsfunktion
Kanalkapazität
Gewichtete Summe
Große Vereinheitlichung
Total <Mathematik>
Extrempunkt
Datensichtgerät
Gruppenkeim
Zahlenbereich
Kugelkappe
Extrempunkt
Gerichteter Graph
Computeranimation
Demoszene <Programmierung>
Graph
Open Source
Knotenmenge
Einheit <Mathematik>
Keilförmige Anordnung
Software
Datennetz
Speicher <Informatik>
Schnitt <Graphentheorie>
Parallele Schnittstelle
Lineares Funktional
Graph
Kanalkapazität
Quellcode
Knotenmenge
Partitionsfunktion
Objekt <Kategorie>
Knotenpunkt
Funktion <Mathematik>
Menge
Energieerhaltung
Stapelverarbeitung
Innerer Automorphismus
Subtraktion
Kanalkapazität
Graph
Extrempunkt
Güte der Anpassung
Zahlenbereich
Schlussregel
Quellcode
Extrempunkt
Gerichteter Graph
Computeranimation
Kugelkappe
Software
Prozess <Informatik>
Datentyp
Schnitt <Graphentheorie>
Standardabweichung
Theorem
Graph
Software
Extrempunkt
Rechter Winkel
Datennetz
Grundsätze ordnungsmäßiger Datenverarbeitung
Strömungsrichtung
Wort <Informatik>
Term
Schnitt <Graphentheorie>
Computeranimation
Einfach zusammenhängender Raum
Bit
Zusammenhängender Graph
Mathematik
Kartesische Koordinaten
Übertrag
Computeranimation
Einheit <Mathematik>
Bildsegmentierung
Menge
Software
Eliminationsverfahren
Datennetz
Trennschärfe <Statistik>
Mereologie
Projektive Ebene
Bildgebendes Verfahren
Data Mining
Teilmenge
Service provider
Graph
Graph
Extrempunkt
Projektive Ebene
Stochastische Abhängigkeit
Computeranimation
Vektorpotenzial
Kanalkapazität
Sichtenkonzept
Gewichtete Summe
Graph
Feasibility-Studie
Relativitätstheorie
Kanalkapazität
Quellcode
Gerichteter Graph
Computeranimation
Kugelkappe
Objekt <Kategorie>
Open Source
Negative Zahl
Keilförmige Anordnung
Menge
Software
Datennetz
Konditionszahl
Datentyp
Projektive Ebene
Wort <Informatik>
Soundverarbeitung
Lineares Funktional
Web Site
Bit
Gewicht <Mathematik>
Gewichtete Summe
Mathematik
Graph
Extrempunkt
Element <Mathematik>
Quellcode
Term
Computeranimation
Arithmetisches Mittel
Konstante
Teilmenge
Texteditor
Negative Zahl
Menge
Datentyp
Projektive Ebene
Schnitt <Graphentheorie>
Metropolitan area network
Graph
Gamecontroller
Bildgebendes Verfahren
Computeranimation
Videospiel
Gewichtete Summe
Extrempunkt
Kanalkapazität
Zahlenbereich
Paarvergleich
Quellcode
Computeranimation
Übergang
Menge
Software
Total <Mathematik>
Projektive Ebene
Schnitt <Graphentheorie>
Standardabweichung
Leistung <Physik>
Einheit <Mathematik>
Versionsverwaltung
Bildschirmfenster
Verkehrsinformation