org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/synchronization/graph/SyncSpanningTree.java

   1 /*******************************************************************************
   2  * Copyright (c) 2014 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are made
   5  * available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *   Geneviève Bastien - Initial implementation and API
  11  *******************************************************************************/
  12
  13 package org.eclipse.linuxtools.internal.tmf.core.synchronization.graph;
  14
  15 import java.math.BigDecimal;
  16 import java.util.List;
  17 import java.util.SortedSet;
  18 import java.util.TreeSet;
  19
  20 import org.eclipse.linuxtools.internal.tmf.core.synchronization.ITmfTimestampTransformInvertible;
  21 import org.eclipse.linuxtools.tmf.core.synchronization.ITmfTimestampTransform;
  22 import org.eclipse.linuxtools.tmf.core.synchronization.TimestampTransformFactory;
  23
  24 /**
  25  * Implements a tree to calculate the synchronization between hosts
  26  *
  27  * TODO: This minimal implementation does not take into account the accuracy of
  28  * the synchronization or the number of hops between 2 traces. A great
  29  * improvement would be to implement Masoume Jabbarifar's minimal spanning tree
  30  * algorithm to select reference trace(s) and optimal path to each node of the
  31  * tree.
  32  *
  33  * @author Geneviève Bastien
  34  */
  35 public class SyncSpanningTree {
  36
  37     private final SyncGraph<String, ITmfTimestampTransform> fSyncGraph;
  38
  39     /*
  40      * Using a TreeSet here to make sure the order of the hosts, and thus the
  41      * reference node, is predictable, mostly for unit tests.
  42      */
  43     private SortedSet<String> fHosts = new TreeSet<>();
  44
  45     /**
  46      * Default constructor
  47      */
  48     public SyncSpanningTree() {
  49         fSyncGraph = new SyncGraph<>();
  50     }
  51
  52     /**
  53      * Add a synchronization formula between hostFrom and hostTo with a given
  54      * accuracy
  55      *
  56      * @param hostFrom
  57      *            Host from which the transform applies
  58      * @param hostTo
  59      *            Host to which the transform applies
  60      * @param transform
  61      *            The timestamp transform
  62      * @param accuracy
  63      *            The accuracy of the synchronization between hostFrom and
  64      *            hostTo
  65      */
  66     public void addSynchronization(String hostFrom, String hostTo, ITmfTimestampTransform transform, BigDecimal accuracy) {
  67         fHosts.add(hostFrom);
  68         fHosts.add(hostTo);
  69         fSyncGraph.addEdge(hostFrom, hostTo, transform);
  70         if (transform instanceof ITmfTimestampTransformInvertible) {
  71             fSyncGraph.addEdge(hostTo, hostFrom, ((ITmfTimestampTransformInvertible) transform).inverse());
  72         }
  73     }
  74
  75     /**
  76      * Get the timestamp transform to a host
  77      *
  78      * FIXME: This might not work in situations where we have disjoint graphs
  79      * since we only calculate 1 root node and each tree has its own root. When
  80      * implementing the algorithm with minimal spanning tree, we will solve this
  81      * problem.
  82      *
  83      * @param host
  84      *            The host to reach
  85      * @return The timestamp transform to host
  86      */
  87     public ITmfTimestampTransform getTimestampTransform(String host) {
  88         ITmfTimestampTransform result = TimestampTransformFactory.getDefaultTransform();
  89         String rootNode = getRootNode();
  90         /*
  91          * Compute the path from reference node to the given host id
  92          */
  93         if (rootNode != null) {
  94             List<Edge<String, ITmfTimestampTransform>> path = fSyncGraph.path(rootNode, host);
  95             /*
  96              * Compute the resulting transform by chaining each transforms on
  97              * the path.
  98              */
  99             for (Edge<String, ITmfTimestampTransform> edge : path) {
 100                 result = result.composeWith(edge.getLabel());
 101             }
 102         }
 103         return result;
 104     }
 105
 106     private String getRootNode() {
 107         /**
 108          * Get the root node from which all other paths will be calculated. For
 109          * now, we take the first node alphabetically.
 110          */
 111         if (fHosts.size() == 0) {
 112             return null;
 113         }
 114         return fHosts.first();
 115     }
 116
 117     /**
 118      * Check if this multi-host synchronization tree is connected, ie all nodes
 119      * have a synchronization path to a reference node.
 120      *
 121      * @return true if the tree is connected, false otherwise
 122      */
 123     public boolean isConnected() {
 124         return fSyncGraph.isConnected();
 125     }
 126
 127 }