1 /*******************************************************************************
2 * Copyright (c) 2014 École Polytechnique de Montréal
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
10 * Geneviève Bastien - Initial implementation and API
11 *******************************************************************************/
13 package org
.eclipse
.linuxtools
.internal
.tmf
.core
.synchronization
.graph
;
15 import java
.math
.BigDecimal
;
16 import java
.util
.List
;
17 import java
.util
.SortedSet
;
18 import java
.util
.TreeSet
;
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
;
25 * Implements a tree to calculate the synchronization between hosts
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
33 * @author Geneviève Bastien
35 public class SyncSpanningTree
{
37 private final SyncGraph
<String
, ITmfTimestampTransform
> fSyncGraph
;
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.
43 private SortedSet
<String
> fHosts
= new TreeSet
<>();
48 public SyncSpanningTree() {
49 fSyncGraph
= new SyncGraph
<>();
53 * Add a synchronization formula between hostFrom and hostTo with a given
57 * Host from which the transform applies
59 * Host to which the transform applies
61 * The timestamp transform
63 * The accuracy of the synchronization between hostFrom and
66 public void addSynchronization(String hostFrom
, String hostTo
, ITmfTimestampTransform transform
, BigDecimal accuracy
) {
69 fSyncGraph
.addEdge(hostFrom
, hostTo
, transform
);
70 if (transform
instanceof ITmfTimestampTransformInvertible
) {
71 fSyncGraph
.addEdge(hostTo
, hostFrom
, ((ITmfTimestampTransformInvertible
) transform
).inverse());
76 * Get the timestamp transform to a host
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
85 * @return The timestamp transform to host
87 public ITmfTimestampTransform
getTimestampTransform(String host
) {
88 ITmfTimestampTransform result
= TimestampTransformFactory
.getDefaultTransform();
89 String rootNode
= getRootNode();
91 * Compute the path from reference node to the given host id
93 if (rootNode
!= null) {
94 List
<Edge
<String
, ITmfTimestampTransform
>> path
= fSyncGraph
.path(rootNode
, host
);
96 * Compute the resulting transform by chaining each transforms on
99 for (Edge
<String
, ITmfTimestampTransform
> edge
: path
) {
100 result
= result
.composeWith(edge
.getLabel());
106 private String
getRootNode() {
108 * Get the root node from which all other paths will be calculated. For
109 * now, we take the first node alphabetically.
111 if (fHosts
.size() == 0) {
114 return fHosts
.first();
118 * Check if this multi-host synchronization tree is connected, ie all nodes
119 * have a synchronization path to a reference node.
121 * @return true if the tree is connected, false otherwise
123 public boolean isConnected() {
124 return fSyncGraph
.isConnected();