私は F# の初心者で、本格的なプログラミングを初めて試みました。コードが少し長くて申し訳ありませんが、理解できない可変性の問題がいくつかあります。
これは、無向グラフ コンポーネントの最小カットを計算する Karger MinCut アルゴリズムの実装です。詳細については、ここではアルゴリズムの仕組みについては説明しませんhttps://en.wikipedia.org/wiki/Karger%27s_algorithm 重要なのは、ランダム化されたアルゴリズムであり、決められた回数の試行を実行し、 「最高の」走り。
ランダム試行ごとに特定の関数を作成すれば、以下の多くの問題を回避できることがわかりましたが、以下の実装の何が問題なのかを正確に理解したいと思います。
この単純なグラフでコードを実行しています (グラフを 2 つのコンポーネント (1,2,3,4) と (5,6,7,8) に分割し、これら 2 つのコンポーネントの間に 2 つのエッジしかない場合、最小カットは 2 です) )
3--4-----5--6
|\/| |\/|
|/\| |/\|
2--1-----7--8
ファイルsimplegraph.txtはこのグラフを次のようにエンコードする必要があります (最初の列 = ノード番号、他の列 = リンク)
1 2 3 4 7
2 1 3 4
3 1 2 4
4 1 2 3 5
5 4 6 7 8
6 5 7 8
7 1 5 6 8
8 5 6 7
このコードはまだ命令型プログラミングのように見えるかもしれませんが、申し訳ありません。
そのため、各試行を呼び出すメインの for i ループがあります。最初の実行 (i=1 の場合) はスムーズで完璧に見えますが、i=2 の場合は実行時エラーが発生します。これは、WG などの変数が正しく再初期化されず、範囲外のエラーが発生するように見えるためです。
WG、WG1、および WGmin はtype wgraphobj、ディクショナリオブジェクト
のレコードであり、 WG1 はメイン ループの外側で定義され、WG1 に新しい割り当てを行いません。
[しかし、残念ながら、そのタイプは変更可能です]
私は指示で最初のWGを定義しました
let mutable WG = WG1
次に for i ループの最初に、次のように書きます。
WG <- WG1
その後、試行ごとに WG オブジェクトを変更して計算を行います。試用が終了し、次の試用に進むとき (i が増加) WG を WG1 のような初期状態にリセットしたい。しかし、それは機能していないようで、理由がわかりません...
ここに完全なコードがあります
MyModule.fs [一部実行に不要な機能]
namespace MyModule
module Dict =
open System.Collections.Generic
let toSeq d = d |> Seq.map (fun (KeyValue(k,v)) -> (k,v))
let toArray (d:IDictionary<_,_>) = d |> toSeq |> Seq.toArray
let toList (d:IDictionary<_,_>) = d |> toSeq |> Seq.toList
let ofMap (m:Map<'k,'v>) = new Dictionary<'k,'v>(m) :> IDictionary<'k,'v>
let ofList (l:('k * 'v) list) = new Dictionary<'k,'v>(l |> Map.ofList) :> IDictionary<'k,'v>
let ofSeq (s:('k * 'v) seq) = new Dictionary<'k,'v>(s |> Map.ofSeq) :> IDictionary<'k,'v>
let ofArray (a:('k * 'v) []) = new Dictionary<'k,'v>(a |> Map.ofArray) :> IDictionary<'k,'v>
Karger.fs
open MyModule.Dict
open System.IO
let x = File.ReadAllLines "\..\simplegraph.txt";;
// val x : string [] =
let splitAtTab (text:string)=
text.Split [|'\t';' '|]
let splitIntoKeyValue (s:seq<'T>) =
(Seq.head s, Seq.tail s)
let parseLine (line:string)=
line
|> splitAtTab
|> Array.filter (fun s -> not(s=""))
|> Array.map (fun s-> (int s))
|> Array.toSeq
|> splitIntoKeyValue
let y =
x |> Array.map parseLine
open System.Collections.Generic
// let graph = new Map <int, int array>
let graphD = new Dictionary<int,int seq>()
y |> Array.iter graphD.Add
let graphM = y |> Map.ofArray //immutable
let N = y.Length // number of nodes
let Nruns = 2
let remove_table = new Dictionary<int,bool>()
[for i in 1..N do yield (i,false)] |> List.iter remove_table.Add
// let remove_table = seq [|for a in 1 ..N -> false|] // plus court
let label_head_table = new Dictionary<int,int>()
[for i in 1..N do yield (i,i)] |> List.iter label_head_table.Add
let label = new Dictionary<int,int seq>()
[for i in 1..N do yield (i,[i])] |> List.iter label.Add
let mutable min_cut = 1000000
type wgraphobj =
{ Graph : Dictionary<int,int seq>
RemoveTable : Dictionary<int,bool>
Label : Dictionary<int,int seq>
LabelHead : Dictionary<int,int> }
let WG1 = {Graph = graphD;
RemoveTable = remove_table;
Label = label;
LabelHead = label_head_table}
let mutable WGmin = WG1
let IsNotRemoved x = //
match x with
| (i,false) -> true
| (i,true) -> false
let IsNotRemoved1 WG i = //
(i,WG.RemoveTable.[i]) |>IsNotRemoved
let GetLiveNode d =
let myfun x =
match x with
| (i,b) -> i
d |> toList |> List.filter IsNotRemoved |> List.map myfun
let rand = System.Random()
// subsets a dictionary given a sub_list of keys
let D_Subset (dict:Dictionary<'T,'U>) (sub_list:list<'T>) =
let z = Dictionary<'T,'U>() // create new empty dictionary
sub_list |> List.filter (fun k -> dict.ContainsKey k)
|> List.map (fun k -> (k, dict.[k]))
|> List.iter (fun s -> z.Add s)
z
// subsets a dictionary given a sub_list of keys to remove
let D_SubsetC (dict:Dictionary<'T,'U>) (sub_list:list<'T>) =
let z = dict
sub_list |> List.filter (fun k -> dict.ContainsKey k)
|> List.map (fun k -> (dict.Remove k)) |>ignore
z
// subsets a sequence by values in a sequence
let S_Subset (S:seq<'T>)(sub_list:seq<'T>) =
S |> Seq.filter (fun s-> Seq.exists (fun elem -> elem = s) sub_list)
let S_SubsetC (S:seq<'T>)(sub_list:seq<'T>) =
S |> Seq.filter (fun s-> not(Seq.exists (fun elem -> elem = s) sub_list))
[<EntryPoint>]
let main argv =
let mutable u = 0
let mutable v = 0
let mutable r = 0
let mutable N_cut = 1000000
let mutable cluster_A_min = seq [0]
let mutable cluster_B_min = seq [0]
let mutable WG = WG1
let mutable LiveNodeList = [0]
// when i = 2, i encounter problems with mutability
for i in 1 .. Nruns do
WG <- WG1
printfn "%d" i
for k in 1..(N-2) do
LiveNodeList <- GetLiveNode WG.RemoveTable
r <- rand.Next(0,N-k)
u <- LiveNodeList.[r] //selecting a live node
let uuu = WG.Graph.[u] |> Seq.map (fun s -> WG.LabelHead.[s] )
|> Seq.filter (IsNotRemoved1 WG)
|> Seq.distinct
let n_edge = uuu |> Seq.length
let x = rand.Next(1,n_edge)
let mutable ok = false //maybe we can take this out
while not(ok) do
// selecting the edge from node u
v <- WG.LabelHead.[Array.get (uuu |> Seq.toArray) (x-1)]
let vvv = WG.Graph.[v] |> Seq.map (fun s -> WG.LabelHead.[s] )
|> Seq.filter (IsNotRemoved1 WG)
|> Seq.distinct
let zzz = S_SubsetC (Seq.concat [uuu;vvv] |> Seq.distinct) [u;v]
WG.Graph.[u] <- zzz
let lab_u = WG.Label.[u]
let lab_v = WG.Label.[v]
WG.Label.[u] <- Seq.concat [lab_u;lab_v] |> Seq.distinct
if (k<N-1) then
WG.RemoveTable.[v]<-true
//updating Label_head for all members of Label.[v]
WG.LabelHead.[v]<- u
for j in WG.Label.[v] do
WG.LabelHead.[j]<- u
ok <- true
printfn "u= %d v=%d" u v
// end of for k in 1..(N-2)
// counting cuts
// u,v contain the 2 indexes of groupings
let cluster_A = WG.Label.[u]
let cluster_B = S_SubsetC (seq[for i in 1..N do yield i]) cluster_A // defined as complementary of A
// let WG2 = {Graph = D_Subset WG1.Graph (cluster_A |> Seq.toList)
// RemoveTable = remove_table
// Label = D_Subset WG1.Graph (cluster_A |> Seq.toList)
// LabelHead = label_head_table}
let cross_edge = // returns keyvalue pair (k,S')
let IsInCluster cluster (k,S) =
(k,S_Subset S cluster)
graphM |> toSeq |> Seq.map (IsInCluster cluster_B)
N_cut <-
cross_edge |> Seq.map (fun (k:int,v:int seq)-> Seq.length v)
|> Seq.sum
if (N_cut<min_cut) then
min_cut <- N_cut
WGmin <- WG
cluster_A_min <- cluster_A
cluster_B_min <- cluster_B
// end of for i in 1..Nruns
0 // return an integer exit code
アルゴリズムの説明: (私の問題を解決するのにそれほど重要ではないと思います)
各試行で、いくつかの手順があります。各ステップで、2 つのノードを 1 つにマージし (実質的に 1 つを削除)、グラフを更新します。これを 6 回繰り返して、残りのノードが 2 つになるまで (2 つのクラスターとして定義します)、これら 2 つのクラスター間のクロス エッジの数を調べます。「運が良ければ」これらの 2 つのクラスターは (1,2,3,4) と (5,6,7,8) になり、適切な数のカットが見つかります。各ステップで、オブジェクト WG が更新され、LiveNode (2 つのノードをマージした結果として除去されないもの) のみを使用して 2 つのノードをマージする効果が完全に最新に保たれます。
WG.Graph は更新されたグラフです
WG.Label には、現在のノードにマージされたノードのラベルが含まれています
WG.LabelHead には、そのノードがマージされたノードのラベルが含まれます
WG.RemoveTable は、ノードが削除されたかどうかを示します。
見てくださる方、よろしくお願いします！