# Traversing Mazes the pythonic way and other Algorithmic Adventures

42 views

Citation of segment
Embed Code

 Title Traversing Mazes the pythonic way and other Algorithmic Adventures Title of Series EuroPython 2014 Part Number 67 Number of Parts 120 Author Maggio, Valerio License CC Attribution 3.0 Unported:You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. DOI 10.5446/20047 Publisher EuroPython Release Date 2014 Language English Production Place Berlin

 Subject Area Computer Science Abstract Valerio Maggio - Traversing Mazes the pythonic way and other Algorithmic Adventures Graphs define a powerful mental (and mathematical) model of structure, representing the building blocks of formulations and/or solutions for many hard problems. In this talk, graphs and (some of the) main graph-related algorithms will be analysed from a very pythonic angle: the Zen of Python (e.g., beautiful is better than ugly, simple is better than complex, readability counts). Keywords EuroPython Conference EP 2014 EuroPython 2014
Series
Annotations
Transcript
the
the guy thanks a lot for coming and very excited to be here today In this talk I would like to talk about something I like it a lot in computer science which is algorithms and in particular graph algorithms that are graphs are great data structures and almost useful for every problem you solve every in your everyday code OK so the
said comes in different flavors we may have directed or undirected graphs in the the figure you may see that the edges house and and and the notion of directions is the are unweighted or weighted graphs work sorry were the there is not a weights on the on the edges that there may be simple or non simple graphs the non-simple right here means that there's some edges make that may require some special handling in your in our algorithm for instance and this case self loops or groups in general uh we'll see another example of this in a few minutes and are sometimes thermal will be group ages that may be it may be incident multiple times in the signal in that case there will be a that will be graph not graph action OK so we may have cycling versus psychic graphs and understands for and cited references a tree uh trees are connected STT and undirected graphs we may have sold the well known in the so called Don which stands for directed acyclic graphs and we'd actually be made the applied topological sorting and stuff like that this is that these are called concepts for it a from very basic in introductory algorithmic blasts can and finally we may have a label advertis labeled graphs where there is a label on nodes so versus on the graph a graphs may be its forests or maybe bands in which refers to the number of edges in the graph uh and last but not least on graphs may be explicit or implicit this is what I was referring before when I told you that graphs are a great big structure and a powerful man mental model because sometimes when you have to deal with with the problem you have to solve such kind of problem you may think to the prom being uh as a graph problem so you may represent your data your problem as a graph and you may apply graph algorithms to your to problem so here we can here we go to the graph representation so finally we we start to see some code and actions of 1 of the most common way to represent
graphs use the education Salazar and something like that that what is additionally so 1 of the most intuitive ways to implement graphs and for each node we can access a list what as we will see in few minutes all its neighbors so this is the idea and this is the graph we're going to have to use the right sample in the next slides again so we have nodes labeled from 8 to age and for simplicity we assume that we number all the notes from a to age assigning a number that goes from 0 to 7 so and minus 1 in Python we want to implement
objections set which shows up In this case we is the shape of the notes from a to and H and then we use create the structure and which is an a list of additionally the uh over all sets are kind of come before just just the mention before Python 274 or Python 3 of you would use the set constructed here but and now we Europe you may
dictionary where that's for and efficiencies X and uh with the structure we are allowed to just 4 membership for neighborhood membership which is still a constant time and we may calculate the degree of a new the other well known structure to represent graphs use the adhesion to metrics and so on In addition Semantics will list all the neighbors for each node of character so uh we want to store of value indicating the presence or the absence of the edge in the graph connecting 2 nodes which is true or false instance 0 1 1 atmosphere respectively OK and we may try to implement in addition metrics with nested lists the we may argue that this is not a and actually matrix this is a list of lists of guide this just implementation details of Python this just to adjust just to do that sort of proof of concept of and so a with this
structure we are able to implement we're able to test for membership as usual were able to to to calculate the degree of the nodes and of course you may substitute this homemade implementation of the metrics using for instance new pi race cancer which is of course even more efficient and if we will have time I will uh I would like to to talk about the the sci-fi graph implementation and already in the library of uh all sci-fi token of the
the same ways of more than once a cat cover the basic idea is backtracking so the idea is some looking in any direction once and then backtracked whenever you came to dead end or an intersection that you are ready to walk through to avoid cycles this is the basic idea and we will see and details of this 1 OK so I'm sorry for the the formatting this this may be due to the the font size the
server that we may have this kind of functions in Python which is the arbitrary walk can we assume as said before we assume our graph represented as a dictionary agency set and we have an input and an S node which is the starting point OK so we select a random starting point or the point the point where we are and how we have to structures that P and acute uh structures these the predecessors to use the set of the nodes to
be we selected randomly uh we simply we add to the to the to the set to the starting point and we traits while Q while the the the the set Q has elements inside we pick 1 element in the queue completely arbitrary OK I by using that you don't popped method and for every node switches in the which is incident to the you know to what has not been visited yet we and there's no to the you and then we sort the predecessor so in this case we walked through the to do graph 1 step the step by step I actually this algorithm will travesti a single connected component OK so we'll try we will weird you we will find the connected components of a graph starting from the uh from at a given node p is that processes 3 if
you would like to be uh if you would like to get all the connected components in graph we might I rate only ever every node in the graph and we call the walk functions and we use this is simply um updates the structure of a scene which is a set of this is nodes again OK well thank you could have the time complexity of this algorithm is status of the plus of these so this the which is the complexity of almost every traversal of a but just a little another detail about this is the important point here is that when we select the notes we want to do this if we use real on
the the the pop method here on the set which takes randomly an element in the sector of character so this is why this is called an arbitrary uh and that's if
we want to go deep so we want to apply the on the so called adapt 1st trouble so we might use another trick so instead of picking randomly the the the elements in the In this structure we might use a structure that task of the size of a predefined particle to get the elements in this case in the case of the death 1st proposal is the last in 1st out particles cat but this is a recursive implementation but in Python where we may we generally we made every always translated custom implementation to a unintelligible 1 In this case we rely on the list structure mechanics so every time we at the end up to a node which is which is new a week extend the the the frames to the the set of incidence nodes to do today to be you want of God and you know a mock implementation we use a set of characters so we would risk having the same nodes scheduled from more than 1 this OK so this is why the depth-first traversal yes more efficient in general case in the DFS we use the Allies uh therefore use so every node is scheduled for only once if you want to generalize this role so we might write this function which is the progress and um did the did the type of turbo so we're going to my depends on the
structure we're going to use for the french OK in general this is a set which is very similar to the arbitrary walk already showed a few slides go if we use the the list of so the Python lists these will end up to be depth-first 1st reversal and using the yield that allows for it lazy iterations so on uh it will may create an generated Python which is very very useful and this is more efficient for dance and the graphs can and that's it for yes thank you and that's it for it and the mazes OK but what about the infinite mazes and unweighted shortest path a so far the over EGA behaviors 4th deft 1st for fossils have hasn't the a problem actually the problem of the dead dead 1st reversal of the 1st search is that you may run for ages and never get back a character so in case of very very deep graph the graph the depth 1st reversal is not a good is not a good choice that in fact in case of visiting of trolling the graph of the web the adapt 1st proposal is not that the solution can in general the debris uh the the distillate Bayesian here's another kind of 2 rules so which is the breadth 1st search at that I'm going to talk about now and what if we would like to follow the shortest path from s and amazing so in this case the shoppers sparse means the minimum number of the intersection of time the 1st attempt is the iterative deepening their 1st search and I'm not going into the details of this ordering the basic idea is that this algorithm applies a depth-first search for causal many times with different our death limits OK kind but this algorithm led to another well known algorithm which is the breath 1st search breath 1st search is versatility the ITER DFS so the idea of a version of the depth-first-search but if it uses a different our structure OK in disguise the daft breath 1st search for users are um a structure which is a Q and follow that follows the FIFO set first-come-first-served uh which is the 1st the 1st of words and then we may be implemented in Python using the DTD structure which is in the standard library in this for a very simple and very retrieval to to implement the did you actually corresponds to a double links to in Python as you may know that ends up in this case we rely on the top-left function to be get the element we want to start visiting start traversing and the proper leftists constant time because of the implementation of the uh the you structure the complexity of overall breath 1st search is always again that's out of the each of the dimension of edges plus the dimension of purchases and it can be demonstrated that the birth the BFS calculus always apparent
and in case of weighted graphs and other well known problem in computer science and and algorithms in general is the shortest path but this time the short to spot means the path with the minimum within the minimum cost start as these comics as I would like to have a pillow talk sort uh we will talk about the dice for algorithm not the moment for as in this it's a comic OK they and the dice threshold back on directed acyclic graphs relies on the relaxed function which the basic idea of the relaxed function is to propagate the knowledge about the shortest path 1 uh step at a time we looked for an improvement to the publicly known distance to be by trying to take a shortcut through are you which is the they vertex we want to test OK if the structure if the it is a short so if we pass through the you know to cost less than the already computed shortest path we will follow that direction and we tested this 1 step at a time a kind of OK and so on yep did I saw
algorithm applied and exploits the EQ structure which is a priority queue that allows us to get the notes every time we add a note to this structure we Our guaranteed to respect the EP fight uh relations so that and we add the a the notes you in order this is a priority queue so this is a Q order to and we get the elements a with the pop which which returns the the element with the least priority OK of the difference in the relationship between the dice frog remember breath 1st search algorithm is that by allows assigning distances of the then 1 for each step meanwhile the breadth-first-search search basically just expands the search by 1 step of that which happens to have the effect of finding the moles the number of steps it takes to get to and even a to any given node from any source
it can the last example here is the shortest path from all of for all pairs because I story is the sure this past also known as shortest paths Single source so you have and nodes a target that you want to optimized and you start looking for the shortest paths considering that single node the another very interesting problem is the shortest path for all pairs OK so we're interested in getting the shot response for every possible proposal on our graph this is usually solved by a well known algorithm which is the Floyd-Warshall algorithm that relies on a technique an optimization technique which is called dynamic programming also known as don't repeat yourself In mathematics Adamic programming is a method for solving complex problems by breaking them down into simpler subproblems it is applicable to problems 6 beating the properties of overlapping subproblems and optimal substructure so the basic idea is memoization memoization means cash value already solved problems is so instead of recomputing every time the same subproblems we might create
function for memorization implies that in a very elegant way I like this a lot we may create a mammal decorated which relies on which exploits the prox function from fund tools which it wraps is a sort of show that for a partial and another function is a function of Fund tools to sort function which is partial and in this case we create
them this decorator to uh in this broker recreated cash which is the dictionary that stores the values of all the problems OK this is it in action the Floyd-Warshall algorithm is a problem that may relying on the dynamic programming technique because the the basic idea is that uh let us consider the DUP k be the length of the shortest path that exists from node u to node b a if you're only allowed to use that you're only allowed to use the 1st k nodes in your graph right you can decompose the problem as it follows that the distance from node u to node v using the k a notice in your path corresponds to the minimum to the distance from you to the without taking that node or the cost uh from that good of the path that goes from a you to can and k to the maybe this is uh this is uh more clear in this in this slide we might considering whether or not to include not k in the in the the shortest path of character so we calculate the cost of the paths that pass through the k nodes that starting from you and ending to to be if this as I'm not a convenient costs so so if the cost of not taking that node is less than taking that node we simply consider we simply disregarded node but otherwise we include that node the node k initial paths we may I create the so we may implement the Floyd-Warshall algorithm in Python considering 1st since the additional semantics and the distance all the solution in this case we a deep copy the graphs and updates that implies that the the the weights of the of the distances but we may also exploit the memoization a wraps for afford formatting is very often awful
and we made a recursively apply the but this the D function which is the function that calculates the distance from notes using the memorization so if we end up to our distance from a node u v and K already calculated the memorization functions of Y to calculated again and
returns the value thanks to the decorator presented before so that sets some references to buy the logarithms this a very introductory route for this kind of stuff uh of the algorithm this manually as not actually related to fight and but it's very a good reference manual and that's it thank you very much for a definitive thank you very much for their
only any questions there
is the lifetimes lunch break Saul please feel free to ask questions OK so I think it was a very compact introduction thank you very much like what the
Algorithm
Computer animation
Algorithm
Code
Computer science
Data structure
Graph (mathematics)
Complex (psychology)
Group action
Scientific modelling
Source code
Data model
Pointer (computer programming)
Connected space
Mathematics
Forest
Physical system
Social class
Computer icon
Theory of relativity
Infinity
Bit
Staff (military)
Instance (computer science)
Sequence
Graph (mathematics)
System programming
Cycle (graph theory)
Figurate number
Supremum
Ewe language
Algorithm
Mathematical analysis
Graph (mathematics)
Number
Representation (politics)
Data structure
Weight function
Metropolitan area network
Information
Quark
Independence (probability theory)
Set (mathematics)
System call
Local Group
Table (information)
Population density
Word
Loop (music)
Personal digital assistant
Graph (mathematics)
Game theory
Asymptotic analysis
Musical ensemble
System call
Manufacturing execution system
Transportation theory (mathematics)
Code
Multiplication sign
Direction (geometry)
Finitary relation
Parameter (computer programming)
Mereology
Weight
Asymptote
Variance
Formal language
Subset
Image resolution
Positional notation
Bit rate
Square number
Cubic graph
Hex map
Algorithm
Logical constant
Subgraph
Functional (mathematics)
Network topology
Multi-agent system
Computer science
output
Right angle
Data structure
Implementation
Presentation of a group
MIDI
Virtual machine
Electronic program guide
Sparse matrix
Distance
Field (computer science)
Emulation
Power (physics)
Operator (mathematics)
Program slicing
Best, worst and average case
Subtraction
Mutual information
Multiplication
Computer
Expression
Mathematical analysis
Computational complexity theory
Positional notation
Computer animation
Computer network
Vertex (graph theory)
Units of measurement
Matching (graph theory)
Slide rule
Set (mathematics)
Electronic mailing list
Sampling (statistics)
Electronic mailing list
Set (mathematics)
Shape (magazine)
Euler angles
Graph (mathematics)
Graph (mathematics)
Number
Computer animation
Personal digital assistant
Vertex (graph theory)
Object (grammar)
Data structure
Representation (politics)
Complex (psychology)
Code
Multiplication sign
Decision theory
Mathematical singularity
Weight
Data dictionary
Semantics (computer science)
Pointer (computer programming)
Matrix (mathematics)
Square number
Moving average
Algorithm
Binary code
Electronic mailing list
Sound effect
Range (statistics)
Drop (liquid)
Bit
Instance (computer science)
Graph (mathematics)
Metric tensor
Maxima and minima
Degree (graph theory)
Proof theory
Arithmetic mean
Sparse matrix
Vector space
Data storage device
Uniform resource name
Normal (geometry)
Convex hull
Pattern language
Quicksort
Representation (politics)
Permian
Point (geometry)
Pressure
Slide rule
Neighbourhood (graph theory)
Implementation
Set (mathematics)
Line (geometry)
Electronic program guide
Electronic mailing list
Graph (mathematics)
Event horizon
Emulation
2 (number)
Number
Population density
Representation (politics)
Software testing
Data structure
Computer-assisted translation
Best, worst and average case
Subtraction
Associative property
Key (cryptography)
Information
Sine
Poisson-Klammer
Element (mathematics)
Expression
Neighbourhood (graph theory)
Set (mathematics)
Graph theory
Computer animation
Personal digital assistant
Blog
Computer network
Vertex (graph theory)
Graph (mathematics)
Library (computing)
Manufacturing execution system
Ferry Corsten
Multiplication sign
Parameter (computer programming)
Weight
Semantics (computer science)
Traverse (surveying)
Storage area network
Pointer (computer programming)
Video game
Type theory
Bit rate
Exception handling
Social class
Thumbnail
Metropolitan area network
Algorithm
Spacetime
Binary code
Electronic mailing list
Infinity
Instance (computer science)
Graph (mathematics)
Metric tensor
Connected space
Degree (graph theory)
Category of being
Arithmetic mean
Dreiecksmatrix
Network topology
Uniform resource name
Computer cluster
Computer science
Representation (politics)
Data type
Reverse engineering
Row (database)
Field (mathematics)
Wide area network
Point (geometry)
Slide rule
Implementation
Presentation of a group
Diagonal
Electronic mailing list
Graph (mathematics)
Rule of inference
Number
Revision control
Operating system
Representation (politics)
Software testing
Data structure
Normal (geometry)
Diagonal matrix
Subtraction
Form (programming)
Condition number
Rule of inference
Information
Element (mathematics)
Weight
Set (mathematics)
Line (geometry)
Loop (music)
Maize
Computer animation
Personal digital assistant
Universe (mathematics)
Vertex (graph theory)
Matrix (mathematics)
Library (computing)
Point (geometry)
Dialect
Server (computing)
File format
Direction (geometry)
Set (mathematics)
Graph (mathematics)
Computer font
Functional (mathematics)
MKS system of units
Computer animation
Vertex (graph theory)
output
Personal area network
Cycle (graph theory)
Data structure
Computer-assisted translation
Units of measurement
Point (geometry)
Complex (psychology)
Algorithm
Multiplication sign
Element (mathematics)
Set (mathematics)
Graph (mathematics)
Functional (mathematics)
Demoscene
Traverse (surveying)
Connected space
Component-based software engineering
Connected space
Computer animation
Personal digital assistant
Vertex (graph theory)
Queue (abstract data type)
Data structure
Software engineering
Implementation
Multiplication sign
Structural mechanics
Graph (mathematics)
Discrete element method
Connected space
Physical law
Data structure
Computer-assisted translation
Recursion
Dean number
God
Turbo-Code
Torus
Element (mathematics)
Electronic mailing list
Set (mathematics)
Depth-first search
Functional (mathematics)
Frame problem
Maxima and minima
Component-based software engineering
Particle system
Computer animation
Personal digital assistant
Uniform resource name
Vertex (graph theory)
Landau theory
Units of measurement
Arithmetic progression
Data type
Logical constant
Axiom of choice
Complex (psychology)
Length
Multiplication sign
Direction (geometry)
Weight
Proper map
Web 2.0
Summation
Maxima and minima
Bayesian network
Algorithm
Keyboard shortcut
Moment (mathematics)
Infinity
Functional (mathematics)
Root
Hausdorff dimension
Computer science
Quicksort
Electric generator
Reverse engineering
Slide rule
Implementation
Division (mathematics)
Infinity
Graph (mathematics)
Distance
Rule of inference
Thresholding (image processing)
Number
Revision control
4 (number)
Goodness of fit
Causality
Data structure
Weight function
Element (mathematics)
Length
Stack (abstract data type)
Depth-first search
Calculus
Set (mathematics)
Limit (category theory)
Dijkstra's algorithm
Word
Maize
Computer animation
Personal digital assistant
Function (mathematics)
Information retrieval
Iteration
Graph (mathematics)
Document Type Definition
Units of measurement
Library (computing)
Computer programming
Algorithm
Multiplication sign
Source code
MIDI
Graph (mathematics)
Distance
Number
Mathematics
Single-precision floating-point format
Aerodynamics
Data structure
Subtraction
Priority queue
Algorithm
Theory of relativity
Element (mathematics)
Sound effect
Computer programming
Dijkstra's algorithm
Category of being
Computer animation
Uniform resource name
Search algorithm
Vertex (graph theory)
Dependent and independent variables
Mathematical optimization
Computer programming
Slide rule
Group action
Algorithm
Length
Correspondence (mathematics)
Dynamical system
Weight
Distance
Graph (mathematics)
Semantics (computer science)
Emulation
Maxima and minima
Motion blur
Aerodynamics
Vertex (graph theory)
Algorithm
File format
Weight
Computer programming
Functional (mathematics)
Distance
Maxima and minima
Computer animation
Personal digital assistant
Data storage device
Vertex (graph theory)
Right angle
Graph (mathematics)
Quicksort
Service-oriented architecture
Units of measurement
Matrix (mathematics)
Algorithm
Goodness of fit
Logarithm
Computer animation
Algorithm
Vertex (graph theory)
Distance
Functional (mathematics)
Routing
Error message
Computer animation
Control flow

### Timings

```  716 ms - page object
```

### Version

AV-Portal 3.8.0 (dec2fe8b0ce2e718d55d6f23ab68f0b2424a1f3f)