text: ﻿/* ***************************************************************************
   * This file is part of SharpNEAT - Evolution of Neural Networks.
   * 
   * Copyright 2004-2016 Colin Green (sharpneat@gmail.com)
   *
   * SharpNEAT is free software; you can redistribute it and/or modify
   * it under the terms of The MIT License (MIT).
   *
   * You should have received a copy of the MIT License
   * along with SharpNEAT; if not, see https://opensource.org/licenses/MIT.
   */
  using System.Collections.Generic;
  
  namespace SharpNeat.Network
  {
      /// <summary>
      /// An algorithm for analysing cyclic networks and calculating the depth of each node in the network.
      /// Bias and input nodes are defined as being at depth 0, the depth of all other nodes is defined as 
      /// the maximum number of hops from the depth 0 nodes, so where multiple paths exist to a node (potentially
      /// with different numbers of hops) we take the maximum number of hops as that node's depth. 
      /// 
      /// The number of hops to a node ignores any cycles in the connectivity, that is, the number of hops is the 
      /// number of hops in the direct routes to a node (no node in the pathway more than once, hence not including 
      /// any cycles)
      /// </summary>
      public class CyclicNetworkDepthAnalysis
      {
          /// <summary>
          /// Connectivity data for the INetworkDefinition that is currently being tested.
          /// </summary>
          NetworkConnectivityData _networkConnectivityData;
  
          /// <summary>
          /// Dictionary of node depths keyed by node ID. Working data.
          /// </summary>
          readonly Dictionary<uint,int> _nodeDepthById = new Dictionary<uint,int>();
  
          #region Public Methods
  
          /// <summary>
          /// Calculate node depths in an acyclic network.
          /// </summary>
          public NetworkDepthInfo CalculateNodeDepths(INetworkDefinition networkDef)
          {
              // Clear any existing state (allow reuse of this class).
              _nodeDepthById.Clear();
  
              // Get and store connectivity data for the network.
              _networkConnectivityData = networkDef.GetConnectivityData();
  
              // Loop over all input (and bias) nodes; Perform a depth first traversal of each in turn.
              // Set of nodes visited in the current traversal (reset before each individual depth first traversal).
              HashSet<uint> visitedNodeSet = new HashSet<uint>();
              int inputAndBiasCount = networkDef.InputNodeCount + 1;
              for(int i=0; i<inputAndBiasCount; i++)
              {
                  visitedNodeSet.Clear();
                  TraverseNode(_networkConnectivityData.GetNodeDataByIndex(i), visitedNodeSet, 0);
              }
  
              // Extract node depths from _nodeDepthById into an array of depths (node depth by node index).
              // Note. Any node not in the dictionary is in an isolated sub-network and will be assigned to 
              // layer 0 by default.
              INodeList nodeList = networkDef.NodeList;
              int nodeCount = nodeList.Count;
              int[] nodeDepthArr = new int[nodeCount];
              int maxDepth = 0;
  
              // Loop over nodes and set the node depth. Skip over input and bias nodes, they are defined as 
              // being in layer zero.
              for(int i=inputAndBiasCount; i<nodeCount; i++)
              {
                  // Lookup the node's depth. If not found depth remains set to zero.
                  int depth;
                  if(_nodeDepthById.TryGetValue(nodeList[i].Id, out depth)) 
                  {
                      nodeDepthArr[i] = depth;
                      // Also determine maximum depth, that is, total depth of the network.
                      if(depth > maxDepth) {
                          maxDepth = depth;
                      }
                  }
              }
  
              // Return depth analysis info.
              return new NetworkDepthInfo(maxDepth+1, nodeDepthArr);
          }
  
          #endregion
  
          #region Private Methods
  
          private void TraverseNode(NodeConnectivityData nodeData, HashSet<uint> visitedNodeSet, int depth)
          {
              // Check if the node has already been encountered during the current traversal (have we followed a cycle in the connectivity).
              if(visitedNodeSet.Contains(nodeData._id)) 
              {   // Don't follow cycles.
                  return;
              }
  
              // Register the visit.
              visitedNodeSet.Add(nodeData._id);
  
              // Check if the node has been traversed by a previous traversal.
              int assignedDepth;
              if(_nodeDepthById.TryGetValue(nodeData._id, out assignedDepth) && assignedDepth >= depth)
              {   // The node already has already been visited via a path that assigned it a greater depth than the 
                  // current path. Stop traversing this path.
                  return;
              }
  
              // Either this is the first visit to the node *or* the node has been visited, but via a shorter path.
              // Either way we assign it the current depth value and traverse into its targets to update/set their depth.
              _nodeDepthById[nodeData._id] = depth;
              foreach(uint targetId in nodeData._tgtNodes)
              {
                  TraverseNode(_networkConnectivityData.GetNodeDataById(targetId), visitedNodeSet, depth + 1);
              }
          }
  
          #endregion
      }
  }
  