0
# Specialized Graph Types
1
2
Advanced graph implementations for specific use cases including hypergraphs (where edges can connect multiple vertices simultaneously) and ordered graph structures with custom sorting capabilities.
3
4
## Capabilities
5
6
### SetHypergraph
7
8
Hypergraph implementation where edges (hyperedges) can connect any number of vertices simultaneously, suitable for modeling complex multi-way relationships.
9
10
```java { .api }
11
/**
12
* An implementation of Hypergraph that is suitable for sparse graphs and permits parallel edges.
13
* Hyperedges can connect multiple vertices (not just pairs).
14
*/
15
public class SetHypergraph<V,H> implements Hypergraph<V,H>, MultiGraph<V,H>, Serializable {
16
17
/**
18
* Creates a SetHypergraph and initializes the internal data structures
19
*/
20
public SetHypergraph();
21
22
/**
23
* Returns a Factory which creates instances of this hypergraph type
24
* @return Factory supplier for SetHypergraph instances
25
*/
26
public static <V,H> Supplier<Hypergraph<V,H>> getFactory();
27
28
// Hypergraph-specific edge addition
29
public boolean addEdge(H hyperedge, Collection<? extends V> to_attach);
30
public boolean addEdge(H hyperedge, Collection<? extends V> to_attach, EdgeType edge_type);
31
32
// Core graph operations
33
public boolean addVertex(V vertex);
34
public boolean removeVertex(V vertex);
35
public boolean removeEdge(H hyperedge);
36
37
// Vertex and edge queries
38
public Collection<H> getEdges();
39
public Collection<V> getVertices();
40
public boolean containsVertex(V vertex);
41
public boolean containsEdge(H edge);
42
public int getEdgeCount();
43
public int getVertexCount();
44
45
// Hypergraph navigation
46
public Collection<V> getNeighbors(V vertex); // All vertices connected via hyperedges
47
public Collection<H> getIncidentEdges(V vertex); // All hyperedges containing vertex
48
public Collection<V> getIncidentVertices(H edge); // All vertices in hyperedge
49
50
// Edge finding between vertices
51
public H findEdge(V v1, V v2);
52
public Collection<H> findEdgeSet(V v1, V v2);
53
54
// Relationship queries
55
public boolean isNeighbor(V v1, V v2);
56
public boolean isIncident(V vertex, H edge);
57
public int degree(V vertex);
58
public int getNeighborCount(V vertex);
59
public int getIncidentCount(H edge); // Number of vertices in hyperedge
60
61
// Edge type operations (hypergraphs are always undirected)
62
public EdgeType getEdgeType(H edge); // Always EdgeType.UNDIRECTED
63
public int getEdgeCount(EdgeType edge_type);
64
public Collection<H> getEdges(EdgeType edge_type);
65
public EdgeType getDefaultEdgeType(); // Returns EdgeType.UNDIRECTED
66
67
// Directed graph interface (not applicable to hypergraphs)
68
public Collection<H> getInEdges(V vertex); // Same as getIncidentEdges
69
public Collection<H> getOutEdges(V vertex); // Same as getIncidentEdges
70
public int inDegree(V vertex); // Same as degree
71
public int outDegree(V vertex); // Same as degree
72
public V getDest(H directed_edge); // Always returns null
73
public V getSource(H directed_edge); // Always returns null
74
public Collection<V> getPredecessors(V vertex); // Same as getNeighbors
75
public Collection<V> getSuccessors(V vertex); // Same as getNeighbors
76
}
77
```
78
79
**Usage Examples:**
80
81
```java
82
import edu.uci.ics.jung.graph.SetHypergraph;
83
import edu.uci.ics.jung.graph.Hypergraph;
84
import java.util.Arrays;
85
86
// Create a hypergraph
87
Hypergraph<String, String> hypergraph = new SetHypergraph<>();
88
89
// Add vertices
90
hypergraph.addVertex("A");
91
hypergraph.addVertex("B");
92
hypergraph.addVertex("C");
93
hypergraph.addVertex("D");
94
95
// Add hyperedges connecting multiple vertices
96
hypergraph.addEdge("hyperedge1", Arrays.asList("A", "B", "C")); // 3-way connection
97
hypergraph.addEdge("hyperedge2", Arrays.asList("B", "C", "D")); // Another 3-way
98
hypergraph.addEdge("hyperedge3", Arrays.asList("A", "D")); // Standard edge (2-way)
99
100
// Query hyperedge contents
101
Collection<String> vertices1 = hypergraph.getIncidentVertices("hyperedge1"); // ["A", "B", "C"]
102
int edgeSize = hypergraph.getIncidentCount("hyperedge1"); // 3
103
104
// Query vertex connections
105
Collection<String> incidentEdges = hypergraph.getIncidentEdges("B"); // ["hyperedge1", "hyperedge2"]
106
Collection<String> neighbors = hypergraph.getNeighbors("B"); // ["A", "C", "D"]
107
108
// Vertex degree in hypergraph context
109
int degree = hypergraph.degree("B"); // Number of hyperedges containing B: 2
110
111
// Find hyperedges between vertices
112
String edge = hypergraph.findEdge("A", "B"); // Returns one of: "hyperedge1"
113
Collection<String> edges = hypergraph.findEdgeSet("A", "B"); // All edges containing both A and B
114
```
115
116
### OrderedSparseMultigraph
117
118
Mixed multigraph that maintains insertion order for vertices and edges, extending SparseMultigraph with ordering capabilities.
119
120
```java { .api }
121
/**
122
* An implementation of Graph that orders its vertex and edge collections
123
* according to insertion time, is suitable for sparse graphs, and permits
124
* directed, undirected, and parallel edges.
125
*/
126
public class OrderedSparseMultigraph<V,E> extends SparseMultigraph<V,E> implements MultiGraph<V,E> {
127
128
/**
129
* Creates a new instance of OrderedSparseMultigraph
130
*/
131
public OrderedSparseMultigraph();
132
133
/**
134
* Returns a Supplier that creates instances of this graph type
135
* @return Factory supplier for OrderedSparseMultigraph instances
136
*/
137
public static <V,E> Supplier<Graph<V,E>> getFactory();
138
139
// Overridden methods that preserve insertion order
140
public boolean addVertex(V vertex);
141
public Collection<V> getPredecessors(V vertex);
142
public Collection<V> getSuccessors(V vertex);
143
public Collection<V> getNeighbors(V vertex);
144
public Collection<E> getIncidentEdges(V vertex);
145
}
146
```
147
148
### SortedSparseMultigraph
149
150
Mixed multigraph that orders vertices and edges according to specified comparators or natural ordering, providing deterministic ordering based on element properties.
151
152
```java { .api }
153
/**
154
* An implementation of Graph suitable for sparse graphs, orders its vertex
155
* and edge collections according to specified Comparator instances or natural
156
* ordering, and permits directed, undirected, and parallel edges.
157
*/
158
public class SortedSparseMultigraph<V,E> extends OrderedSparseMultigraph<V,E> implements MultiGraph<V,E> {
159
160
/**
161
* Creates new instance with specified comparators
162
* @param vertex_comparator Comparator for ordering vertices
163
* @param edge_comparator Comparator for ordering edges
164
*/
165
public SortedSparseMultigraph(Comparator<V> vertex_comparator, Comparator<E> edge_comparator);
166
167
/**
168
* Creates new instance that sorts according to natural ordering
169
*/
170
public SortedSparseMultigraph();
171
172
/**
173
* Returns a Supplier that creates instances of this graph type
174
* @return Factory supplier for SortedSparseMultigraph instances
175
*/
176
public static <V,E> Supplier<Graph<V,E>> getFactory();
177
178
/**
179
* Provides new Comparator for sorting vertices
180
* @param vertex_comparator New comparator for vertex ordering
181
*/
182
public void setVertexComparator(Comparator<V> vertex_comparator);
183
184
// Overridden method for sorted vertex addition
185
public boolean addVertex(V vertex);
186
187
// Protected fields for custom ordering
188
protected Comparator<V> vertex_comparator;
189
protected Comparator<E> edge_comparator;
190
}
191
```
192
193
**Usage Examples:**
194
195
```java
196
import edu.uci.ics.jung.graph.SortedSparseMultigraph;
197
import java.util.Comparator;
198
199
// Create sorted graph with custom comparators
200
SortedSparseMultigraph<String, String> sortedGraph = new SortedSparseMultigraph<>(
201
String::compareTo, // Natural string ordering for vertices
202
Comparator.comparing(String::length) // Sort edges by length
203
);
204
205
// Add vertices - automatically sorted
206
sortedGraph.addVertex("Zebra");
207
sortedGraph.addVertex("Apple");
208
sortedGraph.addVertex("Banana");
209
210
// Vertices returned in sorted order
211
Collection<String> vertices = sortedGraph.getVertices(); // ["Apple", "Banana", "Zebra"]
212
213
// Add edges with different lengths - sorted by length
214
sortedGraph.addEdge("a", "Apple", "Banana"); // Length 1
215
sortedGraph.addEdge("medium", "Banana", "Zebra"); // Length 6
216
sortedGraph.addEdge("short", "Apple", "Zebra"); // Length 5
217
218
// Edges returned sorted by length
219
Collection<String> edges = sortedGraph.getEdges(); // ["a", "short", "medium"]
220
221
// Change vertex sorting dynamically
222
sortedGraph.setVertexComparator(Comparator.reverseOrder());
223
// Future vertex operations will use reverse ordering
224
```
225
226
## Specialized Ordering Implementations
227
228
### DirectedOrderedSparseMultigraph
229
230
Directed multigraph with insertion order preservation, extending DirectedSparseMultigraph.
231
232
```java { .api }
233
/**
234
* An implementation of DirectedGraph suitable for sparse graphs that orders
235
* its vertex and edge collections according to insertion time and permits parallel edges.
236
*/
237
public class DirectedOrderedSparseMultigraph<V,E> extends DirectedSparseMultigraph<V,E>
238
implements DirectedGraph<V,E>, MultiGraph<V,E> {
239
240
public DirectedOrderedSparseMultigraph();
241
public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
242
243
// Insertion order preserved methods
244
public boolean addVertex(V vertex);
245
public Collection<V> getPredecessors(V vertex);
246
public Collection<V> getSuccessors(V vertex);
247
public Collection<V> getNeighbors(V vertex);
248
public Collection<E> getIncidentEdges(V vertex);
249
}
250
```
251
252
### UndirectedOrderedSparseMultigraph
253
254
Undirected multigraph with insertion order preservation, extending UndirectedSparseMultigraph.
255
256
```java { .api }
257
/**
258
* An implementation of UndirectedGraph suitable for sparse graphs that orders
259
* its vertex and edge collections according to insertion time and permits parallel edges.
260
*/
261
public class UndirectedOrderedSparseMultigraph<V,E> extends UndirectedSparseMultigraph<V,E>
262
implements UndirectedGraph<V,E> {
263
264
public UndirectedOrderedSparseMultigraph();
265
public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
266
267
// Insertion order preserved methods
268
public boolean addVertex(V vertex);
269
public Collection<V> getNeighbors(V vertex);
270
}
271
```
272
273
## Hypergraph Concepts
274
275
### Multi-way Relationships
276
277
Unlike traditional graphs where edges connect exactly two vertices, hypergraphs allow edges to connect any number of vertices:
278
279
```java
280
// Traditional graph: edge connects 2 vertices
281
graph.addEdge("edge1", "A", "B");
282
283
// Hypergraph: hyperedge connects multiple vertices
284
hypergraph.addEdge("hyperedge1", Arrays.asList("A", "B", "C", "D"));
285
```
286
287
### Hypergraph Neighborhoods
288
289
In hypergraphs, vertices are neighbors if they share at least one hyperedge:
290
291
```java
292
// Hyperedge connects A, B, C
293
hypergraph.addEdge("hedge1", Arrays.asList("A", "B", "C"));
294
// Hyperedge connects B, D, E
295
hypergraph.addEdge("hedge2", Arrays.asList("B", "D", "E"));
296
297
Collection<String> neighborsB = hypergraph.getNeighbors("B"); // ["A", "C", "D", "E"]
298
```
299
300
### Hypergraph vs. Traditional Graph Operations
301
302
| Operation | Traditional Graph | Hypergraph |
303
|-----------|------------------|------------|
304
| Edge connects | Exactly 2 vertices | Any number of vertices |
305
| Neighborhood | Direct connections | Shared hyperedge membership |
306
| Edge finding | Between 2 vertices | Containing all specified vertices |
307
| Directionality | Can be directed/undirected | Always undirected |
308
309
## Performance Characteristics
310
311
### SetHypergraph
312
- **Space Complexity**: O(V + H + I) where H = hyperedges, I = total incidences
313
- **Hyperedge Addition**: O(k) where k = number of vertices in hyperedge
314
- **Neighborhood Queries**: O(degree(v) × average_hyperedge_size)
315
- **Incidence Queries**: O(1) for vertex-in-hyperedge tests
316
317
### Ordered Implementations
318
- **Insertion Order**: LinkedHashSet provides O(1) insertion with order preservation
319
- **Memory Overhead**: Additional storage for maintaining insertion order
320
- **Deterministic Iteration**: Guaranteed consistent ordering across operations
321
322
### Sorted Implementations
323
- **Custom Ordering**: TreeSet provides O(log n) insertion with custom comparators
324
- **Dynamic Reordering**: Ability to change sorting criteria during graph lifetime
325
- **Comparison Overhead**: Performance depends on comparator complexity
326
327
## Common Use Cases
328
329
### SetHypergraph
330
- **Biological Networks**: Protein complexes, metabolic pathways, gene regulatory networks
331
- **Social Networks**: Group memberships, multi-party collaborations, committee structures
332
- **Database Systems**: Multi-table joins, composite relationships, constraint modeling
333
- **Transportation**: Multi-modal routes, transfer stations, logistics networks
334
335
### Ordered Graphs
336
- **Timeline Analysis**: Preserving temporal order of connections
337
- **Process Modeling**: Maintaining step sequences in workflows
338
- **Historical Networks**: Tracking evolution of relationships over time
339
340
### Sorted Graphs
341
- **Hierarchical Systems**: Priority-based networks, organizational structures
342
- **Alphabetical Organization**: Lexicographic ordering for user interfaces
343
- **Weight-based Sorting**: Networks ordered by connection strength or cost
344
- **Custom Metrics**: Any scenario requiring domain-specific ordering