0
# Undirected Graph Implementations
1
2
Graph implementations for symmetric relationships where edges connect vertices without directional preference. All connections are bidirectional, making these implementations ideal for modeling symmetric relationships like friendships, physical connections, or mutual associations.
3
4
## Capabilities
5
6
### UndirectedSparseGraph
7
8
Basic undirected graph implementation suitable for sparse graphs, where all edges represent bidirectional connections.
9
10
```java { .api }
11
/**
12
* An implementation of UndirectedGraph that is suitable for sparse graphs.
13
* Does not permit parallel edges.
14
*/
15
public class UndirectedSparseGraph<V,E> extends AbstractTypedGraph<V,E> implements UndirectedGraph<V,E> {
16
17
/**
18
* Creates an instance of UndirectedSparseGraph
19
*/
20
public UndirectedSparseGraph();
21
22
/**
23
* Returns a Supplier that creates instances of this graph type
24
* @return Factory supplier for UndirectedSparseGraph instances
25
*/
26
public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
27
28
// Core graph operations
29
public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
30
public boolean addVertex(V vertex);
31
public boolean removeVertex(V vertex);
32
public boolean removeEdge(E edge);
33
34
// Vertex and edge queries
35
public Collection<E> getEdges();
36
public Collection<V> getVertices();
37
public boolean containsVertex(V vertex);
38
public boolean containsEdge(E edge);
39
public int getEdgeCount();
40
public int getVertexCount();
41
42
// Edge discovery and navigation
43
public E findEdge(V v1, V v2);
44
public Collection<E> findEdgeSet(V v1, V v2);
45
public Pair<V> getEndpoints(E edge);
46
47
// Undirected graph operations (in/out edges are equivalent)
48
public Collection<E> getInEdges(V vertex); // Same as getIncidentEdges
49
public Collection<E> getOutEdges(V vertex); // Same as getIncidentEdges
50
public Collection<V> getPredecessors(V vertex); // Same as getNeighbors
51
public Collection<V> getSuccessors(V vertex); // Same as getNeighbors
52
53
// Direction queries (always return null/false for undirected graphs)
54
public V getSource(E directed_edge); // Returns null
55
public V getDest(E directed_edge); // Returns null
56
public boolean isSource(V vertex, E edge); // Returns false
57
public boolean isDest(V vertex, E edge); // Returns false
58
59
// Neighborhood operations
60
public Collection<V> getNeighbors(V vertex);
61
public Collection<E> getIncidentEdges(V vertex);
62
}
63
```
64
65
**Usage Examples:**
66
67
```java
68
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
69
import edu.uci.ics.jung.graph.UndirectedGraph;
70
71
// Create an undirected graph
72
UndirectedGraph<String, String> graph = new UndirectedSparseGraph<>();
73
74
// Add vertices
75
graph.addVertex("A");
76
graph.addVertex("B");
77
graph.addVertex("C");
78
79
// Add undirected edges (A-B, B-C)
80
graph.addEdge("edge1", "A", "B");
81
graph.addEdge("edge2", "B", "C");
82
83
// All relationships are symmetric
84
Collection<String> neighborsA = graph.getNeighbors("A"); // ["B"]
85
Collection<String> neighborsB = graph.getNeighbors("B"); // ["A", "C"]
86
87
// Predecessors and successors are identical in undirected graphs
88
Collection<String> predecessors = graph.getPredecessors("B"); // ["A", "C"]
89
Collection<String> successors = graph.getSuccessors("B"); // ["A", "C"]
90
91
// No directional information available
92
String source = graph.getSource("edge1"); // null
93
String dest = graph.getDest("edge1"); // null
94
95
// In/out edges are the same as incident edges
96
Collection<String> inEdges = graph.getInEdges("B"); // ["edge1", "edge2"]
97
Collection<String> outEdges = graph.getOutEdges("B"); // ["edge1", "edge2"]
98
Collection<String> incidentEdges = graph.getIncidentEdges("B"); // ["edge1", "edge2"]
99
```
100
101
### UndirectedSparseMultigraph
102
103
Undirected graph implementation that permits parallel edges (multiple edges between the same vertex pair).
104
105
```java { .api }
106
/**
107
* An implementation of UndirectedGraph that is suitable for sparse graphs
108
* and permits parallel edges.
109
*/
110
public class UndirectedSparseMultigraph<V,E> extends AbstractTypedGraph<V,E>
111
implements UndirectedGraph<V,E>, MultiGraph<V,E> {
112
113
/**
114
* Creates a new instance of UndirectedSparseMultigraph
115
*/
116
public UndirectedSparseMultigraph();
117
118
/**
119
* Returns a Supplier that creates instances of this graph type
120
* @return Factory supplier for UndirectedSparseMultigraph instances
121
*/
122
public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
123
124
// Core graph operations
125
public boolean addEdge(E edge, V v1, V v2, EdgeType edgeType);
126
public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edge_type);
127
public boolean addVertex(V vertex);
128
public boolean removeVertex(V vertex);
129
public boolean removeEdge(E edge);
130
131
// Collection queries
132
public Collection<E> getEdges();
133
public Collection<V> getVertices();
134
public boolean containsVertex(V vertex);
135
public boolean containsEdge(E edge);
136
public int getEdgeCount();
137
public int getVertexCount();
138
139
// Undirected graph operations
140
public Collection<E> getInEdges(V vertex); // Same as getIncidentEdges
141
public Collection<E> getOutEdges(V vertex); // Same as getIncidentEdges
142
public Collection<V> getPredecessors(V vertex); // Same as getNeighbors
143
public Collection<V> getSuccessors(V vertex); // Same as getNeighbors
144
public Collection<V> getNeighbors(V vertex);
145
public Collection<E> getIncidentEdges(V vertex);
146
147
// Edge finding and endpoints
148
public E findEdge(V v1, V v2);
149
public Pair<V> getEndpoints(E edge);
150
151
// Direction queries (no directional information in undirected graphs)
152
public V getDest(E directed_edge); // Returns null
153
public V getSource(E directed_edge); // Returns null
154
public boolean isDest(V vertex, E edge); // Returns false
155
public boolean isSource(V vertex, E edge); // Returns false
156
}
157
```
158
159
**Usage Examples:**
160
161
```java
162
import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;
163
import edu.uci.ics.jung.graph.UndirectedGraph;
164
165
// Create an undirected multigraph
166
UndirectedGraph<String, String> multigraph = new UndirectedSparseMultigraph<>();
167
168
multigraph.addVertex("A");
169
multigraph.addVertex("B");
170
171
// Add multiple edges between same vertices (parallel edges)
172
multigraph.addEdge("edge1", "A", "B");
173
multigraph.addEdge("edge2", "A", "B"); // Second edge A-B
174
multigraph.addEdge("edge3", "A", "B"); // Third edge A-B
175
176
// Query parallel edges
177
Collection<String> incidentEdges = multigraph.getIncidentEdges("A");
178
// ["edge1", "edge2", "edge3"]
179
180
Collection<String> neighbors = multigraph.getNeighbors("A"); // ["B"]
181
int edgeCount = multigraph.getEdgeCount(); // 3
182
183
// findEdge returns one of the parallel edges (implementation dependent)
184
String someEdge = multigraph.findEdge("A", "B"); // "edge1", "edge2", or "edge3"
185
```
186
187
### UndirectedOrderedSparseMultigraph
188
189
Undirected multigraph that maintains insertion order for vertices and edges.
190
191
```java { .api }
192
/**
193
* An implementation of UndirectedGraph that is suitable for sparse graphs,
194
* orders its vertex and edge collections according to insertion time,
195
* and permits parallel edges.
196
*/
197
public class UndirectedOrderedSparseMultigraph<V,E> extends UndirectedSparseMultigraph<V,E>
198
implements UndirectedGraph<V,E> {
199
200
/**
201
* Creates a new instance of UndirectedOrderedSparseMultigraph
202
*/
203
public UndirectedOrderedSparseMultigraph();
204
205
/**
206
* Returns a Supplier that creates instances of this graph type
207
* @return Factory supplier for UndirectedOrderedSparseMultigraph instances
208
*/
209
public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
210
211
// Overridden methods that preserve insertion order
212
public boolean addVertex(V vertex);
213
public Collection<V> getNeighbors(V vertex);
214
}
215
```
216
217
**Usage Examples:**
218
219
```java
220
import edu.uci.ics.jung.graph.UndirectedOrderedSparseMultigraph;
221
import edu.uci.ics.jung.graph.UndirectedGraph;
222
223
// Create an ordered undirected multigraph
224
UndirectedGraph<String, String> orderedGraph = new UndirectedOrderedSparseMultigraph<>();
225
226
// Add vertices - order is preserved
227
orderedGraph.addVertex("First");
228
orderedGraph.addVertex("Second");
229
orderedGraph.addVertex("Third");
230
231
orderedGraph.addEdge("edge1", "First", "Second");
232
orderedGraph.addEdge("edge2", "First", "Third");
233
orderedGraph.addEdge("edge3", "Second", "Third");
234
235
// Collections maintain insertion order
236
Collection<String> vertices = orderedGraph.getVertices();
237
// Order: ["First", "Second", "Third"]
238
239
Collection<String> neighbors = orderedGraph.getNeighbors("First");
240
// Order: ["Second", "Third"] (insertion order preserved)
241
```
242
243
## Key Differences from Directed Graphs
244
245
### Symmetric Relationships
246
247
In undirected graphs, all relationships are bidirectional:
248
- If vertex A is connected to vertex B, then B is also connected to A
249
- `getNeighbors()`, `getPredecessors()`, and `getSuccessors()` return identical results
250
- `getInEdges()`, `getOutEdges()`, and `getIncidentEdges()` return identical results
251
252
### No Directional Information
253
254
Undirected graphs have no concept of edge direction:
255
- `getSource()` and `getDest()` always return `null`
256
- `isSource()` and `isDest()` always return `false`
257
- Edge endpoints are unordered pairs
258
259
### Edge Semantics
260
261
```java
262
// In directed graphs:
263
directedGraph.addEdge("edge", "A", "B"); // A -> B (A is source, B is destination)
264
265
// In undirected graphs:
266
undirectedGraph.addEdge("edge", "A", "B"); // A - B (no direction, mutual connection)
267
```
268
269
## Performance Characteristics
270
271
### UndirectedSparseGraph
272
- **Space Complexity**: O(V + E) - optimal for sparse graphs
273
- **Edge Addition**: O(1) average case
274
- **Vertex Removal**: O(degree(v))
275
- **Edge Lookup**: O(1) average case
276
- **Neighbor Queries**: O(degree(v))
277
278
### UndirectedSparseMultigraph
279
- **Parallel Edge Support**: Efficient storage of multiple edges between vertices
280
- **Space Complexity**: O(V + E) with set-based edge storage
281
282
### UndirectedOrderedSparseMultigraph
283
- **Ordering Guarantee**: LinkedHashSet ensures insertion order preservation
284
- **Memory Overhead**: Slightly higher than unordered variants
285
286
## Common Use Cases
287
288
### UndirectedSparseGraph
289
- Social networks (friendships, connections), computer networks, molecular structures
290
- Collaboration networks, transportation infrastructure, communication networks
291
292
### UndirectedSparseMultigraph
293
- Transportation networks with multiple routes between locations
294
- Communication networks with redundant connections, weighted edges represented as parallel edges
295
296
### UndirectedOrderedSparseMultigraph
297
- Networks where connection order matters, temporal analysis of relationship formation
298
- Ordered traversals, maintaining historical context of connections