CtrlK
BlogDocsLog inGet started
Tessl Logo

tessl/maven-net-sf-jung--jung-graph-impl

Graph implementations for the JUNG project - provides concrete implementations of graph data structures for the Java Universal Network/Graph Framework

—

Pending
Overview
Eval results
Files

directed-graphs.mddocs/

Directed Graph Implementations

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.

Capabilities

DirectedSparseGraph

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

/**
 * An implementation of DirectedGraph suitable for sparse graphs.
 * Does not permit parallel edges.
 */
public class DirectedSparseGraph<V,E> extends AbstractTypedGraph<V,E> implements DirectedGraph<V,E> {
    
    /**
     * Creates an instance of DirectedSparseGraph
     */
    public DirectedSparseGraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for DirectedSparseGraph instances
     */
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
    
    // Core graph operations
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
    public boolean addVertex(V vertex);
    public boolean removeVertex(V vertex);
    public boolean removeEdge(E edge);
    
    // Vertex and edge queries
    public Collection<E> getEdges();
    public Collection<V> getVertices();
    public boolean containsVertex(V vertex);
    public boolean containsEdge(E edge);
    public int getEdgeCount();
    public int getVertexCount();
    
    // Edge discovery and navigation
    public E findEdge(V v1, V v2);
    public Collection<E> findEdgeSet(V v1, V v2);
    public Pair<V> getEndpoints(E edge);
    
    // Directed graph specific operations
    public Collection<E> getInEdges(V vertex);
    public Collection<E> getOutEdges(V vertex);
    public Collection<V> getPredecessors(V vertex);
    public Collection<V> getSuccessors(V vertex);
    public V getSource(E directed_edge);
    public V getDest(E directed_edge);
    public boolean isSource(V vertex, E edge);
    public boolean isDest(V vertex, E edge);
    
    // Neighborhood operations
    public Collection<V> getNeighbors(V vertex);
    public Collection<E> getIncidentEdges(V vertex);
}

Usage Examples:

import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.DirectedGraph;

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

// Add vertices
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");

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

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

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

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

DirectedSparseMultigraph

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

/**
 * An implementation of DirectedGraph suitable for sparse graphs that permits parallel edges.
 */
public class DirectedSparseMultigraph<V,E> extends AbstractTypedGraph<V,E> 
    implements DirectedGraph<V,E>, MultiGraph<V,E> {
    
    /**
     * Creates a new instance of DirectedSparseMultigraph
     */
    public DirectedSparseMultigraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for DirectedSparseMultigraph instances
     */
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
    
    // Core graph operations (same interface as DirectedSparseGraph)
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
    public boolean addVertex(V vertex);
    public boolean removeVertex(V vertex);
    public boolean removeEdge(E edge);
    
    // Collection queries
    public Collection<E> getEdges();
    public Collection<V> getVertices();
    public boolean containsVertex(V vertex);
    public boolean containsEdge(E edge);
    public int getEdgeCount();
    public int getVertexCount();
    
    // Directed graph operations
    public Collection<E> getInEdges(V vertex);
    public Collection<E> getOutEdges(V vertex);
    public Collection<V> getPredecessors(V vertex);
    public Collection<V> getSuccessors(V vertex);
    public V getSource(E edge);
    public V getDest(E edge);
    public boolean isSource(V vertex, E edge);
    public boolean isDest(V vertex, E edge);
    public Pair<V> getEndpoints(E edge);
    
    // Edge finding (may return any of multiple parallel edges)
    public E findEdge(V v1, V v2);
    
    // Neighborhood operations
    public Collection<V> getNeighbors(V vertex);
    public Collection<E> getIncidentEdges(V vertex);
}

Usage Examples:

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.DirectedGraph;

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

multigraph.addVertex("A");
multigraph.addVertex("B");

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

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

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

DirectedOrderedSparseMultigraph

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

/**
 * An implementation of DirectedGraph suitable for sparse graphs that orders 
 * its vertex and edge collections according to insertion time and permits parallel edges.
 */
public class DirectedOrderedSparseMultigraph<V,E> extends DirectedSparseMultigraph<V,E> 
    implements DirectedGraph<V,E>, MultiGraph<V,E> {
    
    /**
     * Creates a new instance of DirectedOrderedSparseMultigraph
     */
    public DirectedOrderedSparseMultigraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for DirectedOrderedSparseMultigraph instances
     */
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
    
    // Overridden methods that preserve insertion order
    public boolean addVertex(V vertex);
    public Collection<V> getPredecessors(V vertex);
    public Collection<V> getSuccessors(V vertex);
    public Collection<V> getNeighbors(V vertex);
    public Collection<E> getIncidentEdges(V vertex);
}

Usage Examples:

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph;
import edu.uci.ics.jung.graph.DirectedGraph;

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

// Add vertices - order is preserved
orderedGraph.addVertex("First");
orderedGraph.addVertex("Second");
orderedGraph.addVertex("Third");

orderedGraph.addEdge("edge1", "First", "Second");
orderedGraph.addEdge("edge2", "First", "Third");
orderedGraph.addEdge("edge3", "Second", "Third");

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

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

Performance Characteristics

DirectedSparseGraph

  • Space Complexity: O(V + E) - optimal for sparse graphs
  • Edge Addition: O(1) average case
  • Vertex Removal: O(degree(v))
  • Edge Lookup: O(1) average case
  • Neighbor Queries: O(degree(v))

DirectedSparseMultigraph

  • Space Complexity: O(V + E) - supports multiple edges efficiently
  • Parallel Edge Support: Uses sets to store multiple edges between vertices
  • Edge Lookup: O(1) for existence, returns arbitrary parallel edge

DirectedOrderedSparseMultigraph

  • Ordering Overhead: Uses LinkedHashSet for order preservation
  • Insertion Order: Guaranteed preservation across all collection operations
  • Memory Overhead: Slightly higher than unordered variants

Common Use Cases

DirectedSparseGraph

  • Dependency graphs, workflow modeling, social network following relationships
  • Network routing, finite state machines, citation networks

DirectedSparseMultigraph

  • Transportation networks with multiple routes, communication networks with redundant connections
  • Biological networks with multiple interaction types

DirectedOrderedSparseMultigraph

  • Process flows where step order matters, hierarchical structures
  • Timeline-based networks, ordered dependency chains

Install with Tessl CLI

npx tessl i tessl/maven-net-sf-jung--jung-graph-impl

docs

abstract-base-classes.md

directed-graphs.md

index.md

mixed-graphs.md

specialized-graphs.md

tree-structures.md

undirected-graphs.md

utilities.md

tile.json