| 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 | * Francis Giraldeau - Initial implementation and API |
| 11 | *******************************************************************************/ |
| 12 | |
| 13 | package org.eclipse.linuxtools.internal.tmf.core.synchronization.graph; |
| 14 | |
| 15 | import java.util.ArrayList; |
| 16 | import java.util.Collection; |
| 17 | import java.util.Collections; |
| 18 | import java.util.HashMap; |
| 19 | import java.util.HashSet; |
| 20 | import java.util.LinkedList; |
| 21 | import java.util.List; |
| 22 | import java.util.Queue; |
| 23 | import java.util.Set; |
| 24 | import java.util.Stack; |
| 25 | |
| 26 | import com.google.common.collect.ArrayListMultimap; |
| 27 | import com.google.common.collect.Multimap; |
| 28 | |
| 29 | /** |
| 30 | * Minimal graph implementation to compute timestamps transforms of a trace from |
| 31 | * a given synchronized set of traces. The graph is implemented as an adjacency |
| 32 | * list and is directed. To create undirected graph, add the edge in both |
| 33 | * directions. |
| 34 | * |
| 35 | * @author Francis Giraldeau <francis.giraldeau@gmail.com> |
| 36 | * @param <V> |
| 37 | * The vertices type |
| 38 | * @param <E> |
| 39 | * The edge annotation type |
| 40 | */ |
| 41 | public class SyncGraph<V, E> { |
| 42 | |
| 43 | private Multimap<V, Edge<V, E>> fAdjacentEdges; |
| 44 | private Set<V> fVertices; |
| 45 | |
| 46 | /** |
| 47 | * Construct empty graph |
| 48 | */ |
| 49 | public SyncGraph() { |
| 50 | fAdjacentEdges = ArrayListMultimap.create(); |
| 51 | fVertices = new HashSet<>(); |
| 52 | } |
| 53 | |
| 54 | /** |
| 55 | * Add edge from v to w and annotation label |
| 56 | * |
| 57 | * @param from |
| 58 | * from vertex |
| 59 | * @param to |
| 60 | * to vertex |
| 61 | * @param label |
| 62 | * the edge label |
| 63 | */ |
| 64 | public void addEdge(V from, V to, E label) { |
| 65 | fAdjacentEdges.put(from, new Edge<>(from, to, label)); |
| 66 | fVertices.add(from); |
| 67 | fVertices.add(to); |
| 68 | } |
| 69 | |
| 70 | /** |
| 71 | * Get the number of edges |
| 72 | * |
| 73 | * @return number of edges |
| 74 | */ |
| 75 | public int getNbEdges() { |
| 76 | return fAdjacentEdges.entries().size(); |
| 77 | } |
| 78 | |
| 79 | /** |
| 80 | * Get the number of vertices |
| 81 | * |
| 82 | * @return number of vertices |
| 83 | */ |
| 84 | public int getNbVertices() { |
| 85 | return fVertices.size(); |
| 86 | } |
| 87 | |
| 88 | /** |
| 89 | * Returns the adjacent edges of the given vertex |
| 90 | * |
| 91 | * @param v |
| 92 | * the vertex |
| 93 | * @return the adjacent vertices |
| 94 | */ |
| 95 | public Collection<Edge<V, E>> getAdjacentEdges(V v) { |
| 96 | return fAdjacentEdges.get(v); |
| 97 | } |
| 98 | |
| 99 | /** |
| 100 | * Returns a path between start and end vertices. |
| 101 | * |
| 102 | * @param start |
| 103 | * vertex |
| 104 | * @param end |
| 105 | * vertex |
| 106 | * @return the list of edges between start and end vertices |
| 107 | */ |
| 108 | public List<Edge<V, E>> path(V start, V end) { |
| 109 | ArrayList<Edge<V, E>> path = new ArrayList<>(); |
| 110 | HashMap<V, Edge<V, E>> hist = new HashMap<>(); |
| 111 | HashSet<V> visited = new HashSet<>(); |
| 112 | Queue<V> queue = new LinkedList<>(); |
| 113 | queue.offer(start); |
| 114 | /** |
| 115 | * Build the map of nodes reachable from the start node, by recursively |
| 116 | * visiting all accessible nodes. It is a breadth-first search, so the |
| 117 | * edges kept for each node will be the shortest path to that node. |
| 118 | */ |
| 119 | while (!queue.isEmpty()) { |
| 120 | V node = queue.poll(); |
| 121 | visited.add(node); |
| 122 | for (Edge<V, E> e : getAdjacentEdges(node)) { |
| 123 | V to = e.getTo(); |
| 124 | if (!visited.contains(to)) { |
| 125 | queue.offer(e.getTo()); |
| 126 | if (!hist.containsKey(e.getTo())) { |
| 127 | hist.put(e.getTo(), e); |
| 128 | } |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | /* |
| 133 | * Find path from start to end by traversing the edges backward, from |
| 134 | * the end node |
| 135 | */ |
| 136 | V node = end; |
| 137 | Edge<V, E> edge = hist.get(node); |
| 138 | while (edge != null && node != start) { |
| 139 | path.add(edge); |
| 140 | node = edge.getFrom(); |
| 141 | edge = hist.get(node); |
| 142 | } |
| 143 | Collections.reverse(path); |
| 144 | return path; |
| 145 | } |
| 146 | |
| 147 | /** |
| 148 | * Check if this graph is connected, ie there are no partitions, all |
| 149 | * vertices are reachable from every other one. It is a depth-first visit of |
| 150 | * all vertices reachable from the first vertex of the graph. |
| 151 | * |
| 152 | * @return true if the graph is connected, false otherwise |
| 153 | */ |
| 154 | public boolean isConnected() { |
| 155 | HashSet<V> visited = new HashSet<>(); |
| 156 | Stack<V> stack = new Stack<>(); |
| 157 | stack.push(fVertices.iterator().next()); |
| 158 | while (!stack.isEmpty()) { |
| 159 | V node = stack.pop(); |
| 160 | visited.add(node); |
| 161 | for (Edge<V, E> edge : getAdjacentEdges(node)) { |
| 162 | if (!visited.contains(edge.getTo())) { |
| 163 | stack.push(edge.getTo()); |
| 164 | } |
| 165 | } |
| 166 | } |
| 167 | return visited.size() == fVertices.size(); |
| 168 | } |
| 169 | |
| 170 | @Override |
| 171 | public String toString() { |
| 172 | StringBuilder str = new StringBuilder(); |
| 173 | for (V key : fAdjacentEdges.keySet()) { |
| 174 | str.append(key + ": " + fAdjacentEdges.get(key) + "\n"); //$NON-NLS-1$ //$NON-NLS-2$ |
| 175 | } |
| 176 | return str.toString(); |
| 177 | } |
| 178 | |
| 179 | } |