0
# Mixed Graph Implementations
1

2
General-purpose graph implementations that support both directed and undirected edges within the same graph structure. These implementations provide maximum flexibility for modeling complex relationships that include both symmetric and asymmetric connections.
3

4
## Capabilities
5

6
### SparseGraph
7

8
Basic mixed graph implementation supporting both directed and undirected edges, suitable for sparse graphs.
9

10
```java { .api }
11
/**
12
 * An implementation of Graph that is suitable for sparse graphs and 
13
 * permits both directed and undirected edges.
14
 */
15
public class SparseGraph<V,E> extends AbstractGraph<V,E> implements Graph<V,E> {
16
    
17
    // Static constants for edge direction queries
18
    public static final int INCOMING = 0;
19
    public static final int OUTGOING = 1;
20
    public static final int INCIDENT = 2;
21
    
22
    /**
23
     * Creates an instance of SparseGraph
24
     */
25
    public SparseGraph();
26
    
27
    /**
28
     * Returns a Supplier that creates instances of this graph type
29
     * @return Factory supplier for SparseGraph instances
30
     */
31
    public static <V,E> Supplier<Graph<V,E>> getFactory();
32
    
33
    // Core graph operations
34
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
35
    public boolean addVertex(V vertex);
36
    public boolean removeVertex(V vertex);
37
    public boolean removeEdge(E edge);
38
    
39
    // Vertex and edge queries
40
    public Collection<E> getEdges();
41
    public Collection<V> getVertices();
42
    public boolean containsVertex(V vertex);
43
    public boolean containsEdge(E edge);
44
    public int getEdgeCount();
45
    public int getVertexCount();
46
    
47
    // Edge discovery and navigation
48
    public E findEdge(V v1, V v2);
49
    public Collection<E> findEdgeSet(V v1, V v2);
50
    public Pair<V> getEndpoints(E edge);
51
    
52
    // Edge type operations
53
    public Collection<E> getEdges(EdgeType edgeType);
54
    public EdgeType getEdgeType(E edge);
55
    public int getEdgeCount(EdgeType edge_type);
56
    public EdgeType getDefaultEdgeType(); // Returns EdgeType.UNDIRECTED
57
    
58
    // Directional queries (context-sensitive based on edge type)
59
    public Collection<E> getInEdges(V vertex);    // Directed in-edges + undirected edges
60
    public Collection<E> getOutEdges(V vertex);   // Directed out-edges + undirected edges
61
    public Collection<V> getPredecessors(V vertex);
62
    public Collection<V> getSuccessors(V vertex);
63
    public V getSource(E directed_edge);    // Returns source if directed, null if undirected
64
    public V getDest(E directed_edge);      // Returns dest if directed, null if undirected
65
    public boolean isSource(V vertex, E edge);
66
    public boolean isDest(V vertex, E edge);
67
    
68
    // Neighborhood operations
69
    public Collection<V> getNeighbors(V vertex);
70
    public Collection<E> getIncidentEdges(V vertex);
71
}
72
```
73

74
**Usage Examples:**
75

76
```java
77
import edu.uci.ics.jung.graph.SparseGraph;
78
import edu.uci.ics.jung.graph.Graph;
79
import edu.uci.ics.jung.graph.util.EdgeType;
80

81
// Create a mixed graph
82
Graph<String, String> mixedGraph = new SparseGraph<>();
83

84
// Add vertices
85
mixedGraph.addVertex("A");
86
mixedGraph.addVertex("B");
87
mixedGraph.addVertex("C");
88

89
// Add both directed and undirected edges
90
mixedGraph.addEdge("directed1", "A", "B", EdgeType.DIRECTED);    // A -> B
91
mixedGraph.addEdge("undirected1", "B", "C", EdgeType.UNDIRECTED); // B - C
92

93
// Query edge types
94
EdgeType type1 = mixedGraph.getEdgeType("directed1");   // EdgeType.DIRECTED
95
EdgeType type2 = mixedGraph.getEdgeType("undirected1"); // EdgeType.UNDIRECTED
96

97
// Get edges by type
98
Collection<String> directedEdges = mixedGraph.getEdges(EdgeType.DIRECTED);
99
Collection<String> undirectedEdges = mixedGraph.getEdges(EdgeType.UNDIRECTED);
100

101
// Directional queries are context-sensitive
102
String source = mixedGraph.getSource("directed1");   // "A"
103
String dest = mixedGraph.getDest("directed1");       // "B"
104
String sourceUndirected = mixedGraph.getSource("undirected1"); // null
105

106
// In/out edges include appropriate edge types
107
Collection<String> inEdgesB = mixedGraph.getInEdges("B");  
108
// ["directed1", "undirected1"] - directed in-edge + undirected edge
109

110
Collection<String> outEdgesB = mixedGraph.getOutEdges("B"); 
111
// ["undirected1"] - only undirected edge (no directed out-edges from B)
112
```
113

114
### SparseMultigraph
115

116
Mixed graph implementation that permits parallel edges and supports both directed and undirected edge types.
117

118
```java { .api }
119
/**
120
 * An implementation of Graph that is suitable for sparse graphs and 
121
 * permits directed, undirected, and parallel edges.
122
 */
123
public class SparseMultigraph<V,E> extends AbstractGraph<V,E> implements MultiGraph<V,E> {
124
    
125
    /**
126
     * Creates a new instance of SparseMultigraph
127
     */
128
    public SparseMultigraph();
129
    
130
    /**
131
     * Returns a Supplier that creates instances of this graph type
132
     * @return Factory supplier for SparseMultigraph instances
133
     */
134
    public static <V,E> Supplier<Graph<V,E>> getFactory();
135
    
136
    // Core graph operations
137
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
138
    public boolean addVertex(V vertex);
139
    public boolean removeVertex(V vertex);
140
    public boolean removeEdge(E edge);
141
    
142
    // Collection queries
143
    public Collection<E> getEdges();
144
    public Collection<V> getVertices();
145
    public boolean containsVertex(V vertex);
146
    public boolean containsEdge(E edge);
147
    public int getEdgeCount();
148
    public int getVertexCount();
149
    
150
    // Mixed graph operations
151
    public Collection<E> getInEdges(V vertex);
152
    public Collection<E> getOutEdges(V vertex);
153
    public Collection<V> getPredecessors(V vertex);
154
    public Collection<V> getSuccessors(V vertex);
155
    public Collection<V> getNeighbors(V vertex);
156
    public Collection<E> getIncidentEdges(V vertex);
157
    
158
    // Edge discovery and endpoints
159
    public E findEdge(V v1, V v2);
160
    public Pair<V> getEndpoints(E edge);
161
    
162
    // Directional information
163
    public V getSource(E edge);
164
    public V getDest(E edge);
165
    public boolean isSource(V vertex, E edge);
166
    public boolean isDest(V vertex, E edge);
167
    
168
    // Edge type operations
169
    public EdgeType getEdgeType(E edge);
170
    public Collection<E> getEdges(EdgeType edgeType);
171
    public int getEdgeCount(EdgeType edge_type);
172
    public EdgeType getDefaultEdgeType(); // Returns EdgeType.UNDIRECTED
173
}
174
```
175

176
**Usage Examples:**
177

178
```java
179
import edu.uci.ics.jung.graph.SparseMultigraph;
180
import edu.uci.ics.jung.graph.Graph;
181
import edu.uci.ics.jung.graph.util.EdgeType;
182

183
// Create a mixed multigraph
184
Graph<String, String> mixedMultigraph = new SparseMultigraph<>();
185

186
mixedMultigraph.addVertex("A");
187
mixedMultigraph.addVertex("B");
188

189
// Add parallel edges of different types
190
mixedMultigraph.addEdge("directed1", "A", "B", EdgeType.DIRECTED);
191
mixedMultigraph.addEdge("directed2", "A", "B", EdgeType.DIRECTED);
192
mixedMultigraph.addEdge("undirected1", "A", "B", EdgeType.UNDIRECTED);
193

194
// Query parallel edges
195
Collection<String> allEdges = mixedMultigraph.getIncidentEdges("A");
196
// ["directed1", "directed2", "undirected1"]
197

198
// Count edges by type
199
int directedCount = mixedMultigraph.getEdgeCount(EdgeType.DIRECTED);   // 2
200
int undirectedCount = mixedMultigraph.getEdgeCount(EdgeType.UNDIRECTED); // 1
201

202
// Get edges by type
203
Collection<String> directedEdges = mixedMultigraph.getEdges(EdgeType.DIRECTED);
204
// ["directed1", "directed2"]
205
```
206

207
### OrderedSparseMultigraph
208

209
Mixed multigraph that maintains insertion order for vertices and edges while supporting both edge types.
210

211
```java { .api }
212
/**
213
 * An implementation of Graph that orders its vertex and edge collections 
214
 * according to insertion time, is suitable for sparse graphs, and permits 
215
 * directed, undirected, and parallel edges.
216
 */
217
public class OrderedSparseMultigraph<V,E> extends SparseMultigraph<V,E> implements MultiGraph<V,E> {
218
    
219
    /**
220
     * Creates a new instance of OrderedSparseMultigraph
221
     */
222
    public OrderedSparseMultigraph();
223
    
224
    /**
225
     * Returns a Supplier that creates instances of this graph type
226
     * @return Factory supplier for OrderedSparseMultigraph instances
227
     */
228
    public static <V,E> Supplier<Graph<V,E>> getFactory();
229
    
230
    // Overridden methods that preserve insertion order
231
    public boolean addVertex(V vertex);
232
    public Collection<V> getPredecessors(V vertex);
233
    public Collection<V> getSuccessors(V vertex);
234
    public Collection<V> getNeighbors(V vertex);
235
    public Collection<E> getIncidentEdges(V vertex);
236
}
237
```
238

239
### SortedSparseMultigraph
240

241
Mixed multigraph that orders vertices and edges according to specified comparators or natural ordering.
242

243
```java { .api }
244
/**
245
 * An implementation of Graph suitable for sparse graphs, orders its vertex 
246
 * and edge collections according to specified Comparator instances or natural 
247
 * ordering, and permits directed, undirected, and parallel edges.
248
 */
249
public class SortedSparseMultigraph<V,E> extends OrderedSparseMultigraph<V,E> implements MultiGraph<V,E> {
250
    
251
    /**
252
     * Creates new instance with specified comparators
253
     * @param vertex_comparator Comparator for ordering vertices
254
     * @param edge_comparator Comparator for ordering edges
255
     */
256
    public SortedSparseMultigraph(Comparator<V> vertex_comparator, Comparator<E> edge_comparator);
257
    
258
    /**
259
     * Creates new instance that sorts according to natural ordering
260
     */
261
    public SortedSparseMultigraph();
262
    
263
    /**
264
     * Returns a Supplier that creates instances of this graph type
265
     * @return Factory supplier for SortedSparseMultigraph instances
266
     */
267
    public static <V,E> Supplier<Graph<V,E>> getFactory();
268
    
269
    /**
270
     * Provides new Comparator for sorting vertices
271
     * @param vertex_comparator New comparator for vertex ordering
272
     */
273
    public void setVertexComparator(Comparator<V> vertex_comparator);
274
    
275
    // Overridden method for sorted vertex addition
276
    public boolean addVertex(V vertex);
277
}
278
```
279

280
**Usage Examples:**
281

282
```java
283
import edu.uci.ics.jung.graph.SortedSparseMultigraph;
284
import java.util.Comparator;
285

286
// Create a sorted mixed multigraph
287
SortedSparseMultigraph<String, String> sortedGraph = 
288
    new SortedSparseMultigraph<>(
289
        String::compareTo,  // Natural string ordering for vertices
290
        String::compareTo   // Natural string ordering for edges
291
    );
292

293
// Add vertices - they will be sorted
294
sortedGraph.addVertex("Charlie");
295
sortedGraph.addVertex("Alice");
296
sortedGraph.addVertex("Bob");
297

298
// Vertices are returned in sorted order
299
Collection<String> vertices = sortedGraph.getVertices(); 
300
// Order: ["Alice", "Bob", "Charlie"]
301

302
// Change sorting criteria
303
sortedGraph.setVertexComparator(Comparator.reverseOrder());
304
// Future operations will use reverse ordering
305
```
306

307
## Edge Type Semantics
308

309
### Mixed Edge Behavior
310

311
In mixed graphs, edge behavior depends on the edge type:
312

313
```java
314
// Directed edges have source/destination
315
graph.addEdge("dir1", "A", "B", EdgeType.DIRECTED);
316
String source = graph.getSource("dir1");  // "A"
317
String dest = graph.getDest("dir1");      // "B"
318

319
// Undirected edges have no directional information
320
graph.addEdge("undir1", "A", "B", EdgeType.UNDIRECTED);
321
String sourceUndir = graph.getSource("undir1"); // null
322
String destUndir = graph.getDest("undir1");     // null
323
```
324

325
### Neighborhood Queries
326

327
Mixed graphs compute neighborhoods based on both edge types:
328

329
```java
330
// A -> B (directed), B - C (undirected)
331
Collection<String> successorsB = graph.getSuccessors("B");  // ["C"] (via undirected)
332
Collection<String> predecessorsB = graph.getPredecessors("B"); // ["A", "C"]
333
Collection<String> neighborsB = graph.getNeighbors("B");    // ["A", "C"]
334
```
335

336
## Performance Characteristics
337

338
### SparseGraph
339
- **Space Complexity**: O(V + E) with separate storage for directed/undirected edges
340
- **Edge Type Queries**: O(1) lookup with dedicated edge type storage
341
- **Mixed Operations**: Efficient handling of both edge types
342

343
### SparseMultigraph
344
- **Parallel Edge Support**: Set-based storage allows multiple edges of different types
345
- **Edge Type Filtering**: Efficient queries for edges of specific types
346

347
### OrderedSparseMultigraph
348
- **Insertion Order**: LinkedHashSet preserves addition order across mixed edge types
349
- **Ordering Consistency**: Maintains order for vertices and edges independently
350

351
### SortedSparseMultigraph
352
- **Custom Ordering**: TreeSet-based sorting with user-defined comparators
353
- **Dynamic Reordering**: Ability to change sorting criteria during graph lifetime
354

355
## Common Use Cases
356

357
### SparseGraph
358
- Social networks with both mutual (friendship) and directional (following) relationships
359
- Communication networks with bidirectional and unidirectional channels
360
- Workflow systems with both parallel and sequential dependencies
361

362
### SparseMultigraph
363
- Transportation networks with multiple connection types (road, rail, air)
364
- Communication systems with redundant directed and undirected links
365
- Biological networks with various interaction types
366

367
### OrderedSparseMultigraph
368
- Time-series networks where connection order represents temporal relationships
369
- Process flows combining sequential and parallel steps
370
- Social network evolution tracking
371

372
### SortedSparseMultigraph
373
- Hierarchical networks with custom vertex/edge ranking
374
- Priority-based routing systems, alphabetically organized social networks
375
- Any scenario requiring consistent ordering with mixed edge semantics