Advertisement
Guest User

Untitled

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