algorithm - 頂点間の距離が辺の重みに対応するグラフを描く

Question

重み付きグラフを与え、頂点間のエッジの重みが頂点間の距離を指すときに、グラフ内の頂点の座標を与えるアルゴリズムはありますか?

何かのようなもの：

public _ArrayOfCoordinatesForVertices_ **super_hyper_algorithm**(weighted_graph){  
     return _foo_;  
}

Answer 1

これは一般的に不可能です。3 つのノード n1、n2、および n3 を持つグラフを想像してください。

ここで、次の距離を考慮してください。

n1-n2: 4
n1-n3: 1
n2-n3: 1

(これは三角形の不等式に違反します)。

Answer 2

あなたが参照しているのは多次元尺度構成法（MDS）と呼ばれ、それを検索する方法がわかったので、たくさんの実装を見つける必要があります。

他の人が言ったように、ある程度、制約（ポイント間の距離）に違反せずにパーフェクトグラフを描くことは不可能です。MDSアルゴリズムは、このような違反を最小限に抑えることを特に目的としています。

Answer 3

グラフがユークリッド空間で描かれている場合、それはできません。この回答で指摘されているように、三角不等式に違反する可能性があるためです。

通常、エッジの重みは、さまざまな色を使用する（つまり、重みをカラーマップにマッピングする）か、エッジのさまざまな厚さを使用する（つまり、重みを厚さスケールにマッピングする）ことで視覚的に表すことができます。

Answer 4

OK、私はPython用のライブラリを見つけました. ドットでは、重量が重いほど、端が短く、まっすぐで、垂直になります。