Graph Representation Comparison in Computer Science
Explore the different graph representations in computer science - Actor-Actor, Movie-Movie, and Actor-Movie. Discover which graph has the most vertices and edges, and which is easiest to implement. Dive into the world of data representation and graph theory in this insightful analysis.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CompSci 201 Bacon Jeff Forbes April 20, 2018 5/2/2025 CompSci 201, Spring 2018, Graphs 1
Y is for Y2K Bits are cheap? Yahoo! The importance of browsing YAML, YACC Yet another Yao s minimax principle Randomized algorithms & their limits 5/2/2025 CompSci 201, Spring 2018, Graphs 2
Data Representation IMDB via the Sedgewick and Wayne book site Movie title, followed by a list of actors and actresses that appeared in that movie, delimited by / /. File Description input8.txt sample data cast-06.txt movies released in 2006 cast-mpaa.txt movies rated by MPAA cast-rated.txt popular movies cast-all.txt over 250,000 movies Movie 3/E/F/G Movie 4/F/G/H Movie 5/H/I/J/K Movie 6/J/L/M/N Movie 7/A/B/C/D Who has the highest bacon degree? Movies Actors 8 8,780 21,861 280,624 4,527 122,406 285,462 933,864 15 84,236 Movie 0/Bacon, Kevin/A Movie 1/A/B/C Movie 2/D/E/A/B 5/2/2025 CompSci 201, Spring 2018, Graphs 3
Actor-Actor Representation Movie 0/Bacon, Kevin/A Movie 1/A/B/C Movie 2/D/E/A/B Movie 3/E/F/G Movie 4/F/G/H Movie 5/H/I/J/K Movie 6/J/L/M/N Movie 7/A/B/C/D Vertices: Vertices: Actors or actresses Edges: Edges: Two actors are adjacent if and only if they appeared in the same movie publicvoid createActorGraph() { for (Actor a : myActors.values()) for (Actor b : a.coStars().keySet()) myG.addEdge(a.getName(), b.getName()); } CompSci 201, Spring 2018, Graphs 4
Movie-Movie Representation Vertices: Vertices: Movies Edges: Edges: Two movies are adjacent iff they share a cast member publicvoid createMovieGraph() { for (Movie m : myMovies.values()) for (Actor a : m.getActors()) for (Movie otherMoov : a.getMovies()) if (otherMoov != m) myG.addEdge(m.name, otherMoov.name); } CompSci 201, Spring 2018, Graphs 5
Actor-Movie Representation Vertices: Vertices: Actors, actresses, and movies Edges: Edges: An Actor is connected to a Movie iff he or she appeared in that movie publicvoid createActorMovieGraph() { for (Movie m : myMovies.values()) for (Actor a : m.getActors()) myG.addEdge(m.name, a.name); } CompSci 201, Spring 2018, Graphs 6
Bacon Questions Compare and contrast representations for the problem: 1. Actor-Actor 2. Movie-Movie 3. Actor-Movie Which graph will be have the most vertices or edges? Which one will be easiest to implement? 7 CompSci 201, Spring 2018, Graphs
Center of the Hollywood Universe? 2,331,812 people can be connected to Bacon Is he the center of the Hollywood Universe? Who are other good centers? What makes them good centers? Centrality Closeness: the inverse average distance of a node to all other nodes Degree: the degree of a node Betweenness: a measure of how much a vertex is between other nodes Name someone who is 4 degrees or more away from Kevin Bacon CompSci 201, Spring 2018, Graphs 8
More Graph problems Word Ladders How many ladders from cart to dire as shown? Circuits What is the the longest path in a directed acyclic graph? l l care dare dire cart tart dart dirt CompSci 201, Spring 2018, Graphs 9
Sorting: In 2 Slides Why do people study sorting? Because we have to Because sorting is beautiful Example of algorithm analysis in a simple, useful setting There are n sorting algorithms, how many should we study? O(n), O(log n), Why do we study more than one algorithm? Some are good, some are bad, some are very, very sad Paradigms of trade-offs and algorithmic design Which sorting algorithm is best? Which sort should you call from code you write? CompSci 201, Spring 2018, Graphs 10
Sorting out sorts Simple, O(n2) sorts --- for sorting n elements Selection sort --- n2 comparisons, nswaps, easy to code Insertion sort --- n2 comparisons, n2 moves, stable, fast Bubble sort --- n2 everything, slow, slower, and ugly Divide and conquer faster sorts: O(n log n) for n elements Quick sort: fast in practice, O(n2) worst case Merge sort: good worst case, great for linked lists, uses extra storage for vectors/arrays Other sorts: Heap sort, basically priority queue sorting, Big-Oh? Radix sort: doesnt compare keys, uses digits/characters O(dn+kd) Shell sort: quasi-insertion, fast in practice, non- recursive O(n1.5) https://www.youtube.com/watch?v=kPRA0W1kECg CompSci 201, Spring 2018, Graphs 11
