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 | * 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 | } |