Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.89 KB | None | 0 0
  1. This algorithms works by calling the create_craph method. create_graph initally sets
  2.  
  3. create_graph():
  4. artists = create_artists() # creates vertices for artists
  5. for a in artists:
  6. g = undefiend
  7. if !vertex_exists(a.getGenre())
  8. g = create_genre(g)
  9. else
  10. g = get_genre_vertex(a.getGenre())
  11. # creates an directed-edge between artist and genre with f(a,g) = 0, and c(a,g)=#min_songs for a
  12. create_vertex(a)
  13. create_edge(a, g, min_songs_for(a), min_songs_for(a))
  14.  
  15. genres = get_genre_vertices()
  16. p = create_playlist() # creates a sink
  17. for g in genres:
  18. # creates an edge between the genre and the sink (i.e. playlist) with f(g,p)=L_g, and c=g,p)=undefined currently
  19. create_edge(g, p, min_songs_for(g), 0)
  20. return create_min_flow()
  21.  
  22. create_min_flow():
  23. max_songs = 200
  24. p = get_playlist()
  25. for g in get_genre_vertices():
  26. min_songs := flow(g,s) #min songs required for genre
  27. # playlist already needs to be bigger thus it is impossible to build
  28. max_songs -= min_songs
  29. if max_songs < 0:
  30. return error()
  31.  
  32. for a in g.get_artists_vertices():
  33. min_songs -= flow(a,g)
  34. flow(g,p) += flow(a,g)
  35. if min_songs < 0:
  36. return error()
  37.  
  38. # If this is true then a genre has not enough artists to reach
  39. # the minium specified for this genre
  40. if min_songs > 0:
  41. return error()
  42.  
  43. return increase_flow(max_songs)
  44.  
  45. increase_flow(remainder):
  46. p = get_playlist()
  47. for g in get_genre_vertices():
  48. for a in g.get_arists_vertices():
  49. if remainder > 0:
  50. # How many songs more can we take from this artists to increase the max flow?
  51. amt_songs := min(remainder, capacity(a,g)-flow(a,g))
  52. # Increase capacity from artists -> genre -> playlist
  53. capacity(a,g) += amt_songs
  54. capacity(g,p) += amt_songs
  55. remainder -= amt_songs # Reduce available amount of songs
  56. else:
  57. break
  58. if remainder > 50:
  59. return error()
  60. else:
  61. return success()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement