analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/base/TmfGraph.java

   1 /*******************************************************************************
   2  * Copyright (c) 2015 É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  *   Francis Giraldeau - Initial implementation and API
  11  *   Geneviève Bastien - Initial implementation and API
  12  *******************************************************************************/
  13
  14 package org.eclipse.tracecompass.analysis.graph.core.base;
  15
  16 import java.util.HashMap;
  17 import java.util.HashSet;
  18 import java.util.List;
  19 import java.util.Map;
  20 import java.util.Set;
  21 import java.util.Stack;
  22 import java.util.concurrent.CountDownLatch;
  23
  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;
  29
  30 import com.google.common.collect.ArrayListMultimap;
  31 import com.google.common.collect.ImmutableSet;
  32 import com.google.common.collect.ListMultimap;
  33
  34 /**
  35  * Undirected, unweighed, timed graph data type for dependencies between
  36  * elements of a system.
  37  *
  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.
  41  *
  42  * @author Francis Giraldeau
  43  * @author Geneviève Bastien
  44  */
  45 public class TmfGraph {
  46
  47     private final ListMultimap<IGraphWorker, TmfVertex> fNodeMap;
  48     private final Map<TmfVertex, IGraphWorker> fReverse;
  49
  50     /* Latch tracking if the graph is done building or not */
  51     private final CountDownLatch fFinishedLatch = new CountDownLatch(1);
  52
  53     /**
  54      * Constructor
  55      */
  56     public TmfGraph() {
  57         fNodeMap = NonNullUtils.checkNotNull(ArrayListMultimap.create());
  58         fReverse = new HashMap<>();
  59     }
  60
  61     /**
  62      * Add node to the provided object without linking
  63      *
  64      * @param worker
  65      *            The key of the object the vertex belongs to
  66      * @param vertex
  67      *            The new vertex
  68      */
  69     public void add(IGraphWorker worker, TmfVertex vertex) {
  70         List<TmfVertex> list = fNodeMap.get(worker);
  71         list.add(vertex);
  72         fReverse.put(vertex, worker);
  73     }
  74
  75     /**
  76      * Add node to object's list and make horizontal link with tail.
  77      *
  78      * @param worker
  79      *            The key of the object the vertex belongs to
  80      * @param vertex
  81      *            The new vertex
  82      * @return The edge constructed
  83      */
  84     public @Nullable TmfEdge append(IGraphWorker worker, TmfVertex vertex) {
  85         return append(worker, vertex, EdgeType.DEFAULT);
  86     }
  87
  88     /**
  89      * Add node to object's list and make horizontal link with tail.
  90      *
  91      * @param worker
  92      *            The key of the object the vertex belongs to
  93      * @param vertex
  94      *            The new vertex
  95      * @param type
  96      *            The type of edge to create
  97      * @return The edge constructed
  98      */
  99     public @Nullable TmfEdge append(IGraphWorker worker, TmfVertex vertex, EdgeType type) {
 100         List<TmfVertex> list = fNodeMap.get(worker);
 101         TmfVertex tail = getTail(worker);
 102         TmfEdge link = null;
 103         if (tail != null) {
 104             link = tail.linkHorizontal(vertex);
 105             link.setType(type);
 106         }
 107         list.add(vertex);
 108         fReverse.put(vertex, worker);
 109         return link;
 110     }
 111
 112     /**
 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.
 117      *
 118      * Caution: this will remove without warning any previous link from the
 119      * 'from' vertex
 120      *
 121      * @param from
 122      *            The source vertex
 123      * @param to
 124      *            The destination vertex
 125      * @return The newly created edge
 126      */
 127     public TmfEdge link(TmfVertex from, TmfVertex to) {
 128         return link(from, to, EdgeType.DEFAULT);
 129     }
 130
 131     /**
 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.
 136      *
 137      * Caution: this will remove without warning any previous link from the
 138      * 'from' vertex
 139      *
 140      * @param from
 141      *            The source vertex
 142      * @param to
 143      *            The destination vertex
 144      * @param type
 145      *            The type of edge to create
 146      * @return The newly created edge
 147      */
 148     public TmfEdge link(TmfVertex from, TmfVertex to, EdgeType type) {
 149         IGraphWorker ofrom = fReverse.get(from);
 150         IGraphWorker oto = fReverse.get(to);
 151         if (ofrom == null) {
 152             throw new IllegalArgumentException(Messages.TmfGraph_FromNotInGraph);
 153         }
 154
 155         /* to vertex not in the graph, add it to ofrom */
 156         if (oto == null) {
 157             this.add(ofrom, to);
 158             oto = ofrom;
 159         }
 160
 161         TmfEdge link;
 162         if (oto.equals(ofrom)) {
 163             link = from.linkHorizontal(to);
 164         } else {
 165             link = from.linkVertical(to);
 166         }
 167         link.setType(type);
 168         return link;
 169     }
 170
 171     /**
 172      * Returns tail node of the provided object
 173      *
 174      * @param worker
 175      *            The key of the object the vertex belongs to
 176      * @return The last vertex of obj
 177      */
 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);
 182         }
 183         return null;
 184     }
 185
 186     /**
 187      * Removes the last vertex of the provided object
 188      *
 189      * @param worker
 190      *            The key of the object the vertex belongs to
 191      * @return The removed vertex
 192      */
 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);
 198             return last;
 199         }
 200         return null;
 201     }
 202
 203     /**
 204      * Returns head node of the provided object. This is the very first node of
 205      * an object
 206      *
 207      * @param worker
 208      *            The key of the object the vertex belongs to
 209      * @return The head vertex
 210      */
 211     public @Nullable TmfVertex getHead(IGraphWorker worker) {
 212         IGraphWorker ref = worker;
 213         List<TmfVertex> list = fNodeMap.get(ref);
 214         if (!list.isEmpty()) {
 215             return list.get(0);
 216         }
 217         return null;
 218     }
 219
 220     /**
 221      * Returns the head node of the first object of the nodeMap
 222      *
 223      * @return The head vertex
 224      */
 225     public @Nullable TmfVertex getHead() {
 226         if (fNodeMap.isEmpty()) {
 227             return null;
 228         }
 229         return getHead(NonNullUtils.checkNotNull(fNodeMap.keySet().iterator().next()));
 230     }
 231
 232     /**
 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
 236      *
 237      * @param vertex
 238      *            The vertex for which to get the head
 239      * @return The head vertex from the requested vertex
 240      */
 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();
 248             }
 249             edge = headNode.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
 250         }
 251         return headNode;
 252     }
 253
 254     /**
 255      * Returns all nodes of the provided object.
 256      *
 257      * @param obj
 258      *            The key of the object the vertex belongs to
 259      * @return The list of vertices for the object
 260      */
 261     public List<TmfVertex> getNodesOf(IGraphWorker obj) {
 262         return NonNullUtils.checkNotNull(fNodeMap.get(obj));
 263     }
 264
 265     /**
 266      * Returns the object the vertex belongs to
 267      *
 268      * @param node
 269      *            The vertex to get the parent for
 270      * @return The object the vertex belongs to
 271      */
 272     public @Nullable IGraphWorker getParentOf(TmfVertex node) {
 273         return fReverse.get(node);
 274     }
 275
 276     /**
 277      * Returns the graph objects
 278      *
 279      * @return The vertex map
 280      */
 281     public Set<IGraphWorker> getWorkers() {
 282         return NonNullUtils.checkNotNull(ImmutableSet.copyOf(fNodeMap.keySet()));
 283     }
 284
 285     /**
 286      * Returns the number of vertices in the graph
 287      *
 288      * @return number of vertices
 289      */
 290     public int size() {
 291         return fReverse.size();
 292     }
 293
 294     @Override
 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()));
 298     }
 299
 300     /**
 301      * Dumps the full graph
 302      *
 303      * @return A string with the graph dump
 304      */
 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$
 311         }
 312         return NonNullUtils.nullToEmptyString(str.toString());
 313     }
 314
 315     // ----------------------------------------------
 316     // Graph operations and visits
 317     // ----------------------------------------------
 318
 319     /**
 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
 322      *
 323      * Each time the worker changes, it goes back to the beginning of the
 324      * current horizontal sequence and visits all nodes from there.
 325      *
 326      * Parts of the graph that are totally disjoints from paths to/from start
 327      * will not be visited by this method
 328      *
 329      * @param start
 330      *            The vertex to start the scan for
 331      * @param visitor
 332      *            The visitor
 333      */
 334     public void scanLineTraverse(final @Nullable TmfVertex start, final ITmfGraphVisitor visitor) {
 335         if (start == null) {
 336             return;
 337         }
 338         Stack<TmfVertex> stack = new Stack<>();
 339         HashSet<TmfVertex> visited = new HashSet<>();
 340         stack.add(start);
 341         while (!stack.isEmpty()) {
 342             TmfVertex curr = NonNullUtils.checkNotNull(stack.pop());
 343             if (visited.contains(curr)) {
 344                 continue;
 345             }
 346             // process one line
 347             TmfVertex n = getHead(curr);
 348             visitor.visitHead(n);
 349             while (true) {
 350                 visitor.visit(n);
 351                 visited.add(n);
 352
 353                 // Only visit links up-right, guarantee to visit once only
 354                 TmfEdge edge = n.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE);
 355                 if (edge != null) {
 356                     stack.push(edge.getVertexTo());
 357                     visitor.visit(edge, false);
 358                 }
 359                 edge = n.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
 360                 if (edge != null) {
 361                     stack.push(edge.getVertexFrom());
 362                 }
 363                 edge = n.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
 364                 if (edge != null) {
 365                     visitor.visit(edge, true);
 366                     n = edge.getVertexTo();
 367                 } else {
 368                     // end of the horizontal list
 369                     break;
 370                 }
 371             }
 372         }
 373     }
 374
 375     /**
 376      * @see TmfGraph#scanLineTraverse(TmfVertex, ITmfGraphVisitor)
 377      *
 378      * @param start
 379      *            The worker from which to start the scan
 380      * @param visitor
 381      *            The visitor
 382      */
 383     public void scanLineTraverse(@Nullable IGraphWorker start, final ITmfGraphVisitor visitor) {
 384         if (start == null) {
 385             return;
 386         }
 387         scanLineTraverse(getHead(start), visitor);
 388     }
 389
 390     /**
 391      * Return the vertex for an object at a given timestamp, or the first vertex
 392      * after the timestamp
 393      *
 394      * @param startTime
 395      *            The desired time
 396      * @param worker
 397      *            The object for which to get the vertex
 398      * @return Vertex at timestamp or null if no vertex at or after timestamp
 399      */
 400     public @Nullable TmfVertex getVertexAt(ITmfTimestamp startTime, IGraphWorker worker) {
 401         List<TmfVertex> list = fNodeMap.get(worker);
 402
 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) {
 407                 return vertex;
 408             }
 409         }
 410         return null;
 411     }
 412
 413     /**
 414      * Returns whether the graph is completed or not
 415      *
 416      * @return whether the graph is done building
 417      */
 418     public boolean isDoneBuilding() {
 419         return fFinishedLatch.getCount() == 0;
 420     }
 421
 422     /**
 423      * Countdown the latch to show that the graph is done building
 424      */
 425     public void closeGraph() {
 426         fFinishedLatch.countDown();
 427     }
 428
 429 }