0
# Directed Graph Implementations
1

2
Specialized graph implementations for directed relationships where edges have a defined source vertex and destination vertex. These implementations are optimized for sparse graphs and provide efficient directed graph operations including predecessor/successor queries and directional traversals.
3

4
## Capabilities
5

6
### DirectedSparseGraph
7

8
Basic directed graph implementation suitable for sparse graphs (few edges relative to possible edges).
9

10
```java { .api }
11
/**
12
 * An implementation of DirectedGraph suitable for sparse graphs.
13
 * Does not permit parallel edges.
14
 */
15
public class DirectedSparseGraph<V,E> extends AbstractTypedGraph<V,E> implements DirectedGraph<V,E> {
16
    
17
    /**
18
     * Creates an instance of DirectedSparseGraph
19
     */
20
    public DirectedSparseGraph();
21
    
22
    /**
23
     * Returns a Supplier that creates instances of this graph type
24
     * @return Factory supplier for DirectedSparseGraph instances
25
     */
26
    public static <V,E> Supplier<DirectedGraph<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
    // Directed graph specific operations
48
    public Collection<E> getInEdges(V vertex);
49
    public Collection<E> getOutEdges(V vertex);
50
    public Collection<V> getPredecessors(V vertex);
51
    public Collection<V> getSuccessors(V vertex);
52
    public V getSource(E directed_edge);
53
    public V getDest(E directed_edge);
54
    public boolean isSource(V vertex, E edge);
55
    public boolean isDest(V vertex, E edge);
56
    
57
    // Neighborhood operations
58
    public Collection<V> getNeighbors(V vertex);
59
    public Collection<E> getIncidentEdges(V vertex);
60
}
61
```
62

63
**Usage Examples:**
64

65
```java
66
import edu.uci.ics.jung.graph.DirectedSparseGraph;
67
import edu.uci.ics.jung.graph.DirectedGraph;
68

69
// Create a directed graph
70
DirectedGraph<String, String> graph = new DirectedSparseGraph<>();
71

72
// Add vertices
73
graph.addVertex("A");
74
graph.addVertex("B");
75
graph.addVertex("C");
76

77
// Add directed edges (A->B, B->C)
78
graph.addEdge("edge1", "A", "B");
79
graph.addEdge("edge2", "B", "C");
80

81
// Query directed relationships
82
Collection<String> successors = graph.getSuccessors("A"); // ["B"]
83
Collection<String> predecessors = graph.getPredecessors("B"); // ["A"]
84

85
// Edge direction queries
86
String source = graph.getSource("edge1"); // "A"
87
String dest = graph.getDest("edge1");     // "B"
88
boolean isSource = graph.isSource("A", "edge1"); // true
89

90
// Directed edge collections
91
Collection<String> outEdges = graph.getOutEdges("A"); // ["edge1"]
92
Collection<String> inEdges = graph.getInEdges("B");   // ["edge1"]
93
```
94

95
### DirectedSparseMultigraph
96

97
Directed graph implementation that permits parallel edges (multiple edges between the same vertex pair).
98

99
```java { .api }
100
/**
101
 * An implementation of DirectedGraph suitable for sparse graphs that permits parallel edges.
102
 */
103
public class DirectedSparseMultigraph<V,E> extends AbstractTypedGraph<V,E> 
104
    implements DirectedGraph<V,E>, MultiGraph<V,E> {
105
    
106
    /**
107
     * Creates a new instance of DirectedSparseMultigraph
108
     */
109
    public DirectedSparseMultigraph();
110
    
111
    /**
112
     * Returns a Supplier that creates instances of this graph type
113
     * @return Factory supplier for DirectedSparseMultigraph instances
114
     */
115
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
116
    
117
    // Core graph operations (same interface as DirectedSparseGraph)
118
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
119
    public boolean addVertex(V vertex);
120
    public boolean removeVertex(V vertex);
121
    public boolean removeEdge(E edge);
122
    
123
    // Collection queries
124
    public Collection<E> getEdges();
125
    public Collection<V> getVertices();
126
    public boolean containsVertex(V vertex);
127
    public boolean containsEdge(E edge);
128
    public int getEdgeCount();
129
    public int getVertexCount();
130
    
131
    // Directed graph operations
132
    public Collection<E> getInEdges(V vertex);
133
    public Collection<E> getOutEdges(V vertex);
134
    public Collection<V> getPredecessors(V vertex);
135
    public Collection<V> getSuccessors(V vertex);
136
    public V getSource(E edge);
137
    public V getDest(E edge);
138
    public boolean isSource(V vertex, E edge);
139
    public boolean isDest(V vertex, E edge);
140
    public Pair<V> getEndpoints(E edge);
141
    
142
    // Edge finding (may return any of multiple parallel edges)
143
    public E findEdge(V v1, V v2);
144
    
145
    // Neighborhood operations
146
    public Collection<V> getNeighbors(V vertex);
147
    public Collection<E> getIncidentEdges(V vertex);
148
}
149
```
150

151
**Usage Examples:**
152

153
```java
154
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
155
import edu.uci.ics.jung.graph.DirectedGraph;
156

157
// Create a directed multigraph
158
DirectedGraph<String, String> multigraph = new DirectedSparseMultigraph<>();
159

160
multigraph.addVertex("A");
161
multigraph.addVertex("B");
162

163
// Add multiple edges between same vertices (parallel edges)
164
multigraph.addEdge("edge1", "A", "B");
165
multigraph.addEdge("edge2", "A", "B");  // Second edge A->B
166
multigraph.addEdge("edge3", "A", "B");  // Third edge A->B
167

168
// Query parallel edges
169
Collection<String> outEdges = multigraph.getOutEdges("A"); // ["edge1", "edge2", "edge3"]
170
int edgeCount = multigraph.getEdgeCount(); // 3
171

172
// findEdge returns one of the parallel edges (implementation dependent)
173
String someEdge = multigraph.findEdge("A", "B"); // "edge1", "edge2", or "edge3"
174
```
175

176
### DirectedOrderedSparseMultigraph
177

178
Directed multigraph that maintains insertion order for vertices and edges, useful when the order of addition is semantically important.
179

180
```java { .api }
181
/**
182
 * An implementation of DirectedGraph suitable for sparse graphs that orders 
183
 * its vertex and edge collections according to insertion time and permits parallel edges.
184
 */
185
public class DirectedOrderedSparseMultigraph<V,E> extends DirectedSparseMultigraph<V,E> 
186
    implements DirectedGraph<V,E>, MultiGraph<V,E> {
187
    
188
    /**
189
     * Creates a new instance of DirectedOrderedSparseMultigraph
190
     */
191
    public DirectedOrderedSparseMultigraph();
192
    
193
    /**
194
     * Returns a Supplier that creates instances of this graph type
195
     * @return Factory supplier for DirectedOrderedSparseMultigraph instances
196
     */
197
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
198
    
199
    // Overridden methods that preserve insertion order
200
    public boolean addVertex(V vertex);
201
    public Collection<V> getPredecessors(V vertex);
202
    public Collection<V> getSuccessors(V vertex);
203
    public Collection<V> getNeighbors(V vertex);
204
    public Collection<E> getIncidentEdges(V vertex);
205
}
206
```
207

208
**Usage Examples:**
209

210
```java
211
import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph;
212
import edu.uci.ics.jung.graph.DirectedGraph;
213

214
// Create an ordered directed multigraph
215
DirectedGraph<String, String> orderedGraph = new DirectedOrderedSparseMultigraph<>();
216

217
// Add vertices - order is preserved
218
orderedGraph.addVertex("First");
219
orderedGraph.addVertex("Second");
220
orderedGraph.addVertex("Third");
221

222
orderedGraph.addEdge("edge1", "First", "Second");
223
orderedGraph.addEdge("edge2", "First", "Third");
224
orderedGraph.addEdge("edge3", "Second", "Third");
225

226
// Collections maintain insertion order
227
Collection<String> vertices = orderedGraph.getVertices(); 
228
// Order: ["First", "Second", "Third"]
229

230
Collection<String> successors = orderedGraph.getSuccessors("First");
231
// Order: ["Second", "Third"] (insertion order preserved)
232
```
233

234
## Performance Characteristics
235

236
### DirectedSparseGraph
237
- **Space Complexity**: O(V + E) - optimal for sparse graphs
238
- **Edge Addition**: O(1) average case
239
- **Vertex Removal**: O(degree(v))
240
- **Edge Lookup**: O(1) average case
241
- **Neighbor Queries**: O(degree(v))
242

243
### DirectedSparseMultigraph
244
- **Space Complexity**: O(V + E) - supports multiple edges efficiently
245
- **Parallel Edge Support**: Uses sets to store multiple edges between vertices
246
- **Edge Lookup**: O(1) for existence, returns arbitrary parallel edge
247

248
### DirectedOrderedSparseMultigraph
249
- **Ordering Overhead**: Uses LinkedHashSet for order preservation
250
- **Insertion Order**: Guaranteed preservation across all collection operations
251
- **Memory Overhead**: Slightly higher than unordered variants
252

253
## Common Use Cases
254

255
### DirectedSparseGraph
256
- Dependency graphs, workflow modeling, social network following relationships
257
- Network routing, finite state machines, citation networks
258

259
### DirectedSparseMultigraph
260
- Transportation networks with multiple routes, communication networks with redundant connections
261
- Biological networks with multiple interaction types
262

263
### DirectedOrderedSparseMultigraph
264
- Process flows where step order matters, hierarchical structures
265
- Timeline-based networks, ordered dependency chains