0
# JUNG Graph Implementation
1

2
JUNG (Java Universal Network/Graph Framework) Graph Implementation provides concrete data structure implementations for graph modeling, analysis, and visualization. This module offers high-performance sparse graph implementations including directed graphs, undirected graphs, multigraphs, trees, hypergraphs, and specialized ordered variants optimized for network analysis and scientific computing applications.
3

4
## Package Information
5

6
- **Package Name**: jung-graph-impl
7
- **Package Type**: Maven
8
- **Language**: Java
9
- **Installation**: 
10
  ```xml
11
  <dependency>
12
    <groupId>net.sf.jung</groupId>
13
    <artifactId>jung-graph-impl</artifactId>
14
    <version>2.1.1</version>
15
  </dependency>
16
  ```
17

18
## Core Imports
19

20
```java
21
import edu.uci.ics.jung.graph.*;
22
```
23

24
Common specific imports:
25
```java
26
import edu.uci.ics.jung.graph.DirectedSparseGraph;
27
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
28
import edu.uci.ics.jung.graph.SparseMultigraph;
29
import edu.uci.ics.jung.graph.SortedSparseMultigraph;
30
import edu.uci.ics.jung.graph.DelegateTree;
31
import edu.uci.ics.jung.graph.SetHypergraph;
32
import java.util.Comparator;
33
```
34

35
## Basic Usage
36

37
```java
38
import edu.uci.ics.jung.graph.DirectedSparseGraph;
39
import edu.uci.ics.jung.graph.Graph;
40

41
// Create a directed graph
42
Graph<String, String> directedGraph = new DirectedSparseGraph<>();
43

44
// Add vertices
45
directedGraph.addVertex("A");
46
directedGraph.addVertex("B");
47
directedGraph.addVertex("C");
48

49
// Add edges
50
directedGraph.addEdge("edge1", "A", "B");
51
directedGraph.addEdge("edge2", "B", "C");
52

53
// Query the graph
54
System.out.println("Vertices: " + directedGraph.getVertices());
55
System.out.println("Edges: " + directedGraph.getEdges());
56
System.out.println("Neighbors of B: " + directedGraph.getNeighbors("B"));
57
System.out.println("Successors of A: " + directedGraph.getSuccessors("A"));
58
```
59

60
## Architecture
61

62
JUNG Graph Implementation is organized around several key architectural patterns:
63

64
- **Abstract Base Classes**: `AbstractGraph` and `AbstractTypedGraph` provide common functionality and enforce consistent interfaces across implementations
65
- **Graph Type Specialization**: Separate implementations for directed, undirected, and mixed edge type graphs
66
- **Sparse Graph Optimization**: All implementations are optimized for sparse graphs (few edges relative to possible edges)
67
- **Parallel Edge Support**: Multigraph variants support multiple edges between the same vertex pair
68
- **Ordering Preservation**: Ordered variants maintain insertion order for vertices and edges
69
- **Tree Structures**: Specialized tree implementations with parent-child relationships and hierarchical operations
70
- **Hypergraph Support**: Implementation for edges connecting multiple vertices simultaneously
71
- **Factory Pattern**: Static factory methods provide consistent object creation across implementations
72

73
## Capabilities
74

75
### Abstract Base Classes
76

77
Foundation classes that provide common graph functionality and establish consistent interfaces across all graph implementations.
78

79
```java { .api }
80
public abstract class AbstractGraph<V,E> implements Graph<V,E>, Serializable {
81
    public boolean addEdge(E edge, Collection<? extends V> vertices);
82
    public boolean addEdge(E e, V v1, V v2);
83
    public abstract boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
84
}
85

86
public abstract class AbstractTypedGraph<V,E> extends AbstractGraph<V,E> {
87
    public AbstractTypedGraph(EdgeType edge_type);
88
    public EdgeType getDefaultEdgeType();
89
    public EdgeType getEdgeType(E e);
90
}
91
```
92

93
[Abstract Base Classes](./abstract-base-classes.md)
94

95
### Directed Graph Implementations
96

97
Specialized graph implementations for directed relationships where edges have a source vertex and destination vertex.
98

99
```java { .api }
100
public class DirectedSparseGraph<V,E> extends AbstractTypedGraph<V,E> implements DirectedGraph<V,E> {
101
    public DirectedSparseGraph();
102
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
103
}
104

105
public class DirectedSparseMultigraph<V,E> extends AbstractTypedGraph<V,E> 
106
    implements DirectedGraph<V,E>, MultiGraph<V,E> {
107
    public DirectedSparseMultigraph();
108
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
109
}
110
```
111

112
[Directed Graphs](./directed-graphs.md)
113

114
### Undirected Graph Implementations
115

116
Graph implementations for symmetric relationships where edges connect vertices without directional preference.
117

118
```java { .api }
119
public class UndirectedSparseGraph<V,E> extends AbstractTypedGraph<V,E> implements UndirectedGraph<V,E> {
120
    public UndirectedSparseGraph();
121
    public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
122
}
123

124
public class UndirectedSparseMultigraph<V,E> extends AbstractTypedGraph<V,E> 
125
    implements UndirectedGraph<V,E>, MultiGraph<V,E> {
126
    public UndirectedSparseMultigraph();
127
    public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
128
}
129
```
130

131
[Undirected Graphs](./undirected-graphs.md)
132

133
### Mixed Graph Implementations
134

135
General-purpose graph implementations supporting both directed and undirected edges within the same graph structure.
136

137
```java { .api }
138
public class SparseGraph<V,E> extends AbstractGraph<V,E> implements Graph<V,E> {
139
    public SparseGraph();
140
    public static <V,E> Supplier<Graph<V,E>> getFactory();
141
}
142

143
public class SparseMultigraph<V,E> extends AbstractGraph<V,E> implements MultiGraph<V,E> {
144
    public SparseMultigraph();
145
    public static <V,E> Supplier<Graph<V,E>> getFactory();
146
}
147
```
148

149
[Mixed Graphs](./mixed-graphs.md)
150

151
### Tree Implementations
152

153
Specialized hierarchical graph structures with parent-child relationships and tree-specific operations.
154

155
```java { .api }
156
public class DelegateTree<V,E> extends GraphDecorator<V,E> implements Tree<V,E> {
157
    public DelegateTree();
158
    public static <V,E> Supplier<Tree<V,E>> getFactory();
159
    public V getRoot();
160
    public Collection<V> getChildren(V parent);
161
}
162

163
public class DelegateForest<V,E> extends GraphDecorator<V,E> implements Forest<V,E> {
164
    public DelegateForest();
165
    public Collection<V> getRoots();
166
    public Collection<Tree<V,E>> getTrees();
167
}
168
```
169

170
[Tree Structures](./tree-structures.md)
171

172
### Specialized Graph Types
173

174
Advanced graph implementations for specific use cases including hypergraphs, ordered structures, and sorted graphs.
175

176
```java { .api }
177
public class SetHypergraph<V,H> implements Hypergraph<V,H>, MultiGraph<V,H>, Serializable {
178
    public SetHypergraph();
179
    public static <V,H> Supplier<Hypergraph<V,H>> getFactory();
180
    public boolean addEdge(H hyperedge, Collection<? extends V> to_attach);
181
}
182

183
public class OrderedKAryTree<V,E> extends AbstractTypedGraph<V,E> implements Tree<V,E> {
184
    public OrderedKAryTree(int order);
185
    public V getChild(V vertex, int index);
186
}
187

188
public class SortedSparseMultigraph<V,E> extends OrderedSparseMultigraph<V,E> implements MultiGraph<V,E> {
189
    public SortedSparseMultigraph();
190
    public SortedSparseMultigraph(Comparator<V> vertex_comparator, Comparator<E> edge_comparator);
191
    public static <V,E> Supplier<Graph<V,E>> getFactory();
192
}
193

194
public class DirectedOrderedSparseMultigraph<V,E> extends DirectedSparseMultigraph<V,E> 
195
    implements DirectedGraph<V,E>, MultiGraph<V,E> {
196
    public DirectedOrderedSparseMultigraph();
197
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
198
}
199

200
public class UndirectedOrderedSparseMultigraph<V,E> extends UndirectedSparseMultigraph<V,E> 
201
    implements UndirectedGraph<V,E>, MultiGraph<V,E> {
202
    public UndirectedOrderedSparseMultigraph();
203
    public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
204
}
205
```
206

207
[Specialized Graphs](./specialized-graphs.md)
208

209
### Utility Classes
210

211
Helper classes providing graph generation and testing utilities for development and testing purposes.
212

213
```java { .api }
214
public class TestGraphs {
215
    public static Graph<String, Number> createTestGraph(boolean directed);
216
    public static Graph<String,Number> getOneComponentGraph();
217
    public static Graph<String, Number> getDemoGraph();
218
}
219
```
220

221
[Utilities](./utilities.md)
222

223
## Common Types
224

225
```java { .api }
226
// Core interfaces from jung-api (referenced but not implemented in this module)
227
interface Hypergraph<V,E> {
228
    Collection<E> getEdges();
229
    Collection<V> getVertices();
230
    boolean containsVertex(V vertex);
231
    boolean containsEdge(E edge);
232
    int getEdgeCount();
233
    int getVertexCount();
234
    Collection<V> getNeighbors(V vertex);
235
    Collection<E> getIncidentEdges(V vertex);
236
    Collection<V> getIncidentVertices(E edge);
237
    E findEdge(V v1, V v2);
238
    Collection<E> findEdgeSet(V v1, V v2);
239
    boolean addVertex(V vertex);
240
    boolean removeVertex(V vertex);
241
    boolean addEdge(E edge, Collection<? extends V> vertices);
242
    boolean removeEdge(E edge);
243
}
244

245
interface Graph<V,E> extends Hypergraph<V,E> {
246
    Collection<E> getInEdges(V vertex);
247
    Collection<E> getOutEdges(V vertex);
248
    Collection<V> getPredecessors(V vertex);
249
    Collection<V> getSuccessors(V vertex);
250
    int inDegree(V vertex);
251
    int outDegree(V vertex);
252
    boolean isPredecessor(V v1, V v2);
253
    boolean isSuccessor(V v1, V v2);
254
    int getPredecessorCount(V vertex);
255
    int getSuccessorCount(V vertex);
256
    V getSource(E directed_edge);
257
    V getDest(E directed_edge);
258
    boolean isSource(V vertex, E edge);
259
    boolean isDest(V vertex, E edge);
260
}
261

262
interface DirectedGraph<V,E> extends Graph<V,E> {
263
    // Specialized directed graph interface
264
}
265

266
interface UndirectedGraph<V,E> extends Graph<V,E> {
267
    // Specialized undirected graph interface
268
}
269

270
interface MultiGraph<V,E> extends Graph<V,E> {
271
    // Allows multiple edges between same vertex pair
272
}
273

274
interface Tree<V,E> extends Graph<V,E> {
275
    V getRoot();
276
    Collection<V> getChildren(V vertex);
277
    V getParent(V vertex);
278
    int getDepth(V vertex);
279
    int getHeight();
280
}
281

282
interface Forest<V,E> extends Graph<V,E> {
283
    Collection<V> getRoots();
284
    Collection<Tree<V,E>> getTrees();
285
}
286

287
// Utility classes
288
class Pair<T> {
289
    public T getFirst();
290
    public T getSecond();
291
    public static <T> Pair<T> create(T first, T second);
292
}
293

294
enum EdgeType {
295
    DIRECTED, UNDIRECTED
296
}
297

298
// Abstract base classes (implemented in this module)
299
abstract class AbstractGraph<V,E> implements Graph<V,E>, Serializable {
300
    public boolean addEdge(E edge, Collection<? extends V> vertices);
301
    public boolean addEdge(E e, V v1, V v2);
302
    public abstract boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
303
}
304

305
abstract class AbstractTypedGraph<V,E> extends AbstractGraph<V,E> {
306
    public AbstractTypedGraph(EdgeType edge_type);
307
    public EdgeType getDefaultEdgeType();
308
    public EdgeType getEdgeType(E e);
309
}
310
```