forked from lingeringsocket/jgrapht
-
Notifications
You must be signed in to change notification settings - Fork 820
/
FastLookupDirectedSpecifics.java
179 lines (162 loc) · 5.82 KB
/
FastLookupDirectedSpecifics.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
/*
* (C) Copyright 2015-2023, by Joris Kinable and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* See the CONTRIBUTORS.md file distributed with this work for additional
* information regarding copyright ownership.
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License 2.0 which is available at
* http://www.eclipse.org/legal/epl-2.0, or the
* GNU Lesser General Public License v2.1 or later
* which is available at
* http://www.gnu.org/licenses/old-licenses/lgpl-2.1-standalone.html.
*
* SPDX-License-Identifier: EPL-2.0 OR LGPL-2.1-or-later
*/
package org.jgrapht.graph.specifics;
import org.jgrapht.*;
import org.jgrapht.alg.util.*;
import org.jgrapht.graph.*;
import java.util.*;
import java.util.function.*;
/**
* Fast implementation of DirectedSpecifics. This class uses additional data structures to improve
* the performance of methods which depend on edge retrievals, e.g. getEdge(V u, V v),
* containsEdge(V u, V v),addEdge(V u, V v). A disadvantage is an increase in memory consumption. If
* memory utilization is an issue, use a {@link DirectedSpecifics} instead.
*
* @param <V> the graph vertex type
* @param <E> the graph edge type
*
* @author Joris Kinable
*/
public class FastLookupDirectedSpecifics<V, E>
extends DirectedSpecifics<V, E>
{
private static final long serialVersionUID = 4089085208843722263L;
/**
* Maps a pair of vertices <u,v> to a set of edges {(u,v)}. In case of a multigraph, all
* edges which touch both u and v are included in the set.
*/
protected Map<Pair<V, V>, Set<E>> touchingVerticesToEdgeMap;
/**
* Construct a new fast lookup directed specifics.
*
* @param graph the graph for which these specifics are for
* @param vertexMap map for the storage of vertex edge sets. Needs to have a predictable
* iteration order.
* @param touchingVerticesToEdgeMap Additional map for caching. No need for a predictable
* iteration order.
* @param edgeSetFactory factory for the creation of vertex edge sets
*/
public FastLookupDirectedSpecifics(
Graph<V, E> graph, Map<V, DirectedEdgeContainer<V, E>> vertexMap,
Map<Pair<V, V>, Set<E>> touchingVerticesToEdgeMap, EdgeSetFactory<V, E> edgeSetFactory)
{
super(graph, vertexMap, edgeSetFactory);
this.touchingVerticesToEdgeMap = Objects.requireNonNull(touchingVerticesToEdgeMap);
}
@Override
public Set<E> getAllEdges(V sourceVertex, V targetVertex)
{
if (graph.containsVertex(sourceVertex) && graph.containsVertex(targetVertex)) {
Set<E> edges = touchingVerticesToEdgeMap.get(new Pair<>(sourceVertex, targetVertex));
if (edges == null) {
return Collections.emptySet();
} else {
Set<E> edgeSet = edgeSetFactory.createEdgeSet(sourceVertex);
edgeSet.addAll(edges);
return edgeSet;
}
} else {
return null;
}
}
@Override
public E getEdge(V sourceVertex, V targetVertex)
{
Set<E> edges = touchingVerticesToEdgeMap.get(new Pair<>(sourceVertex, targetVertex));
if (edges == null || edges.isEmpty())
return null;
else {
return edges.iterator().next();
}
}
@Override
public boolean addEdgeToTouchingVertices(V sourceVertex, V targetVertex, E e)
{
if (!super.addEdgeToTouchingVertices(sourceVertex, targetVertex, e)) {
return false;
}
addToIndex(sourceVertex, targetVertex, e);
return true;
}
@Override
public boolean addEdgeToTouchingVerticesIfAbsent(V sourceVertex, V targetVertex, E e)
{
// first lookup using our own index
E edge = getEdge(sourceVertex, targetVertex);
if (edge != null) {
return false;
}
return addEdgeToTouchingVertices(sourceVertex, targetVertex, e);
}
@Override
public E createEdgeToTouchingVerticesIfAbsent(
V sourceVertex, V targetVertex, Supplier<E> edgeSupplier)
{
// first lookup using our own index
E edge = getEdge(sourceVertex, targetVertex);
if (edge != null) {
return null;
}
E e = edgeSupplier.get();
addEdgeToTouchingVertices(sourceVertex, targetVertex, e);
return e;
}
@Override
public void removeEdgeFromTouchingVertices(V sourceVertex, V targetVertex, E e)
{
super.removeEdgeFromTouchingVertices(sourceVertex, targetVertex, e);
removeFromIndex(sourceVertex, targetVertex, e);
}
/**
* Add an edge to the index.
*
* @param sourceVertex the source vertex
* @param targetVertex the target vertex
* @param e the edge
*/
protected void addToIndex(V sourceVertex, V targetVertex, E e)
{
Pair<V, V> vertexPair = new Pair<>(sourceVertex, targetVertex);
Set<E> edgeSet = touchingVerticesToEdgeMap.get(vertexPair);
if (edgeSet != null)
edgeSet.add(e);
else {
edgeSet = edgeSetFactory.createEdgeSet(sourceVertex);
edgeSet.add(e);
touchingVerticesToEdgeMap.put(vertexPair, edgeSet);
}
}
/**
* Remove an edge from the index.
*
* @param sourceVertex the source vertex
* @param targetVertex the target vertex
* @param e the edge
*/
protected void removeFromIndex(V sourceVertex, V targetVertex, E e)
{
Pair<V, V> vertexPair = new Pair<>(sourceVertex, targetVertex);
Set<E> edgeSet = touchingVerticesToEdgeMap.get(vertexPair);
if (edgeSet != null) {
edgeSet.remove(e);
if (edgeSet.isEmpty()) {
touchingVerticesToEdgeMap.remove(vertexPair);
}
}
}
}