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 object of the nodeMap that has the earliest
 222      * head vertex time
 223      *
 224      * @return The head vertex
 225      */
 226     public @Nullable TmfVertex getHead() {
 227         if (fNodeMap.isEmpty()) {
 228             return null;
 229         }
 230         IGraphWorker headWorker = fNodeMap.keySet().stream()
 231                 .filter(k -> !fNodeMap.get(k).isEmpty())
 232                 .sorted((k1, k2) -> fNodeMap.get(k1).get(0).compareTo(fNodeMap.get(k2).get(0)))
 233                 .findFirst()
 234                 .get();
 235         return getHead(headWorker);
 236     }
 237
 238     /**
 239      * Returns head vertex from a given node. That is the first of the current
 240      * sequence of edges, the one with no left edge when going back through the
 241      * original vertex's left edge
 242      *
 243      * @param vertex
 244      *            The vertex for which to get the head
 245      * @return The head vertex from the requested vertex
 246      */
 247     public TmfVertex getHead(TmfVertex vertex) {
 248         TmfVertex headNode = vertex;
 249         TmfEdge edge = headNode.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
 250         while (edge != null) {
 251             headNode = edge.getVertexFrom();
 252             if (headNode == vertex) {
 253                 throw new CycleDetectedException();
 254             }
 255             edge = headNode.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
 256         }
 257         return headNode;
 258     }
 259
 260     /**
 261      * Returns all nodes of the provided object.
 262      *
 263      * @param obj
 264      *            The key of the object the vertex belongs to
 265      * @return The list of vertices for the object
 266      */
 267     public List<TmfVertex> getNodesOf(IGraphWorker obj) {
 268         return fNodeMap.get(obj);
 269     }
 270
 271     /**
 272      * Returns the object the vertex belongs to
 273      *
 274      * @param node
 275      *            The vertex to get the parent for
 276      * @return The object the vertex belongs to
 277      */
 278     public @Nullable IGraphWorker getParentOf(TmfVertex node) {
 279         return fReverse.get(node);
 280     }
 281
 282     /**
 283      * Returns the graph objects
 284      *
 285      * @return The vertex map
 286      */
 287     public Set<IGraphWorker> getWorkers() {
 288         return ImmutableSet.copyOf(fNodeMap.keySet());
 289     }
 290
 291     /**
 292      * Returns the number of vertices in the graph
 293      *
 294      * @return number of vertices
 295      */
 296     public int size() {
 297         return fReverse.size();
 298     }
 299
 300     @Override
 301     public String toString() {
 302         return NonNullUtils.nullToEmptyString(String.format("Graph { actors=%d, nodes=%d }", //$NON-NLS-1$
 303                 fNodeMap.keySet().size(), fNodeMap.values().size()));
 304     }
 305
 306     /**
 307      * Dumps the full graph
 308      *
 309      * @return A string with the graph dump
 310      */
 311     public String dump() {
 312         StringBuilder str = new StringBuilder();
 313         for (IGraphWorker obj : fNodeMap.keySet()) {
 314             str.append(String.format("%10s ", obj)); //$NON-NLS-1$
 315             str.append(fNodeMap.get(obj));
 316             str.append("\n"); //$NON-NLS-1$
 317         }
 318         return NonNullUtils.nullToEmptyString(str.toString());
 319     }
 320
 321     // ----------------------------------------------
 322     // Graph operations and visits
 323     // ----------------------------------------------
 324
 325     /**
 326      * Visits a graph from the start vertex and every vertex of the graph having
 327      * a path to/from them that intersects the start vertex
 328      *
 329      * Each time the worker changes, it goes back to the beginning of the
 330      * current horizontal sequence and visits all nodes from there.
 331      *
 332      * Parts of the graph that are totally disjoints from paths to/from start
 333      * will not be visited by this method
 334      *
 335      * @param start
 336      *            The vertex to start the scan for
 337      * @param visitor
 338      *            The visitor
 339      */
 340     public void scanLineTraverse(final @Nullable TmfVertex start, final ITmfGraphVisitor visitor) {
 341         if (start == null) {
 342             return;
 343         }
 344         Stack<TmfVertex> stack = new Stack<>();
 345         HashSet<TmfVertex> visited = new HashSet<>();
 346         stack.add(start);
 347         while (!stack.isEmpty()) {
 348             TmfVertex curr = stack.pop();
 349             if (visited.contains(curr)) {
 350                 continue;
 351             }
 352             // process one line
 353             TmfVertex n = getHead(curr);
 354             visitor.visitHead(n);
 355             while (true) {
 356                 visitor.visit(n);
 357                 visited.add(n);
 358
 359                 // Only visit links up-right, guarantee to visit once only
 360                 TmfEdge edge = n.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE);
 361                 if (edge != null) {
 362                     stack.push(edge.getVertexTo());
 363                     visitor.visit(edge, false);
 364                 }
 365                 edge = n.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
 366                 if (edge != null) {
 367                     stack.push(edge.getVertexFrom());
 368                 }
 369                 edge = n.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
 370                 if (edge != null) {
 371                     visitor.visit(edge, true);
 372                     n = edge.getVertexTo();
 373                 } else {
 374                     // end of the horizontal list
 375                     break;
 376                 }
 377             }
 378         }
 379     }
 380
 381     /**
 382      * @see TmfGraph#scanLineTraverse(TmfVertex, ITmfGraphVisitor)
 383      *
 384      * @param start
 385      *            The worker from which to start the scan
 386      * @param visitor
 387      *            The visitor
 388      */
 389     public void scanLineTraverse(@Nullable IGraphWorker start, final ITmfGraphVisitor visitor) {
 390         if (start == null) {
 391             return;
 392         }
 393         scanLineTraverse(getHead(start), visitor);
 394     }
 395
 396     /**
 397      * Return the vertex for an object at a given timestamp, or the first vertex
 398      * after the timestamp
 399      *
 400      * @param startTime
 401      *            The desired time
 402      * @param worker
 403      *            The object for which to get the vertex
 404      * @return Vertex at timestamp or null if no vertex at or after timestamp
 405      */
 406     public @Nullable TmfVertex getVertexAt(ITmfTimestamp startTime, IGraphWorker worker) {
 407         List<TmfVertex> list = fNodeMap.get(worker);
 408
 409         long ts = startTime.getValue();
 410         // Scan the list until vertex is later than time
 411         for (TmfVertex vertex : list) {
 412             if (vertex.getTs() >= ts) {
 413                 return vertex;
 414             }
 415         }
 416         return null;
 417     }
 418
 419     /**
 420      * Returns whether the graph is completed or not
 421      *
 422      * @return whether the graph is done building
 423      */
 424     public boolean isDoneBuilding() {
 425         return fFinishedLatch.getCount() == 0;
 426     }
 427
 428     /**
 429      * Countdown the latch to show that the graph is done building
 430      */
 431     public void closeGraph() {
 432         fFinishedLatch.countDown();
 433     }
 434
 435 }