From ad4db1abd7c4f22e5c0bf025e3d7a70110a6a3f0 Mon Sep 17 00:00:00 2001
From: marko <marko>
Date: Thu, 13 Dec 2007 12:50:39 +0000
Subject: [PATCH] Implement a simple algorithm for generating random connected
 topologies.

Bug found by:
Submitted by:	Mirta Medanic <mirta.medanic at fer.hr>
Requested by:
Reviewed by:
Approved by:
Obtained from:
---
 topogen.tcl | 48 ++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 46 insertions(+), 2 deletions(-)

diff --git a/topogen.tcl b/topogen.tcl
index c17e2d5..2751c84 100755
--- a/topogen.tcl
+++ b/topogen.tcl
@@ -1,4 +1,4 @@
-# $Id: topogen.tcl,v 1.2.2.1 2007/05/07 08:20:10 ana Exp $ 
+# $Id: topogen.tcl,v 1.2.2.2 2007/12/13 12:50:39 marko Exp $ 
 #
 # Copyright 2007 University of Zagreb, Croatia.  All rights reserved.
 #
@@ -91,6 +91,21 @@ for { set i 1 } { $i <= 12 } { incr i } {
     }
 }
 
+set m .menubar.t_g.random
+menu $m -tearoff 0
+.menubar.t_g add cascade -label "Random" -menu $m -underline 0 -state disabled
+for { set i 3 } { $i <= 24 } { incr i } {
+    set n $m.$i
+    menu $n -tearoff 0
+    $m add cascade -label "R($i,m)" -menu $n -underline 0
+    set l [expr $i - 1]
+    for { set j $l } { $j < [expr { $i * $l / 2 }] } { incr j } {
+	$n add command -label "R($i,$j)" -command "R \[newNodes $i\] $j"
+	if { $j > [expr $i + 24] } {
+	    break
+	}
+    }
+}
 
 proc newNodes { n } {
     global curcanvas grid sizex sizey activetool
@@ -216,5 +231,34 @@ proc Kb { v1 v2 } {
 
 proc Kbhelper { n m } {
     set v [newNodes [expr $n + $m]]
-    Kb [lrange $v 0 [expr $n -1]] [lrange $v $n end]
+    Kb [lrange $v 0 [expr $n - 1]] [lrange $v $n end]
+}
+
+#
+# Random
+#
+proc R { v m } {
+    set cn [lindex $v 0]
+    set dn [lrange $v 1 end]
+    
+    set i 0
+    while { $i < $m } {
+	if { [llength $dn] > 0 } {
+	    set node_1 [expr int(rand() * [llength $cn])]
+	    set node_2 [expr int(rand() * [llength $dn])]
+	    newLink [lindex $cn $node_1] [lindex $dn $node_2]
+	    lappend cn [lindex $dn $node_2]
+	    set dn [lreplace $dn $node_2 $node_2]
+	    incr i
+	} else {
+	    set node_1 [expr int(rand() * [llength $v])]
+	    set node_2 [expr int(rand() * [llength $v])]
+	    if { $node_1 != $node_2 &&
+		[linkByPeers [lindex $v $node_1] [lindex $v $node_2]] == ""} {
+		newLink [lindex $v $node_1] [lindex $v $node_2]
+		incr i
+	    }
+	}
+    }
+    topoGenDone $v
 }
-- 
2.39.5