1 /*******************************************************************************
2 * Copyright (c) 2014 É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 *******************************************************************************/
13 package org
.eclipse
.linuxtools
.internal
.tmf
.core
.synchronization
.graph
;
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
;
24 import java
.util
.Stack
;
26 import com
.google
.common
.collect
.ArrayListMultimap
;
27 import com
.google
.common
.collect
.Multimap
;
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
35 * @author Francis Giraldeau <francis.giraldeau@gmail.com>
39 * The edge annotation type
41 public class SyncGraph
<V
, E
> {
43 private Multimap
<V
, Edge
<V
, E
>> fAdjacentEdges
;
44 private Set
<V
> fVertices
;
47 * Construct empty graph
50 fAdjacentEdges
= ArrayListMultimap
.create();
51 fVertices
= new HashSet
<>();
55 * Add edge from v to w and annotation label
64 public void addEdge(V from
, V to
, E label
) {
65 fAdjacentEdges
.put(from
, new Edge
<>(from
, to
, label
));
71 * Get the number of edges
73 * @return number of edges
75 public int getNbEdges() {
76 return fAdjacentEdges
.entries().size();
80 * Get the number of vertices
82 * @return number of vertices
84 public int getNbVertices() {
85 return fVertices
.size();
89 * Returns the adjacent edges of the given vertex
93 * @return the adjacent vertices
95 public Collection
<Edge
<V
, E
>> getAdjacentEdges(V v
) {
96 return fAdjacentEdges
.get(v
);
100 * Returns a path between start and end vertices.
106 * @return the list of edges between start and end vertices
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
<>();
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.
119 while (!queue
.isEmpty()) {
120 V node
= queue
.poll();
122 for (Edge
<V
, E
> e
: getAdjacentEdges(node
)) {
124 if (!visited
.contains(to
)) {
125 queue
.offer(e
.getTo());
126 if (!hist
.containsKey(e
.getTo())) {
127 hist
.put(e
.getTo(), e
);
133 * Find path from start to end by traversing the edges backward, from
137 Edge
<V
, E
> edge
= hist
.get(node
);
138 while (edge
!= null && node
!= start
) {
140 node
= edge
.getFrom();
141 edge
= hist
.get(node
);
143 Collections
.reverse(path
);
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.
152 * @return true if the graph is connected, false otherwise
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();
161 for (Edge
<V
, E
> edge
: getAdjacentEdges(node
)) {
162 if (!visited
.contains(edge
.getTo())) {
163 stack
.push(edge
.getTo());
167 return visited
.size() == fVertices
.size();
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$
176 return str
.toString();
This page took 0.043448 seconds and 5 git commands to generate.