Changeset 14655


Ignore:
Timestamp:
02/09/17 15:58:45 (4 years ago)
Author:
gkronber
Message:

#2288: added method to calculate the difference of two variable networks

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.VariableInteractionNetworks/HeuristicLab.VariableInteractionNetworks/3.3/VariableInteractionNetwork.cs

    r14622 r14655  
    2323using System.Collections;
    2424using System.Collections.Generic;
     25using System.Diagnostics.Eventing.Reader;
    2526using System.Linq;
    2627using System.Text;
     
    4647    /// <returns></returns>
    4748    public static VariableInteractionNetwork FromNmseAndVariableImpacts(double[] nmse, DoubleMatrix variableImpacts, double nmseThreshold = 0.2, double varImpactThreshold = 0.0) {
    48       if(variableImpacts.Rows != variableImpacts.Columns) throw new ArgumentException();
     49      if (variableImpacts.Rows != variableImpacts.Columns) throw new ArgumentException();
    4950      var network = new VariableInteractionNetwork();
    5051
    5152      Dictionary<string, IVertex> name2funVertex = new Dictionary<string, IVertex>(); // store vertexes representing the function for each target so we can easily add incoming arcs later on
    5253      string[] varNames = variableImpacts.RowNames.ToArray();
    53       if(nmse.Length != varNames.Length) throw new ArgumentException();
    54 
    55       for(int i = 0; i < varNames.Length; i++) {
     54      if (nmse.Length != varNames.Length) throw new ArgumentException();
     55
     56      for (int i = 0; i < varNames.Length; i++) {
    5657        var name = varNames[i];
    5758        var varVertex = new VariableNetworkNode() { Label = name };
    5859        network.AddVertex(varVertex);
    59         if(nmse[i] < nmseThreshold) {
     60        if (nmse[i] < nmseThreshold) {
    6061          var functionVertex = new JunctionNetworkNode() { Label = "f_" + name };
    6162          name2funVertex.Add(name, functionVertex);
     
    6970      var rel = variableImpacts.CloneAsMatrix();
    7071      // make sure the diagonal is not considered
    71       for(int i = 0; i < rel.GetLength(0); i++) rel[i, i] = double.NegativeInfinity;
     72      for (int i = 0; i < rel.GetLength(0); i++) rel[i, i] = double.NegativeInfinity;
    7273
    7374      var addedArcs = AddArcs(network, rel, varNames, name2funVertex, varImpactThreshold);
    74       while(addedArcs.Any()) {
     75      while (addedArcs.Any()) {
    7576        var cycles = network.FindShortestCycles().ToList();
    76         while(cycles.Any()) {
     77        while (cycles.Any()) {
    7778          // delete weakest link
    7879          var weakestArc = cycles.SelectMany(cycle => network.ArcsForCycle(cycle)).OrderBy(a => a.Weight).First();
     
    8889    }
    8990
     91    /// <summary>
     92    /// Produces a combined network from two networks.
     93    /// The set of nodes of the new network is the union of the node sets of the two input networks.
     94    /// The set of edges of the new network is the union of the edge sets of the two input networks.
     95    /// Added and removed nodes and edges are marked so that it is possible to visualize the network difference using graphviz
     96    /// </summary>
     97    /// <returns></returns>
     98    public static VariableInteractionNetwork CalculateNetworkDiff(
     99      VariableInteractionNetwork from,
     100      VariableInteractionNetwork to) {
     101      var g = new VariableInteractionNetwork();
     102
     103      // add nodes which are in both networks
     104      foreach (var node in from.Vertices.Intersect(to.Vertices, new VertexLabelComparer())) {
     105        g.AddVertex((IVertex)node.Clone());
     106      }
     107      // add nodes only in from network
     108      foreach (var node in from.Vertices.Except(to.Vertices, new VertexLabelComparer())) {
     109        var fromVertex = (IVertex)node.Clone();
     110        fromVertex.Label += " (removed)";
     111        g.AddVertex(fromVertex);
     112      }
     113      // add nodes only in to network
     114      foreach (var node in to.Vertices.Except(from.Vertices, new VertexLabelComparer())) {
     115        var fromVertex = (IVertex)node.Clone();
     116        fromVertex.Label += " (added)";
     117        g.AddVertex(fromVertex);
     118      }
     119
     120      // add edges which are in both networks
     121      foreach (var arc in from.Arcs.Intersect(to.Arcs, new ArcComparer())) {
     122        g.AddArc(
     123          g.Vertices.Single(v => arc.Source.Label == v.Label),
     124          g.Vertices.Single(v => arc.Target.Label == v.Label)
     125        );
     126      }
     127      // add edges only in from network
     128      foreach (var arc in from.Arcs.Except(to.Arcs, new ArcComparer())) {
     129        var fromVertex =
     130          g.Vertices.Single(v => v.Label == arc.Source.Label || v.Label == arc.Source.Label + " (removed)");
     131        var toVertex =
     132          g.Vertices.Single(v => v.Label == arc.Target.Label || v.Label == arc.Target.Label + " (removed)");
     133        var newArc = g.AddArc(
     134          fromVertex,
     135          toVertex
     136        );
     137        newArc.Label += " (removed)";
     138      }
     139      // add arcs only in to network
     140      foreach (var arc in to.Arcs.Except(from.Arcs, new ArcComparer())) {
     141        var fromVertex =
     142          g.Vertices.Single(v => v.Label == arc.Source.Label || v.Label == arc.Source.Label + " (added)");
     143        var toVertex =
     144          g.Vertices.Single(v => v.Label == arc.Target.Label || v.Label == arc.Target.Label + " (added)");
     145        var newArc = g.AddArc(
     146          fromVertex,
     147          toVertex
     148        );
     149        newArc.Label += " (added)";
     150      }
     151      return g;
     152    }
     153
     154
    90155    private static List<IArc> AddArcs(VariableInteractionNetwork network, double[,] impacts, string[] varNames, Dictionary<string, IVertex> name2funVertex, double threshold = 0.0) {
    91156      var newArcs = new List<IArc>();
    92       for(int row = 0; row < impacts.GetLength(0); row++) {
    93         if(!name2funVertex.ContainsKey(varNames[row])) continue; // this variable does not have an associated function (considered as independent)
     157      for (int row = 0; row < impacts.GetLength(0); row++) {
     158        if (!name2funVertex.ContainsKey(varNames[row])) continue; // this variable does not have an associated function (considered as independent)
    94159
    95160        var rowVector = Enumerable.Range(0, impacts.GetLength(0)).Select(col => impacts[row, col]).ToArray();
    96161        var max = rowVector.Max();
    97         if(max > threshold) {
     162        if (max > threshold) {
    98163          var idxOfMax = Array.IndexOf<double>(rowVector, max);
    99164          impacts[row, idxOfMax] = double.NegativeInfinity; // edge is not considered anymore
     
    121186    private IList<IArc> ArcsForCycle(IList<IVertex> cycle) {
    122187      var res = new List<IArc>();
    123       foreach(var t in cycle.Zip(cycle.Skip(1), Tuple.Create)) {
     188      foreach (var t in cycle.Zip(cycle.Skip(1), Tuple.Create)) {
    124189        var src = t.Item1;
    125190        var dst = t.Item2;
     
    133198    // finds the shortest cycles in the graph and returns all sub-graphs containing only the nodes / edges within the cycle
    134199    public IEnumerable<IList<IVertex>> FindShortestCycles() {
    135       foreach(var startVariable in base.Vertices.OfType<VariableNetworkNode>()) {
    136         foreach(var cycle in FindShortestCycles(startVariable))
     200      foreach (var startVariable in base.Vertices.OfType<VariableNetworkNode>()) {
     201        foreach (var cycle in FindShortestCycles(startVariable))
    137202          yield return cycle;
    138203      }
     
    154219    // TODO efficiency
    155220    private void FindShortestCycles(Queue<List<IVertex>> queue, int maxPathLength, List<List<IVertex>> cycles) {
    156       while(queue.Any()) {
     221      while (queue.Any()) {
    157222        var path = queue.Dequeue();
    158         if(path.Count > 1 && path.First() == path.Last()) {
     223        if (path.Count > 1 && path.First() == path.Last()) {
    159224          cycles.Add(new List<IVertex>(path)); // found a cycle
    160         } else if(path.Count >= maxPathLength) {
     225        } else if (path.Count >= maxPathLength) {
    161226          continue;
    162227        } else {
    163228          var lastVert = path.Last();
    164229          var neighbours = base.Arcs.Where(a => a.Source == lastVert).Select(a => a.Target);
    165           foreach(var neighbour in neighbours) {
     230          foreach (var neighbour in neighbours) {
    166231            queue.Enqueue(new List<IVertex>(path.Concat(new IVertex[] { neighbour })));
    167232          }
     
    177242
    178243      var name2idx = new Dictionary<string, int>();
    179       for(int i = 0; i < names.Length; i++) {
     244      for (int i = 0; i < names.Length; i++) {
    180245        name2idx.Add(names[i], i);
    181246      }
    182247
    183       foreach(var arc in Arcs) {
     248      foreach (var arc in Arcs) {
    184249        // only consider arcs going into a junction node
    185250        var target = arc.Target as JunctionNetworkNode;
    186         if(target != null)
    187         {
     251        if (target != null) {
    188252          var srcVarName = arc.Source.Label;
    189253          // each function node must have exactly one outgoing arc
     
    199263
    200264    public string ToGraphVizString() {
     265      Func<string, string> NodeAndEdgeColor = (str) =>
     266      {
     267        if (string.IsNullOrEmpty(str)) return "black";
     268        else if (str.Contains("removed")) return "red";
     269        else if (str.Contains("added")) return "green";
     270        else return "black";
     271      };
     272
    201273      var sb = new StringBuilder();
    202274      sb.AppendLine("digraph {");
    203275      sb.AppendLine("rankdir=LR");
    204       foreach(var v in Vertices.OfType<VariableNetworkNode>()) {
    205         sb.AppendFormat("\"{0}\" [shape=oval]", v.Label).AppendLine();
    206       }
    207       foreach(var v in Vertices.OfType<JunctionNetworkNode>()) {
    208         sb.AppendFormat("\"{0}\" [shape=box]", v.Label).AppendLine();
    209       }
    210       foreach(var arc in Arcs) {
    211         sb.AppendFormat("\"{0}\"->\"{1}\"", arc.Source.Label, arc.Target.Label).AppendLine();
     276      foreach (var v in Vertices.OfType<VariableNetworkNode>()) {
     277        sb.AppendFormat("\"{0}\" [shape=oval, color={1}]", v.Label, NodeAndEdgeColor(v.Label)).AppendLine();
     278      }
     279      foreach (var v in Vertices.OfType<JunctionNetworkNode>()) {
     280        sb.AppendFormat("\"{0}\" [shape=box, color={1}]", v.Label, NodeAndEdgeColor(v.Label)).AppendLine();
     281      }
     282      foreach (var arc in Arcs) {
     283        sb.AppendFormat("\"{0}\"->\"{1}\" [color=\"{3}\"]", arc.Source.Label, arc.Target.Label, arc.Label, NodeAndEdgeColor(arc.Label)).AppendLine();
    212284      }
    213285      sb.AppendLine("}");
    214286      return sb.ToString();
     287    }
     288  }
     289
     290  public class VertexLabelComparer : IEqualityComparer<IVertex> {
     291    public bool Equals(IVertex x, IVertex y) {
     292      if (x == null && y == null) return true;
     293      if (x != null && y != null) {
     294        return x.Label == y.Label;
     295      } else return false;
     296    }
     297
     298    public int GetHashCode(IVertex obj) {
     299      return obj.Label.GetHashCode();
     300    }
     301  }
     302
     303  public class ArcComparer : IEqualityComparer<IArc> {
     304    public bool Equals(IArc x, IArc y) {
     305      if (x == null && y == null) return true;
     306      if (x != null && y != null) {
     307        return x.Source.Label == y.Source.Label && x.Target.Label == y.Target.Label;
     308      } else return false;
     309    }
     310
     311    public int GetHashCode(IArc obj) {
     312      return obj.Source.Label.GetHashCode() ^ obj.Target.Label.GetHashCode();
    215313    }
    216314  }
Note: See TracChangeset for help on using the changeset viewer.