ネットワークデータのランダム化

Question

前提・実現したいこと

ネットワークデータが枝リスト形式で記されているファイルがあります。
(例)
0 1
0 2
1 3
1 5
2 1
2 4
2 5
3 0
4 5

このネットワークデータの頂点数、辺数、各頂点の次数を変えずに、枝をランダムにつなぎ変えた、新たなネットワークデータを作成するプログラムをc言語で作成したいです。

Comments

[y_waiwai]

質問は編集できます
追記修正しよう

[ozwk]

質問は何でしょうか
これではただの決意表明です

[DreamTheater]

他ユーザの質問文などを参考に編集してみてください。

Answer 1

ループを許容するならば、数値(頂点)を適当にシャッフルしてやればいいです。

Comments

[fana]

「各頂点の次数を変えずに」を満たすことを単純に考えると，「次数が同じ頂点同士を入れ替える」というのが思いつきますが……
そこらへんの事柄が全て「適当に」という語に（「＝適切に」という意味で）含まれている，ということでしょうか．
それとも，そういう条件無しにシャッフルしてもＯＫということでしょうか．

[asm]

次数は出現回数と等しくなりますし、無条件で問題ないと思いますよ
※有向グラフおよび孤立点を考えない場合

[fana]

自分，ここで言うところの「シャッフル」の意味がわかってないかも(?)です．例えば入力が
0 1
0 2
1 3
のとき，グラフを図にすると
2←→0←→1←→3
みたくなると思うのです．（"←→"は辺を示す）

ここで頂点 2と3 を入れ替えると
3←→0←→1←→2
となりますが，「頂点2」と「頂点3」の次数は入れ替え前後で変わってません(どちらも次数は1のまま)．

でも，0と2を入れ替えちゃうとしたら，結果は
0←→2←→1←→3
となって，「頂点0」の次数は入れ替え前後で(次数2から次数1に)変化したということになりませんか？

[asm]

普通に[0,1,0,2,1,3]という一次元の配列を作って、
シャッフルし[2, 1, 1, 0, 3, 0]という配列をつくり2個ずつ取り出して
2 1
1 0
3 0
というリストが生まれ
2<-->1 <-->0<-->3
になります。

[fana]

なるほど，意味を把握しました．
激しく感謝．