src/app.py

import streamlit as st
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import math
from copy import deepcopy
from itertools import permutations, product
from collections import defaultdict


# Initialize session state
if "voters" not in st.session_state:
    st.session_state.voters = []

if "scoring_history" not in st.session_state:
    st.session_state.scoring_history = []  # List of tuples: (label, vector, manipulability %)

st.title("🎯 Strategy-Proof Ranked Voting System")

# 1. Alternatives and scoring vector
num_alts = st.number_input("Number of alternatives:", min_value=2, value=3)
alternatives = [f"M{i+1}" for i in range(num_alts)]

scoring_input = st.text_input("Enter scoring vector (comma-separated):", value="2,1,0")
try:
    scoring_vector = list(map(int, scoring_input.strip().split(',')))
    assert len(scoring_vector) == num_alts
except:
    st.error("Scoring vector must contain exactly one value per alternative.")
    st.stop()

# 2. Add voter
st.subheader("🗳️ Add Voter")
with st.form("add_voter_form"):
    voter_name = st.text_input("Voter Name:", f"Voter{len(st.session_state.voters)+1}")
    ranking = st.multiselect("Rank alternatives (top to bottom):", alternatives, default=alternatives)
    submit = st.form_submit_button("Add Voter")
    if submit:
        if len(ranking) != num_alts:
            st.warning("Rank all alternatives uniquely.")
        else:
            preferences = {ranking[i]: scoring_vector[i] for i in range(num_alts)}
            st.session_state.voters.append({
                "name": voter_name,
                "ranking": ranking,
                "preferences": preferences
            })
            st.success(f"{voter_name} added.")

# 3. Show all voter preferences
st.subheader("👥 Voter Preferences")
if st.session_state.voters:
    df_votes = pd.DataFrame([{**{"Voter": v["name"]}, **v["preferences"]} for v in st.session_state.voters])
    st.dataframe(df_votes)

# --- Function to detect manipulation ---
import math

def detect_manipulation(voters, alternatives, scoring_vector):
    total_profiles = math.factorial(len(alternatives)) ** len(voters)
    manipulable_cases = 0
    manipulable_info = []

    def get_rank(score_dict):
        sorted_alts = sorted(score_dict.items(), key=lambda x: -x[1])
        return {alt: rank + 1 for rank, (alt, _) in enumerate(sorted_alts)}

    # Original overall ranking
    original_scores = {alt: 0 for alt in alternatives}
    for v in voters:
        for i, alt in enumerate(v["ranking"]):
            original_scores[alt] += scoring_vector[i]
    original_ranks = get_rank(original_scores)
    original_winner = max(original_scores, key=original_scores.get)

    for voter in voters:
        original_ranking = voter["ranking"]

        # Skip if voter's top choice is already the winner
        if original_ranking[0] == original_winner:
            continue

        for alt in alternatives:
            if alt == original_ranking[0]:
                continue  # skip if same as current top

            new_ranking = original_ranking.copy()
            if alt in new_ranking:
                new_ranking.remove(alt)
            new_ranking.insert(0, alt)

            simulated_scores = {a: 0 for a in alternatives}
            for v in voters:
                rank_list = new_ranking if v == voter else v["ranking"]
                for i, a in enumerate(rank_list):
                    simulated_scores[a] += scoring_vector[i]

            simulated_ranks = get_rank(simulated_scores)
            new_winner = max(simulated_scores, key=simulated_scores.get)

            # Manipulation is beneficial ONLY IF new winner is ranked *higher* than original winner
            if original_ranking.index(new_winner) < original_ranking.index(original_winner):
                rank_improvements = []
                for a in alternatives:
                    old_rank = original_ranks[a]
                    new_rank = simulated_ranks[a]
                    if new_rank < old_rank:
                        rank_improvements.append(f"{a}: {old_rank} → {new_rank}")

                manipulable_cases += 1
                manipulable_info.append({
                    "voter": voter["name"],
                    "original_ranking": original_ranking,
                    "manipulated_ranking": new_ranking,
                    "original_winner": original_winner,
                    "new_winner": new_winner,
                    "rank_improvements": rank_improvements,
                    "simulated_ranks": simulated_ranks  # ✅ Add this for your DataFrame logic
                })
                break

    return manipulable_cases, len(voters), manipulable_info

def get_winners(scores):
    max_score = max(scores.values())
    return [alt for alt, score in scores.items() if score == max_score]

# --- Function to count manipulable profile ---
from itertools import permutations, product
from collections import defaultdict

def count_manipulable_profiles(m, n, scoring_vector):
    alternatives = [f"M{i+1}" for i in range(m)]
    all_rankings = list(permutations(alternatives))
    total_profiles = len(all_rankings) ** n
    manipulable_count = 0

    def get_rank(scores):
        # Returns a ranking dictionary based on scores (highest score first)
        sorted_items = sorted(scores.items(), key=lambda x: -x[1])
        return {alt: i + 1 for i, (alt, _) in enumerate(sorted_items)}

    # Iterate over all possible profiles
    for profile in product(all_rankings, repeat=n):
        # Calculate the original scores for this profile
        original_scores = defaultdict(int)
        for ranking in profile:
            for i, alt in enumerate(ranking):
                original_scores[alt] += scoring_vector[i]

        # Identify the original winner (the alternative with the highest score)
        original_winner = max(original_scores, key=original_scores.get)

        # Calculate the original rank order
        original_ranks = get_rank(original_scores)

        # Check if the profile can be manipulated by at least one voter
        profile_manipulated = False
        
        for voter_idx, ranking in enumerate(profile):
            # If the original winner is already the first choice for this voter, no manipulation is possible
            if ranking[0] == original_winner:
                continue
            
            # Find the alternatives this voter prefers over the original winner
            preferred_alts = []
            for alt in ranking:
                if alt == original_winner:
                    break
                preferred_alts.append(alt)

            # Try manipulating the vote by promoting each preferred alternative
            for alt in preferred_alts:
                # Create a manipulated vote where 'alt' is ranked first
                manipulated = list(ranking)
                manipulated.remove(alt)
                manipulated.insert(0, alt)

                # Recalculate the scores with the manipulated vote
                new_scores = original_scores.copy()
                # Subtract the original vote's scores
                for pos, a in enumerate(ranking):
                    new_scores[a] -= scoring_vector[pos]
                # Add the manipulated vote's scores
                for pos, a in enumerate(manipulated):
                    new_scores[a] += scoring_vector[pos]

                # Determine the new winner after manipulation
                new_winner = max(new_scores, key=new_scores.get)

                # Check if the new winner is one of the preferred alternatives and is better than the original winner
                if new_winner in preferred_alts and new_scores[new_winner] > new_scores[original_winner]:
                    manipulable_count += 1
                    profile_manipulated = True
                    break

            if profile_manipulated:
                break
        
        # Count the profile if at least one voter can manipulate it
        if profile_manipulated:
            manipulable_count += 1

    # Return manipulable count, total profiles, and manipulability percentage
    manipulability = (manipulable_count / total_profiles) * 100
    return manipulable_count, total_profiles, manipulability



# 4. Compute results
if st.button("📊 Compute Result") and st.session_state.voters:
    scores = {alt: 0 for alt in alternatives}
    for v in st.session_state.voters:
        for alt, pts in v["preferences"].items():
            scores[alt] += pts

    st.subheader("📈 Result Table")
    score_df = pd.DataFrame(scores.items(), columns=["Alternative", "Score"]).sort_values("Score", ascending=False)
    st.dataframe(score_df)

    # Bar chart
    st.subheader("📊 Score Distribution")
    fig, ax = plt.subplots()
    sns.barplot(data=score_df, x="Alternative", y="Score", palette="Blues_d", ax=ax)
    ax.set_title("Total Points per Alternative")
    st.pyplot(fig)

    # Heatmap of votes
    st.subheader("🔥 Voter Preferences Heatmap")
    heatmap_df = pd.DataFrame(
        [{alt: v["preferences"][alt] for alt in alternatives} for v in st.session_state.voters],
        index=[v["name"] for v in st.session_state.voters]
    )
    fig2, ax2 = plt.subplots(figsize=(8, 4))
    sns.heatmap(heatmap_df, annot=True, cmap="YlGnBu", ax=ax2)
    st.pyplot(fig2)

    # Tie-breaking logic
    top_score = score_df["Score"].max()
    top_alts = score_df[score_df["Score"] == top_score]["Alternative"].tolist()

    if len(top_alts) > 1:
        st.warning(f"Tie detected between: {', '.join(top_alts)}")

        # Top-rank frequency
        first_rank = {alt: 0 for alt in top_alts}
        for v in st.session_state.voters:
            top = v["ranking"][0]
            if top in first_rank:
                first_rank[top] += 1

        max_first = max(first_rank.values())
        tied_top = [a for a in top_alts if first_rank[a] == max_first]

        if len(tied_top) == 1:
            st.success(f"🏅 Winner by top-rank frequency: {tied_top[0]}")
        else:
            final = sorted(tied_top)[0]
            st.success(f"🏅 Still tied after top-rank votes. Tie-breaker by alphabetical order: {final}")
    else:
        st.success(f"🏅 Winner: {top_alts[0]}")


    # 5. Manipulation Detection
    st.subheader("🕵️ Manipulation Detection")

    m_cases, t_cases, m_profiles = detect_manipulation(
        st.session_state.voters, alternatives, scoring_vector
    )

    st.markdown(f"📊 **Voters who can potentially improve their outcome:** `{m_cases} / {t_cases}`")

    if m_profiles:
        for item in m_profiles:
            # Corrected rank improvements with accurate old and new positions
            rank_changes = []
            original_ranking = item['original_ranking']
            manipulated_ranking = item['manipulated_ranking']

            for imp in item['rank_improvements']:
                alt_name, _ = imp.split(':')  # Only keep the alternative name, ignore the rank change part
                alt_name = alt_name.strip()

                # Get original and new rank positions (1-based)
                old = original_ranking.index(alt_name) + 1
                new = manipulated_ranking.index(alt_name) + 1
                benefit = old - new

                if benefit > 0:
                    rank_changes.append(f"✅ {alt_name}: Rank {old} → {new} (↑ {benefit})")
                elif benefit < 0:
                    rank_changes.append(f"⚠️ {alt_name}: Rank {old} → {new} (↓ {abs(benefit)})")
                else:
                    rank_changes.append(f"➖ {alt_name}: Rank {old} → {new} (no change)")


            # Simulated overall rank table
            sim_ranks_df = pd.DataFrame.from_dict(item["simulated_ranks"], orient="index", columns=["Rank"])
            sim_ranks_df.index.name = "Alternative"
            sim_ranks_df = sim_ranks_df.sort_values("Rank")

            # Display voter manipulation info
            st.markdown(f"""
            <div style='margin-bottom:15px; border-left: 3px solid #444; padding-left: 10px;'>
            🔍 <b>{item['voter']}</b> can manipulate:
            <ul>
                <li><b>Original Ranking:</b> {', '.join(original_ranking)}</li>
                <li><b>Manipulated Ranking:</b> {', '.join(manipulated_ranking)}</li>
                <li><b>Original Winner:</b> {item['original_winner']}</li>
                <li><b>New Winner after manipulation:</b> {item['new_winner']}</li>
                <li><b>Rank Improvements:</b>
                    <ul>
                        {''.join(f"<li>{rc}</li>" for rc in rank_changes)}
                    </ul>
                </li>
            </ul>
            </div>
            """, unsafe_allow_html=True)

            st.markdown("**📌 Simulated Ranks after Manipulation:**")
            st.dataframe(sim_ranks_df)
    else:
        st.success("✅ No manipulable profiles detected.")



    # 6. Global Manipulability (All Possible Profiles)
    st.subheader("📚 Global Profile Manipulability")
    m = len(alternatives)
    n = len(st.session_state.voters)

    with st.spinner("Computing over all possible profiles..."):
        manipulable, total,manipulability_perc = count_manipulable_profiles(m, n, scoring_vector)
        st.success(f"Out of {total} total profiles, at least one voter can manipulate in {manipulable} profiles.")
        st.metric("Manipulable Profiles", f"{manipulable} / {total}", delta=f"{round((manipulable/total)*100, 2)}%")

    current_label = f"Custom {scoring_vector}"
    # After detect_manipulation()
    #m_cases, t_cases, m_profiles = detect_manipulation(st.session_state.voters, alternatives, scoring_vector)

    # Accurate manipulability % for the current scoring vector
    global_m, global_t, manipulability = count_manipulable_profiles(len(alternatives), len(st.session_state.voters), scoring_vector)
    #manipulability = (global_m / global_t) * 100

    # Avoid duplicates
    if not any(vector == scoring_vector for _, vector, _, _, _ in st.session_state.scoring_history):
        st.session_state.scoring_history.append((f"Custom {scoring_vector}", scoring_vector.copy(), manipulability, len(alternatives), len(st.session_state.voters)))


    # 6. Accumulated Scoring Vector Comparison
    if st.session_state.scoring_history:
        df_hist = pd.DataFrame(
        [(label, m, n, percent) for label, _, percent, m, n in st.session_state.scoring_history],
        columns=["Scoring Vector", "Alternatives", "Voters", "Manipulable %"]
        )

        st.subheader("📊 Manipulability of All Used Scoring Vectors")
        fig_hist, ax_hist = plt.subplots(figsize=(10, 6))
        sns.barplot(data=df_hist, x="Manipulable %", y="Scoring Vector", palette="Spectral", ax=ax_hist)
        ax_hist.set_xlim(0, 100)
        ax_hist.set_xlabel("Percentage of Manipulable Profiles")
        ax_hist.set_title("Manipulability by Scoring Vector")

        # Annotate each bar with m, n and manipulability %
        for i, row in df_hist.iterrows():
            label = f"m={row['Alternatives']}, n={row['Voters']} | {row['Manipulable %']:.2f}%"
            ax_hist.text(row['Manipulable %'] + 1, i, label, va='center', fontsize=9, color='black')

        st.pyplot(fig_hist)


# Reset
if st.button("🔄 Reset Voters"):
    st.session_state.voters = []
    st.session_state.scoring_history = []
    st.rerun()