var heads = new Bridge [FAN_OUT];
for (int i = 0; i < FAN_OUT; ++i)
heads [i] = new Bridge ();
- var multiplexer = new Bridge [FAN_OUT];
- for (int i = 0; i < FAN_OUT; ++i)
- {
- heads [i].Links.Add (multiplexer);
- multiplexer [i] = new Bridge ();
+
+ // We make five identical multiplexers to verify Tarjan-bridge can merge them together correctly.
+ var MULTIPLEXER_COUNT = 5;
+ Bridge[] multiplexer0 = null;
+ for(int m = 0; m < MULTIPLEXER_COUNT; m++) {
+ var multiplexer = new Bridge [FAN_OUT];
+ if (m == 0) {
+ multiplexer0 = multiplexer;
+ for (int i = 0; i < FAN_OUT; ++i)
+ {
+ heads [i].Links.Add (multiplexer);
+ multiplexer [i] = new Bridge ();
+ }
+ } else {
+ for (int i = 0; i < FAN_OUT; ++i)
+ {
+ heads [i].Links.Add (multiplexer);
+ multiplexer [i] = multiplexer0 [i];
+ }
+ }
}
- Console.WriteLine ("-double fan done-");
+
+ Console.WriteLine ("-double fan x5 done-");
}
/*
tail.Link = tail;
}
+ const int L0_COUNT = 100000;
+ const int L1_COUNT = 100000;
+ const int EXTRA_LEVELS = 4;
+
+ /*
+ Set a complex graph from one bridge to a couple.
+ The graph is designed to expose naive coloring on
+ tarjan and SCC explosion on classic.
+ */
+ static void Spider () {
+ Bridge a = new Bridge ();
+ Bridge b = new Bridge ();
+
+ var l1 = new List<object> ();
+ for (int i = 0; i < L0_COUNT; ++i) {
+ var l0 = new List<object> ();
+ l0.Add (a);
+ l0.Add (b);
+ l1.Add (l0);
+ }
+ var last_level = l1;
+ for (int l = 0; l < EXTRA_LEVELS; ++l) {
+ int j = 0;
+ var l2 = new List<object> ();
+ for (int i = 0; i < L1_COUNT; ++i) {
+ var tmp = new List<object> ();
+ tmp.Add (last_level [j++ % last_level.Count]);
+ tmp.Add (last_level [j++ % last_level.Count]);
+ l2.Add (tmp);
+ }
+ last_level = l2;
+ }
+ Bridge c = new Bridge ();
+ c.Links.Add (last_level);
+ }
+
static void RunTest (ThreadStart setup)
{
var t = new Thread (setup);
t.Join ();
for (int i = 0; i < 5; ++i) {
+ Console.WriteLine("-GC {0}/5-", i);
GC.Collect ();
GC.WaitForPendingFinalizers ();
}
RunTest (SetupDoubleFan);
RunTest (SetupDeadList);
RunTest (SetupSelfLinks);
+ RunTest (Spider);
for (int i = 0; i < 0; ++i) {
GC.Collect ();