algorithm - グラフ変換 - 頂点からエッジへ、エッジから頂点へ

Question

アルゴリズムはありますか、またはエッジを頂点に変換し、頂点をエッジに変換できるグラフの変換の名前はありますか? それから新しいグラフを取得できるようにするためですか、それともこの問題に似たものですか? 意味が通じるかどうかわかりませんが、このような問題について何かヒントをいただければ幸いです。

score 3 · Accepted Answer

LineGraphはWolfram言語の組み込み関数です:

これはそれが何をするかです：

LineGraph[g] の各頂点は、g のエッジに対応します。
無向グラフ g の場合、対応する辺が共通の頂点を共有する場合、LineGraph[g] の 2 つの頂点は隣接しています。
有向グラフ g の場合、対応するエッジが接続されている場合、LineGraph[g] の 2 つの頂点は隣接しています。つまり、一方のエッジのターゲットが他方のエッジのソースです。
LineGraph は、無向グラフ、有向グラフ、およびマルチグラフで動作します。

score 2 · Accepted Answer

パターンベースのグラフ変換について考えたことはありますか? あなたがするように

グラフ変換の文献では、これらの 2 つのステップはグラフ変換規則の左側と右側と呼ばれます。

その分野で利用できる科学文献はたくさんあります。

Soley Studioなど、グラフ変換に特化した開発ソリューションもあります。

それが役立つことを願っています。

score -1 · Accepted Answer

次の Python ライブラリを使用して、エッジを頂点に簡単に変換できると思います: http://networkx.lanl.gov/

エッジリストとノードリストを取得し、2 つを交換して新しいグラフを作成できます。Python の (基本的な) 知識が必要です。

4 に答える 4