| import streamlit as st | |
| import graphviz | |
| import random | |
| import gurobipy as gp | |
| from gurobipy import GRB | |
| import colorsys | |
| def hsv2rgb(h, s, v): | |
| r, g, b = colorsys.hsv_to_rgb(h, s, v) | |
| return int(255 * r), int(255 * g), int(255 * b) | |
| def format_color(color): | |
| return '#%02x%02x%02x' % color | |
| def generate_colors(n): | |
| colors = [hsv2rgb(i / n, 0.5, 1.0) for i in range(n)] | |
| return [format_color(color) for color in colors] | |
| def generate_random_graph(V, density): | |
| E = [(u, v) for u in range(V - 1) for v in range(u + 1, V)] | |
| random.shuffle(E) | |
| E = E[:int(density * V * (V - 1) / 2)] | |
| return V, E | |
| def solve_matching(V, E): | |
| m = gp.Model() | |
| x = m.addVars(E, vtype=GRB.BINARY) | |
| m.setObjective(x.sum(), GRB.MAXIMIZE) | |
| m.addConstrs(x.sum(u, '*') + x.sum('*', u) <= 1 for u in range(V)) | |
| m.optimize() | |
| return [e for e in E if x[e].x > 0.5] | |
| def app_matching(V, E): | |
| M = set(solve_matching(V, E)) | |
| if len(M) == V // 2: | |
| st.success('Perfect matching found') | |
| else: | |
| st.metric('Matching size', len(M)) | |
| G = graphviz.Graph() | |
| for u, v in E: | |
| if (u, v) in M: | |
| G.edge(str(u), str(v), color='red') | |
| else: | |
| G.edge(str(u), str(v), color='gray', style='dashed') | |
| st.graphviz_chart(G) | |
| def solve_hamilton(V, E): | |
| m = gp.Model() | |
| x = m.addVars(range(V), range(V), vtype=GRB.BINARY) | |
| m.addConstrs(x.sum(u, '*') == 1 for u in range(V)) | |
| m.addConstrs(x.sum('*', i) == 1 for i in range(V)) | |
| for u in range(V): | |
| for v in range(V): | |
| if (u, v) not in E and (v, u) not in E: | |
| for i in range(V - 1): | |
| m.addConstr(x[u, i] + x[v, i + 1] <= 1) | |
| m.addConstr(x[u, V - 1] + x[v, 0] <= 1) | |
| m.optimize() | |
| if m.status != GRB.OPTIMAL: | |
| return None | |
| cycle = [] | |
| for i in range(V): | |
| for u in range(V): | |
| if x[u, i].x > 0.5: | |
| cycle.append(u) | |
| break | |
| return cycle | |
| def app_hamilton(V, E): | |
| cycle = solve_hamilton(V, E) | |
| if cycle is None: | |
| st.error('Hamilton cycle not found') | |
| else: | |
| st.success('Hamilton cycle found') | |
| G = graphviz.Graph() | |
| if cycle is not None: | |
| for u in range(V): | |
| G.node(str(cycle.index(u))) | |
| for u, v in E: | |
| if ((cycle.index(u) + 1) % len(cycle)) == cycle.index(v): | |
| G.edge(str(cycle.index(u)), str(cycle.index(v)), dir='forward') | |
| elif ((cycle.index(u) - 1) % len(cycle)) == cycle.index(v): | |
| G.edge(str(cycle.index(u)), str(cycle.index(v)), dir='back') | |
| else: | |
| G.edge(str(cycle.index(u)), str(cycle.index(v)), style='dashed', color='gray') | |
| else: | |
| for u in range(V): | |
| G.node(str(u)) | |
| for u, v in E: | |
| G.edge(str(u), str(v)) | |
| st.graphviz_chart(G) | |
| def solve_vertex_cover(V, E): | |
| m = gp.Model() | |
| x = m.addVars(range(V), vtype=GRB.BINARY) | |
| m.setObjective(x.sum(), GRB.MINIMIZE) | |
| m.addConstrs(x[u] + x[v] >= 1 for u, v in E) | |
| m.optimize() | |
| return [u for u in range(V) if x[u].x > 0.5] | |
| def app_vertex_cover(V, E): | |
| cover = solve_vertex_cover(V, E) | |
| st.metric('Vertex cover size', len(cover)) | |
| G = graphviz.Graph() | |
| for u in range(V): | |
| if u in cover: | |
| G.node(str(u), style='filled', fillcolor='lightblue') | |
| else: | |
| G.node(str(u), color='gray') | |
| for u, v in E: | |
| G.edge(str(u), str(v)) | |
| st.graphviz_chart(G) | |
| def solve_coloring(V, E): | |
| m = gp.Model() | |
| vertex_color = m.addVars(range(V), vtype=GRB.INTEGER, lb=0) | |
| or_helper = m.addVars(E, vtype=GRB.BINARY) | |
| chi = m.addVar(vtype=GRB.INTEGER) | |
| m.setObjective(chi, GRB.MINIMIZE) | |
| m.addConstrs(vertex_color[u] <= chi for u in range(V)) | |
| m.addConstrs((or_helper[u, v] == 0) >> (vertex_color[u] - vertex_color[v] >= 1) for u, v in E) | |
| m.addConstrs((or_helper[u, v] == 1) >> (vertex_color[v] - vertex_color[u] >= 1) for u, v in E) | |
| m.optimize() | |
| return [round(vertex_color[u].x) for u in range(V)] | |
| def app_coloring(V, E): | |
| coloring = solve_coloring(V, E) | |
| st.metric('Chromatic number', max(coloring) + 1) | |
| colors = generate_colors(max(coloring) + 1) | |
| G = graphviz.Graph() | |
| for u in range(V): | |
| G.node(str(u), style='filled', fillcolor=colors[coloring[u]]) | |
| for u, v in E: | |
| G.edge(str(u), str(v)) | |
| st.graphviz_chart(G) | |
| def main(): | |
| V = st.number_input('Number of vertices', min_value=1, value=10) | |
| density = st.slider('Density', min_value=0.0, max_value=1.0, value=0.5) | |
| st.button('Generate') | |
| V, E = generate_random_graph(V, density) | |
| if len(E) > 40: | |
| st.warning('Too many edges to display') | |
| return | |
| apps = [ | |
| app_matching, | |
| app_hamilton, | |
| app_vertex_cover, | |
| app_coloring, | |
| ] | |
| tabs = st.tabs([ | |
| 'Matching', | |
| 'Hamilton', | |
| 'Vertex cover', | |
| 'Coloring', | |
| ]) | |
| for t, a in zip(tabs, apps): | |
| with t: | |
| a(V, E) | |
| if __name__ == '__main__': | |
| main() | |