Commit | Line | Data |
---|---|---|
ac29c59b FG |
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 | } |