context: /*
  This program is part of Brunet, a library for autonomic overlay networks.
  Copyright (C) 2008 David Wolinsky davidiw@ufl.edu, Unversity of Florida
  
  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  */
  
  using Brunet.Util;
  
  using System;
  using System.Collections.Generic;
  using System.IO;
  using System.Security.Cryptography;
  using System.Threading;
  
  namespace Brunet.Graph {
    ///<summary>Graph provides the ability to test routing algorithms for
    ///ring-based structured p2p networks</summary>
    ///<remarks>Key features provided by Graph include support for Tunnels,
    ///latency, hop count, user specified latency, tweaking of network size,
    ///near neighbor count, shortcut count.</remarks>
    public class Graph {
      public const int DHT_DEGREE = 8;
      protected Dictionary<AHAddress, GraphNode> _addr_to_node;
      protected List<AHAddress> _addrs;
      protected Random _rand;
      protected Dictionary<AHAddress, int>  _addr_to_index;
      protected List<List<int>> _latency_map = null;
  
      public Graph(int count, int near, int shortcuts) :
        this(count, near, shortcuts, (new Random()).Next())
      {
      }
  
      public Graph(int count, int near, int shortcuts, int seed) :
        this(count, near, shortcuts, seed, null)
      {
      }
  
      ///</summary>Creates a new Graph for simulate routing algorithms.</summary>
      ///<param name="count">The network size not including the clusters.</param>
      ///<param name="near">The amount of connections on the left or right of a 
      ///node.</param>
      ///<param name="shortcuts">The amount of far connections had per node.</param>
      ///<param name="latency">(optional)count x count matrix containing the
      ///latency between ///two points.</param>
      ///<param name="cluster_count">A cluster is a 100 node network operating on
      ///a single point in the network.  A cluster cannot communicate directly
      ///with another cluster.</param>
      ///<param name="dataset">A square dataset consisting of pairwise latencies.</param>
      public Graph(int count, int near, int shortcuts, int random_seed, List<List<int>> dataset)
      {
        _latency_map = dataset;
  
        _rand = new Random(random_seed);
        GraphNode.SetSeed(_rand.Next());
  
        _addr_to_node = new Dictionary<AHAddress, GraphNode>(count);
        _addrs = new List<AHAddress>(count);
        _addr_to_index = new Dictionary<AHAddress, int>(count);
  
        // first we create our regular network
        while(_addrs.Count < count) {
          AHAddress addr = GenerateAddress();
          GraphNode node = new GraphNode(addr);
          _addr_to_node[addr] = node;
          _addrs.Add(addr);
        }
  
        FixLists();
  
        for(int i = 0; i < count; i++) {
          GraphNode cnode = _addr_to_node[_addrs[i]];
          ConnectionList cons = cnode.ConnectionTable.GetConnections(ConnectionType.Structured);
          // We select our left and right neighbors up to near out (so we get 2*near connections)
          // Then we check to make sure we don't already have this connection, since the other guy
          // may have added it, if we don't we create one and add it.
          for(int j = 1; j <= near; j++) {
            int left = i - j;
            if(left < 0) {
              left += count;
            }
            GraphNode lnode = _addr_to_node[_addrs[left]];
            if(!cons.Contains(lnode.Address)) {
              int delay = CalculateDelay(cnode, lnode);
              AddConnection(cnode, lnode, delay);
              AddConnection(lnode, cnode, delay);
            }
  
            int right = i+j;
            if(right >= count) {
              right -= count;
            }
            GraphNode rnode = _addr_to_node[_addrs[right]];
            // No one has this connection, let's add it to both sides.
            if(!cons.Contains(rnode.Address)) {
              int delay = CalculateDelay(cnode, rnode);
              AddConnection(cnode, rnode, delay);
              AddConnection(rnode, cnode, delay);
            }
          }
          
          // Let's add shortcuts so that we have at least the minimum number of shortcuts
          while(cnode.Shortcuts < shortcuts) {
            cons = cnode.ConnectionTable.GetConnections(ConnectionType.Structured);
            AHAddress addr = ComputeShortcutTarget(cnode.Address);
            addr = FindNodeNearestToAddress(addr);
            if(cons.Contains(addr) || addr.Equals(cnode.Address)) {
              continue;
            }
            GraphNode snode = _addr_to_node[addr];
            cons = snode.ConnectionTable.GetConnections(ConnectionType.Structured);
            int delay = CalculateDelay(cnode, snode);
            if(delay == -1) {
              continue;
            }
            AddConnection(cnode, snode, delay);
            AddConnection(snode, cnode, delay);
            cnode.Shortcuts++;
            snode.Shortcuts++;
          }
        }
  
        foreach(GraphNode gn in _addr_to_node.Values) {
          gn.UpdateSystem();
        }
      }
  
      protected AHAddress GenerateAddress()
      {
        AHAddress addr = null;
        do {
          byte[] baddr = new byte[Address.MemSize];
          _rand.NextBytes(baddr);
          Address.SetClass(baddr, AHAddress.ClassValue);
          addr = new AHAddress(MemBlock.Reference(baddr));
        } while(_addr_to_node.ContainsKey(addr));
        return addr;
      }
  
      protected void FixLists()
      {
        _addrs.Sort();
  
        for(int i = 0; i < _addrs.Count; i++) {
          _addr_to_index[_addrs[i]] = i;
        }
      }
  
      ///<summary>Calculates the delay between two nodes.</summary>
      protected virtual int CalculateDelay(GraphNode node1, GraphNode node2)
      {
        if(_latency_map != null) {
          int mod = _latency_map.Count;
          int x = node1.UniqueID % mod;
          int y = node2.UniqueID % mod;
          return (int) (_latency_map[x][y] / 1000.0);
        }
  
        return _rand.Next(10, 240);
      }
  
      ///<summary>Creates an edge and a connection from node2 to node1 including
      ///the edge.  Note:  this is unidirectional, this must be called twice,
      ///swapping node1 with node2 for a connection to be complete.</summary>
      protected void AddConnection(GraphNode node1, GraphNode node2, int delay)
      {
        Edge edge = new GraphEdge(delay);
        Connection con = new Connection(edge, node2.Address, ConnectionType.Structured.ToString(), null, null);
        node1.ConnectionTable.Add(con);
      }
  
      /// <summary>Calculates a shortcut using a harmonic distribution as in a
      /// Symphony-lke shortcut.</summary>
      protected virtual AHAddress ComputeShortcutTarget(AHAddress addr)
      {
        int network_size = _addrs.Count;
        double logN = (double)(Brunet.Address.MemSize * 8);
        double logk = Math.Log( (double) network_size, 2.0 );
        double p = _rand.NextDouble();
        double ex = logN - (1.0 - p)*logk;
        int ex_i = (int)Math.Floor(ex);
        double ex_f = ex - Math.Floor(ex);
        //Make sure 2^(ex_long+1)  will fit in a long:
        int ex_long = ex_i % 63;
        int ex_big = ex_i - ex_long;
        ulong dist_long = (ulong)Math.Pow(2.0, ex_long + ex_f);
        //This is 2^(ex_big):
        BigInteger big_one = 1;
        BigInteger dist_big = big_one << ex_big;
        BigInteger rand_dist = dist_big * dist_long;
  
        // Add or subtract random distance to the current address
        BigInteger t_add = addr.ToBigInteger();
  
        // Random number that is 0 or 1
        if( _rand.Next(2) == 0 ) {
          t_add += rand_dist;
        }
        else {
          t_add -= rand_dist;
        }
  
        BigInteger target_int = new BigInteger(t_add % Address.Full);
        if((target_int & 1) == 1) {
          target_int -= 1;
        }
  
        byte[]buf = Address.ConvertToAddressBuffer(target_int);
  
        Address.SetClass(buf, AHAddress.ClassValue);
        return new AHAddress(buf);
      }
  
      protected AHAddress FindNodeNearestToAddress(AHAddress addr)
      {
        int index = _addrs.BinarySearch(addr);
        AHAddress to_use = addr;
  
        if(index < 0) { 
          index = ~index;
          if(index == _addrs.Count) {
            index = 0;
          }
          AHAddress right = _addrs[index];
          if(index == 0) {
  
gt:           index = _addrs.Count - 1;