import pulp

# ①問題の定義
problem = pulp.LpProblem("Sudoku Problem", pulp.LpMinimize)

# ②変数の定義
choices = pulp.LpVariable.dicts("Choice", (range(1, 10), range(1, 10), range(1, 10)), cat='Binary')

# ③制約条件の定義
# 各マスは1つの数字に限定される
for row in range(1, 10):
    for col in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for num in range(1, 10)]) == 1

# ④各行には1から9までの数字が1回ずつ現れる
for row in range(1, 10):
    for num in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for col in range(1, 10)]) == 1

# ⑤各列には1から9までの数字が1回ずつ現れる
for col in range(1, 10):
    for num in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for row in range(1, 10)]) == 1

# ⑥各3x3ブロックには1から9までの数字が1回ずつ現れる
for row in range(1, 10, 3):
    for col in range(1, 10, 3):
        for num in range(1, 10):
            problem += pulp.lpSum([choices[i][j][num] for i in range(row, row + 3) for j in range(col, col + 3)]) == 1

# ⑦初期状態を設定
# ナンプレ問題の初期状態には、空きマスを0として表現します。
initial_state = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

for row in range(9):
    for col in range(9):
        if initial_state[row][col] != 0:
            problem += choices[row+1][col+1][initial_state[row][col]] == 1

# ⑧解を求める
problem.solve()

# ⑨解の表示
solution = [[0]*9 for _ in range(9)]
for row in range(1, 10):
    for col in range(1, 10):
        for num in range(1, 10):
            if choices[row][col][num].value() == 1:
                solution[row-1][col-1] = num

for row in solution:
    print(row)

import networkx as nx
import matplotlib.pyplot as plt

# 5つの都市の座標を設定
positions = {1: (0, 0), 2: (1, 1), 3: (2, 0), 4: (3, 1), 5: (4, 0)}

# 距離を計算する関数を定義
def distance(u, v):
    x1, y1 = positions[u]
    x2, y2 = positions[v]
    return ((x1-x2)**2 + (y1-y2)**2)**0.5

# グラフを作成
G = nx.Graph()
G.add_nodes_from(positions.keys())
for u in positions:
    for v in positions:
        if u < v:
            G.add_edge(u, v, weight=distance(u, v))

# 巡回セールスマン問題を解く
tsp = list(nx.algorithms.approximation.traveling_salesman_problem(G))

# 解を表示
print("最短距離の順序：", tsp)
print("最短距離：", sum(distance(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])))

# グラフを可視化
pos = positions
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edges(G, pos=pos, edgelist=[(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])], edge_color='r')
plt.show()

import networkx as nx

# 無向グラフの定義
G = nx.Graph()

# 頂点の追加
G.add_nodes_from([1, 2, 3, 4, 5])

# 辺の追加
G.add_edge(1, 2, weight=5)
G.add_edge(1, 3, weight=2)
G.add_edge(1, 4, weight=6)
G.add_edge(2, 3, weight=3)
G.add_edge(2, 4, weight=2)
G.add_edge(3, 4, weight=1)
G.add_edge(3, 5, weight=4)
G.add_edge(4, 5, weight=6)

# 全点対最短経路を求める
all_shortest_paths = dict(nx.shortest_path(G))

# 結果を表示する
for source in all_shortest_paths:
    for target in all_shortest_paths[source]:
        if source != target:
            print(f"{source} から {target} までの最短経路: {all_shortest_paths[source][target]}")

import networkx as nx

# グラフを定義する
G = nx.Graph()
G.add_nodes_from(["F1", "F2", "F3", "F4", "F5"], bipartite=0)
G.add_nodes_from(["M1", "M2", "M3", "M4", "M5"], bipartite=1)
G.add_weighted_edges_from([
    ("F1", "M1", 70), ("F1", "M2", 90), ("F1", "M3", 80), ("F1", "M4", 80), ("F1", "M5", 70),
    ("F2", "M1", 60), ("F2", "M2", 10), ("F2", "M3", 80), ("F2", "M4", 70), ("F2", "M5", 60),
    ("F3", "M1", 70), ("F3", "M2", 70), ("F3", "M3", 100), ("F3", "M4", 70), ("F3", "M5", 60),
    ("F4", "M1", 80), ("F4", "M2", 80), ("F4", "M3", 80), ("F4", "M4", 50), ("F4", "M5", 60),
    ("F5", "M1", 90), ("F5", "M2", 90), ("F5", "M3", 90), ("F5", "M4", 90), ("F5", "M5", 30)
])

# 最大重みマッチングを求める
max_matching = nx.max_weight_matching(G)
print(max_matching)

import networkx as nx

def find_most_popular_friend_of_friends(G, user):
    """
    指定されたユーザーの友達の友達の中で最も人気がある人を見つける関数

    Parameters
    ----------
    G : NetworkXのグラフオブジェクト
        SNSグラフ
    user : ノード
        検索対象のユーザー

    Returns
    -------
    ノード
        最も人気があるユーザー
    """
    # userの友達を取得
    friends = set(nx.neighbors(G, user))

    # userの友達の友達を取得
    friends_of_friends = set()
    for friend in friends:
        friends_of_friends.update(nx.neighbors(G, friend))

    # userとその友達の友達を除く
    friends_of_friends.discard(user)
    friends_of_friends.difference_update(friends)

    # 各ノードの次数を計算
    degrees = G.degree(friends_of_friends)

    # 次数の降順にソート
    sorted_degrees = sorted(degrees, key=lambda x: x[1], reverse=True)

    # 最も人気のあるユーザーを返す
    return sorted_degrees[0][0]

import networkx as nx

# SNSグラフを作成
G = nx.Graph()
G.add_edges_from([
    ('Alice', 'Bob'),
    ('Alice', 'Charlie'),
    ('Bob', 'David'),
    ('Bob', 'Eve'),
    ('Charlie', 'David'),
    ('Charlie', 'Frank'),
    ('David', 'Eve'),
    ('Eve', 'Frank'),
    ('Eve', 'Grace'),
    ('Frank', 'Grace')
])

# 'Alice'の友達の友達で最も人気がある人を見つける
most_popular_friend_of_friends = find_most_popular_friend_of_friends(G, 'Alice')

print(f"Most popular friend of friends of Alice: {most_popular_friend_of_friends}")

import networkx as nx

# グラフの作成
G = nx.DiGraph()
G.add_nodes_from([1, 2, 3, 4])
G.add_edges_from([(1, 2), (2, 3), (3, 1), (3, 4)])

# 転置グラフの作成
GT = G.reverse(copy=True)

# DFSを行い、スタックに追加
stack = []
visited = set()
for v in G.nodes:
    if v not in visited:
        visited.add(v)
        stack.append(v)
        while stack:
            node = stack[-1]
            neighbors = list(G.neighbors(node))
            unvisited = [n for n in neighbors if n not in visited]
            if unvisited:
                n = unvisited[0]
                visited.add(n)
                stack.append(n)
            else:
                stack.pop()

# スタックから頂点を逆順にして、転置グラフに対してDFSを行う
visited = set()
while stack:
    node = stack.pop()
    if node not in visited:
        visited.add(node)
        t_neighbors = list(GT.neighbors(node))
        for n in t_neighbors:
            if n not in visited:
                stack.append(n)

if len(visited) == len(G.nodes):
    print("グラフは強連結グラフです")
else:
    print("グラフは強連結グラフではありません")

import networkx as nx

# グラフを作成
G = nx.DiGraph()

G.add_nodes_from(['S', 'A', 'B', 'C', 'D', 'T'])

G.add_edges_from([('S', 'A', {'capacity': 10}),
                  ('S', 'C', {'capacity': 5}),
                  ('A', 'B', {'capacity': 9}),
                  ('A', 'D', {'capacity': 4}),
                  ('B', 'T', {'capacity': 8}),
                  ('C', 'D', {'capacity': 3}),
                  ('C', 'T', {'capacity': 7}),
                  ('D', 'B', {'capacity': 6}),
                  ('D', 'T', {'capacity': 9})])

# 最大流を求める
max_flow_value, flow_dict = nx.maximum_flow(G, 'S', 'T', capacity='capacity')

# 結果を表示する
print('Maximum Flow Value:', max_flow_value)
print('Flow Dictionary:', flow_dict)

import networkx as nx

# グラフを作成する
G = nx.DiGraph()
nodes = "ABCDE"
for i in range(len(nodes)):
    G.add_node(nodes[i])
    if i < len(nodes) - 1:
        G.add_edge(nodes[i], nodes[i+1])
G.add_edge(nodes[-1], nodes[0])

# ループを検出する
loops = list(nx.simple_cycles(G))
if len(loops) > 0:
    print("ループを検出しました:")
    print(loops)
else:
    print("ループは検出されませんでした。")

import networkx as nx

# グラフを作成する
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5), (5, 3)])

# 各頂点の次数を計算する
degrees = dict(G.degree())
print(degrees)

import networkx as nx
import matplotlib.pyplot as plt
from networkx.algorithms import community

# グラフの読み込み
G = nx.karate_club_graph()

# グラフの可視化
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
plt.show()

# クラスタリング
communities = community.greedy_modularity_communities(G)

# クラスタリング結果の表示
for i, c in enumerate(communities):
    print("Cluster ", i+1, ": ", c)

# クラスタリング結果をグラフに反映
color_map = []
for node in G:
    for i, c in enumerate(communities):
        if node in c:
            color_map.append(i)
nx.draw(G, pos, node_color=color_map, with_labels=True)
plt.show()