問題タブ [bipartite]

したがって、C＃で無向ネットワーク（これは正しい用語だと思います）を実装するための何らかの方法が必要です

次のデータがあるとしましょう。

これをサポートできるものをどのように実装しますか？

これを行う1つの方法は、FooとBarを含むクラスを作成することです。私の例では、これらを6つ、可能な組み合わせごとに作成しますが、これによりデータが2倍になります。

このデータを使用して、Foo1で、バーのポイントもいくつあるか、Fooのバーのポイントもいくつあるかなどに基づいて計算を実行できる必要があります。

私は答えを探していません。これを実装する方法について、おそらくいくつかのリンクでさえ、いくつかの方向性を示したいと思います。

たとえば、グラフG =（V、E）があるとします。

V = {A、B、C、D}
E = {（A、B）、（A、D）、（C、D）}

このグラフは2部グラフであるため、2つの互いに素なセット{A、C}と{B、D}に分割できます。私の最初の推測は、グラフを歩き、各頂点に交互の色を割り当てることができるということです。これは事実ですか、それともこれよりも複雑/単純ですか？このための既知のアルゴリズムはありますか？

最適な二部マッチングを計算する Python のモジュールを知っている人はいますか? 私は次の2つを試しました：

1. ムンクレス
2. ハンガリー語

ただし、私の場合、不完全なグラフ (つまり、2 つのノード間にエッジがない可能性がある) を処理する必要があるため、ノードにエッジがない場合は一致しない可能性があります。上記の 2 つのパッケージは、これに対処できないようです。

何かアドバイス？

グラフが2部グラフであるかどうかをチェックするプログラムを作成する必要があります。

グラフ彩色と2部グラフに関するウィキペディアの記事を読みました。これらの2つの記事は、BFS検索のような二者択一をテストする方法を提案していますが、これらの方法を実装するプログラムを作成することはできません。

アップデート

これまでのいくつかの回答では、隣接リストの使用が提案されています。隣接リストはJavaでどのように見えるでしょうか? ...ポインタはありません:)

---

ファイルからの情報を 2 つのグループに分類するために、Java で二部グラフを実装しようとしています。私はこの例を見つけました、そしてそれは実際に仕事をします:

http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html

しかし、私は自分のバージョンを実装したいと思っています...私の以前の投稿を見ると、なぜ私が自分でこれをやりたいのか理解できるでしょう。

そのため、頂点の数を簡単に取得できるファイルを読み取る必要がありますが、エッジの数はそれほど簡単ではありません。例の行は"PersonA PersonB"で、これは "PersonA say PersonB "と読むことができます。だから、これらの行を読んで...

... このグループ化を生成します。

この二部グラフを実装するにはどうすればよいですか? このタスクに適したリソースは何ですか? BipartiteGraph クラスを作成するときに、どのようなこと (アルゴリズム) を考慮し、検討する必要がありますか?おそらくトラバース/ソートアルゴリズム?

長方形のグリッド、つまり N ノードと 2N エッジの形式のグラフがあり、隣接するすべてのノードが接続されています。これは、2 色対応であることを意味するため、2 部構成のマッチングを行うことができます。

各 (無向) エッジには、-2、-1、0、1、または 2 のいずれかの重みが割り当てられています。他の値は使用できません。

このグラフで、マッチングの重みの合計を最大化するマッチングを見つけるにはどうすればよいでしょうか? 特定の言語を気にしないでください。

理想的には、二次時間で実行されるアルゴリズムを探しています - 最悪でも O(n^2 log n) かもしれません。

---

解決策を提案する前に、重み 2 のエッジ、次に重み 1 のエッジを使用して最大一致を試みました (重み 2 のエッジを超えることはありません)。私はこの実装で 98% のスコアを獲得しました (問題は情報オリンピックからのものです)。

私は一種の1レベルのツリー構造を次のように持っています:

ここで、p は親ノード、c は子ノード、b は仮想分岐です。

1 つの親のみが1つの子ノードにのみ分岐でき、2 つの分岐は親および/または子を共有できないという制約の下で、分岐のすべての組み合わせを見つけたいと考えています。

例combo: が組み合わせのセットである場合:

それがすべてだと思います。=)

この構造の任意のツリー、つまり p:s、c:s、および b:s の数は任意です。

編集：

これはツリーではなく、二部 有向非巡回グラフです

グラフ表現としてnetworkxを使用して、Pythonでホップクロフトカープアルゴリズムを実装しようとしています。

現在、私はこれまでです：

アルゴリズムはhttp://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithmから取得されますが 、機能しません。次のテストコードを使用します

残念ながら、これは機能せず、無限ループに陥ります:(。誰かがエラーを見つけることができますか、私はアイデアがありません、そして私はまだアルゴリズムを完全に理解していないことを認めなければなりません、それでそれはほとんど疑似の実装ですウィキペディアのコード

隣接行列 A を持つグラフ G があるとします。G が二部であることはわかっています。G の頂点を常に 2 部グラフを形成する 2 つのセットに分割するにはどうすればよいですか? ありがとう！

ここで問題があり、重み付けされた 2 部一致の問題に減らすことができました。基本的に、パーティション A と B を持つ 2 部グラフと、重みを持つ一連のエッジがあります。私の場合、|A|~=20 および |B| です。=300。

重みを最小化し、 「A」をカバーするエッジのセットを見つけたい(A の各エッジには、関連付けられたソリューション エッジがあります)

質問:

-この種の問題に特別な名前があるので、アルゴリズムと解決策を探すことができますか?

-無限の重みで A にダミーの頂点を追加することにより、重み付きの 2 部の完全な一致に減らすことができることを知っています。でも |B|>>|A| 以来、実用的なパフォーマンスが心配です。

-Java ライブラリに関する提案はありますか? これを見つけました: http://algs4.cs.princeton.edu/code/。「AssignmentProblem.java」はほとんど必要なものだと思います-（しかし、完全に一致することは保証されませんか？）

事前に感謝し、英語が下手で申し訳ありません。