1 /*******************************************************************************
2 * Copyright (c) 2015 É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 * Francis Giraldeau - Initial implementation and API
11 * Geneviève Bastien - Initial implementation and API
12 *******************************************************************************/
14 package org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
;
16 import java
.util
.HashMap
;
17 import java
.util
.HashSet
;
18 import java
.util
.List
;
21 import java
.util
.Stack
;
22 import java
.util
.concurrent
.CountDownLatch
;
24 import org
.eclipse
.jdt
.annotation
.Nullable
;
25 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfEdge
.EdgeType
;
26 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfVertex
.EdgeDirection
;
27 import org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
;
28 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.ITmfTimestamp
;
30 import com
.google
.common
.collect
.ArrayListMultimap
;
31 import com
.google
.common
.collect
.ImmutableSet
;
32 import com
.google
.common
.collect
.ListMultimap
;
35 * Undirected, unweighed, timed graph data type for dependencies between
36 * elements of a system.
38 * Vertices are timed: each vertex has a timestamp associated, so the vertex
39 * belongs to an object (the key of the multimap) at a given time. This is why
40 * we use a ListMultimap to represent the graph, instead of a simple list.
42 * @author Francis Giraldeau
43 * @author Geneviève Bastien
45 public class TmfGraph
{
47 private final ListMultimap
<IGraphWorker
, TmfVertex
> fNodeMap
;
48 private final Map
<TmfVertex
, IGraphWorker
> fReverse
;
50 /* Latch tracking if the graph is done building or not */
51 private final CountDownLatch fFinishedLatch
= new CountDownLatch(1);
57 fNodeMap
= NonNullUtils
.checkNotNull(ArrayListMultimap
.create());
58 fReverse
= new HashMap
<>();
62 * Add node to the provided object without linking
65 * The key of the object the vertex belongs to
69 public void add(IGraphWorker worker
, TmfVertex vertex
) {
70 List
<TmfVertex
> list
= fNodeMap
.get(worker
);
72 fReverse
.put(vertex
, worker
);
76 * Add node to object's list and make horizontal link with tail.
79 * The key of the object the vertex belongs to
82 * @return The edge constructed
84 public @Nullable TmfEdge
append(IGraphWorker worker
, TmfVertex vertex
) {
85 return append(worker
, vertex
, EdgeType
.DEFAULT
);
89 * Add node to object's list and make horizontal link with tail.
92 * The key of the object the vertex belongs to
96 * The type of edge to create
97 * @return The edge constructed
99 public @Nullable TmfEdge
append(IGraphWorker worker
, TmfVertex vertex
, EdgeType type
) {
100 List
<TmfVertex
> list
= fNodeMap
.get(worker
);
101 TmfVertex tail
= getTail(worker
);
104 link
= tail
.linkHorizontal(vertex
);
108 fReverse
.put(vertex
, worker
);
113 * Add a link between two vertices of the graph. The from vertex must be in
114 * the graph. If the 'to' vertex is not in the graph, it will be appended to
115 * the object the 'from' vertex is for. Otherwise a vertical or horizontal
116 * link will be created between the vertices.
118 * Caution: this will remove without warning any previous link from the
124 * The destination vertex
125 * @return The newly created edge
127 public TmfEdge
link(TmfVertex from
, TmfVertex to
) {
128 return link(from
, to
, EdgeType
.DEFAULT
);
132 * Add a link between two vertices of the graph. The from vertex must be in
133 * the graph. If the 'to' vertex is not in the graph, it will be appended to
134 * the object the 'from' vertex is for. Otherwise a vertical or horizontal
135 * link will be created between the vertices.
137 * Caution: this will remove without warning any previous link from the
143 * The destination vertex
145 * The type of edge to create
146 * @return The newly created edge
148 public TmfEdge
link(TmfVertex from
, TmfVertex to
, EdgeType type
) {
149 IGraphWorker ofrom
= fReverse
.get(from
);
150 IGraphWorker oto
= fReverse
.get(to
);
152 throw new IllegalArgumentException(Messages
.TmfGraph_FromNotInGraph
);
155 /* to vertex not in the graph, add it to ofrom */
162 if (oto
.equals(ofrom
)) {
163 link
= from
.linkHorizontal(to
);
165 link
= from
.linkVertical(to
);
172 * Returns tail node of the provided object
175 * The key of the object the vertex belongs to
176 * @return The last vertex of obj
178 public @Nullable TmfVertex
getTail(IGraphWorker worker
) {
179 List
<TmfVertex
> list
= fNodeMap
.get(worker
);
180 if (!list
.isEmpty()) {
181 return list
.get(list
.size() - 1);
187 * Removes the last vertex of the provided object
190 * The key of the object the vertex belongs to
191 * @return The removed vertex
193 public @Nullable TmfVertex
removeTail(IGraphWorker worker
) {
194 List
<TmfVertex
> list
= fNodeMap
.get(worker
);
195 if (!list
.isEmpty()) {
196 TmfVertex last
= list
.remove(list
.size() - 1);
197 fReverse
.remove(last
);
204 * Returns head node of the provided object. This is the very first node of
208 * The key of the object the vertex belongs to
209 * @return The head vertex
211 public @Nullable TmfVertex
getHead(IGraphWorker worker
) {
212 IGraphWorker ref
= worker
;
213 List
<TmfVertex
> list
= fNodeMap
.get(ref
);
214 if (!list
.isEmpty()) {
221 * Returns the head node of the first object of the nodeMap
223 * @return The head vertex
225 public @Nullable TmfVertex
getHead() {
226 if (fNodeMap
.isEmpty()) {
229 return getHead(NonNullUtils
.checkNotNull(fNodeMap
.keySet().iterator().next()));
233 * Returns head vertex from a given node. That is the first of the current
234 * sequence of edges, the one with no left edge when going back through the
235 * original vertex's left edge
238 * The vertex for which to get the head
239 * @return The head vertex from the requested vertex
241 public TmfVertex
getHead(TmfVertex vertex
) {
242 TmfVertex headNode
= vertex
;
243 TmfEdge edge
= headNode
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
244 while (edge
!= null) {
245 headNode
= edge
.getVertexFrom();
246 if (headNode
== vertex
) {
247 throw new CycleDetectedException();
249 edge
= headNode
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
255 * Returns all nodes of the provided object.
258 * The key of the object the vertex belongs to
259 * @return The list of vertices for the object
261 public List
<TmfVertex
> getNodesOf(IGraphWorker obj
) {
262 return NonNullUtils
.checkNotNull(fNodeMap
.get(obj
));
266 * Returns the object the vertex belongs to
269 * The vertex to get the parent for
270 * @return The object the vertex belongs to
272 public @Nullable IGraphWorker
getParentOf(TmfVertex node
) {
273 return fReverse
.get(node
);
277 * Returns the graph objects
279 * @return The vertex map
281 public Set
<IGraphWorker
> getWorkers() {
282 return NonNullUtils
.checkNotNull(ImmutableSet
.copyOf(fNodeMap
.keySet()));
286 * Returns the number of vertices in the graph
288 * @return number of vertices
291 return fReverse
.size();
295 public String
toString() {
296 return NonNullUtils
.nullToEmptyString(String
.format("Graph { actors=%d, nodes=%d }", //$NON-NLS-1$
297 fNodeMap
.keySet().size(), fNodeMap
.values().size()));
301 * Dumps the full graph
303 * @return A string with the graph dump
305 public String
dump() {
306 StringBuilder str
= new StringBuilder();
307 for (IGraphWorker obj
: fNodeMap
.keySet()) {
308 str
.append(String
.format("%10s ", obj
)); //$NON-NLS-1$
309 str
.append(fNodeMap
.get(obj
));
310 str
.append("\n"); //$NON-NLS-1$
312 return NonNullUtils
.nullToEmptyString(str
.toString());
315 // ----------------------------------------------
316 // Graph operations and visits
317 // ----------------------------------------------
320 * Visits a graph from the start vertex and every vertex of the graph having
321 * a path to/from them that intersects the start vertex
323 * Each time the worker changes, it goes back to the beginning of the
324 * current horizontal sequence and visits all nodes from there.
326 * Parts of the graph that are totally disjoints from paths to/from start
327 * will not be visited by this method
330 * The vertex to start the scan for
334 public void scanLineTraverse(final @Nullable TmfVertex start
, final ITmfGraphVisitor visitor
) {
338 Stack
<TmfVertex
> stack
= new Stack
<>();
339 HashSet
<TmfVertex
> visited
= new HashSet
<>();
341 while (!stack
.isEmpty()) {
342 TmfVertex curr
= NonNullUtils
.checkNotNull(stack
.pop());
343 if (visited
.contains(curr
)) {
347 TmfVertex n
= getHead(curr
);
348 visitor
.visitHead(n
);
353 // Only visit links up-right, guarantee to visit once only
354 TmfEdge edge
= n
.getEdge(EdgeDirection
.OUTGOING_VERTICAL_EDGE
);
356 stack
.push(edge
.getVertexTo());
357 visitor
.visit(edge
, false);
359 edge
= n
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
);
361 stack
.push(edge
.getVertexFrom());
363 edge
= n
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
365 visitor
.visit(edge
, true);
366 n
= edge
.getVertexTo();
368 // end of the horizontal list
376 * @see TmfGraph#scanLineTraverse(TmfVertex, ITmfGraphVisitor)
379 * The worker from which to start the scan
383 public void scanLineTraverse(@Nullable IGraphWorker start
, final ITmfGraphVisitor visitor
) {
387 scanLineTraverse(getHead(start
), visitor
);
391 * Return the vertex for an object at a given timestamp, or the first vertex
392 * after the timestamp
397 * The object for which to get the vertex
398 * @return Vertex at timestamp or null if no vertex at or after timestamp
400 public @Nullable TmfVertex
getVertexAt(ITmfTimestamp startTime
, IGraphWorker worker
) {
401 List
<TmfVertex
> list
= fNodeMap
.get(worker
);
403 long ts
= startTime
.getValue();
404 // Scan the list until vertex is later than time
405 for (TmfVertex vertex
: list
) {
406 if (vertex
.getTs() >= ts
) {
414 * Returns whether the graph is completed or not
416 * @return whether the graph is done building
418 public boolean isDoneBuilding() {
419 return fFinishedLatch
.getCount() == 0;
423 * Countdown the latch to show that the graph is done building
425 public void closeGraph() {
426 fFinishedLatch
.countDown();