無向グラフ上でのクラスタリング出力結果をまとめる方法

Question

無向グラフ上でのクラスタリング結果をまとめる方法についてコードの書き方についてご教授いただきたいです。

背景
私は現在、無向グラフ上でのクラスタリングのコードを書いています。
クラスタリングは問題なくできたのですが、その出力結果が上手くまとめられないので、上手い出力方法がないかと思い質問に至りました。

やりたいこと
今の出力結果では、残った枝を愚直に出力しているため
x_01_
x_04_
x_14_
x_23_
となっていますが、これを[x_01_, x_04_ ,x_14_], [x_23_]
のように、クラスタごとにまとめたいです。
ソースコードの最後の #クラスタの出力 の部分だけ変更したいと考えております。

x_01_というのは、ノード0とノード1の間の枝を示しています。

コードの説明
x[i,j]は枝がある時1, ない時0を表す01決定変数です。

現段階での私なりの着想
i,jに

import pandas as pd
import numpy as np
import pulp

#問題定義
problem = pulp.LpProblem(name="Test", sense=pulp.LpMaximize)


#距離行列（一例）
cc = [
      [0, 3, 0, 0, 3],
      [0, 0, 1, -3, -1],
      [0, 0, 0, 3, 0],
      [0, 0, 0, 0, -1],
      [0, 0, 0, 0, 0]
      ]

w ={}
for i in range(len(cc)):
    for j in range(len(cc)):
        w[i,j] = cc[i][j]

#xを決定変数として定義
x = {}
for i in range(len(cc)) :
    for j in range(len(cc)):
        x[i,j] = pulp.LpVariable("x[{0}{1}]".format(i,j), 0, 1, pulp.LpInteger)




#目的関数の宣言
problem += pulp.lpSum(w[i,j] * (x[i,j] + y[i,j])  for i in range(len(cc)) for j in range(len(cc))), "TotalValue"

#制約式
for i in range(len(cc)):
    for j in range(len(cc)):
        #problem += x[i,j] <= y[i,j]
        for k in range(len(cc)):
            problem += x[i,j] + x[j,k] - x[i,k] <= 1
            problem += x[i,j] + x[i,k] - x[j,k] <= 1
            problem += x[i,k] + x[j,k] - x[i,j] <= 1


#最適解の結果
status = problem.solve()
print(pulp.LpStatus[status])

print(pulp.value(problem.objective), end="   ")



#クラスタの出力
for i in range(len(cc)):
    for j in range(len(cc)):
        if x[i,j].value() == 1 and i < j:
            print(x[i,j])

Optimal
16.0  

x_01_
x_04_
x_14_
x_23_

▲グラフクラスタイメージ図
出力結果とこの図のノード番号は1ずれています

Answer 1

やりたいこととは、残った枝のみからなるグラフを作ったあと、そのconnected componentsに属する枝かどうかで分類した結果を出力したいということだと思いました。
scipyを使うとこんなかんじにできるのではないでしょうか。

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


edges = [(0, 1), (0, 4), (1, 4), (2, 3)]
data = [1 for i in range(len(edges))]
row = [e[0] for e in edges]
col = [e[1] for e in edges]

graph = csr_matrix((data, (row, col)), shape=(5, 5))
#print(graph)

n_components, labels = connected_components(csgraph=graph, directed=False, return_labels=True)
#print(labels)

for n in range(n_components):
    for e in edges:
        if labels[e[0]] == n:
            print(e, end='')
    print()

出力結果：

(0, 1)(0, 4)(1, 4)
(2, 3)

Comments

[ha_horse]

ご回答ありがとうございます。
こちらの出力結果は、「改行ごとにクラスタがまとまっている」という認識でしょうか。