Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- This algorithms works by calling the create_craph method. create_graph initally sets
- create_graph():
- artists = create_artists() # creates vertices for artists
- for a in artists:
- g = undefiend
- if !vertex_exists(a.getGenre())
- g = create_genre(g)
- else
- g = get_genre_vertex(a.getGenre())
- # creates an directed-edge between artist and genre with f(a,g) = 0, and c(a,g)=#min_songs for a
- create_vertex(a)
- create_edge(a, g, min_songs_for(a), min_songs_for(a))
- genres = get_genre_vertices()
- p = create_playlist() # creates a sink
- for g in genres:
- # creates an edge between the genre and the sink (i.e. playlist) with f(g,p)=L_g, and c=g,p)=undefined currently
- create_edge(g, p, min_songs_for(g), 0)
- return create_min_flow()
- create_min_flow():
- max_songs = 200
- p = get_playlist()
- for g in get_genre_vertices():
- min_songs := flow(g,s) #min songs required for genre
- # playlist already needs to be bigger thus it is impossible to build
- max_songs -= min_songs
- if max_songs < 0:
- return error()
- for a in g.get_artists_vertices():
- min_songs -= flow(a,g)
- flow(g,p) += flow(a,g)
- if min_songs < 0:
- return error()
- # If this is true then a genre has not enough artists to reach
- # the minium specified for this genre
- if min_songs > 0:
- return error()
- return increase_flow(max_songs)
- increase_flow(remainder):
- p = get_playlist()
- for g in get_genre_vertices():
- for a in g.get_arists_vertices():
- if remainder > 0:
- # How many songs more can we take from this artists to increase the max flow?
- amt_songs := min(remainder, capacity(a,g)-flow(a,g))
- # Increase capacity from artists -> genre -> playlist
- capacity(a,g) += amt_songs
- capacity(g,p) += amt_songs
- remainder -= amt_songs # Reduce available amount of songs
- else:
- break
- if remainder > 50:
- return error()
- else:
- return success()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement