app.py

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()