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

undirected-graphs.mddocs/

Undirected Graph Implementations

Graph implementations for symmetric relationships where edges connect vertices without directional preference. All connections are bidirectional, making these implementations ideal for modeling symmetric relationships like friendships, physical connections, or mutual associations.

Capabilities

UndirectedSparseGraph

Basic undirected graph implementation suitable for sparse graphs, where all edges represent bidirectional connections.

/**
 * An implementation of UndirectedGraph that is suitable for sparse graphs.
 * Does not permit parallel edges.
 */
public class UndirectedSparseGraph<V,E> extends AbstractTypedGraph<V,E> implements UndirectedGraph<V,E> {
    
    /**
     * Creates an instance of UndirectedSparseGraph
     */
    public UndirectedSparseGraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for UndirectedSparseGraph instances
     */
    public static <V,E> Supplier<UndirectedGraph<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);
    
    // Undirected graph operations (in/out edges are equivalent)
    public Collection<E> getInEdges(V vertex);    // Same as getIncidentEdges
    public Collection<E> getOutEdges(V vertex);   // Same as getIncidentEdges
    public Collection<V> getPredecessors(V vertex); // Same as getNeighbors
    public Collection<V> getSuccessors(V vertex);   // Same as getNeighbors
    
    // Direction queries (always return null/false for undirected graphs)
    public V getSource(E directed_edge);    // Returns null
    public V getDest(E directed_edge);      // Returns null
    public boolean isSource(V vertex, E edge); // Returns false
    public boolean isDest(V vertex, E edge);   // Returns false
    
    // Neighborhood operations
    public Collection<V> getNeighbors(V vertex);
    public Collection<E> getIncidentEdges(V vertex);
}

Usage Examples:

import edu.uci.ics.jung.graph.UndirectedSparseGraph;
import edu.uci.ics.jung.graph.UndirectedGraph;

// Create an undirected graph
UndirectedGraph<String, String> graph = new UndirectedSparseGraph<>();

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

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

// All relationships are symmetric
Collection<String> neighborsA = graph.getNeighbors("A"); // ["B"]
Collection<String> neighborsB = graph.getNeighbors("B"); // ["A", "C"]

// Predecessors and successors are identical in undirected graphs
Collection<String> predecessors = graph.getPredecessors("B"); // ["A", "C"]
Collection<String> successors = graph.getSuccessors("B");     // ["A", "C"]

// No directional information available
String source = graph.getSource("edge1"); // null
String dest = graph.getDest("edge1");     // null

// In/out edges are the same as incident edges
Collection<String> inEdges = graph.getInEdges("B");  // ["edge1", "edge2"]
Collection<String> outEdges = graph.getOutEdges("B"); // ["edge1", "edge2"]
Collection<String> incidentEdges = graph.getIncidentEdges("B"); // ["edge1", "edge2"]

UndirectedSparseMultigraph

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

/**
 * An implementation of UndirectedGraph that is suitable for sparse graphs 
 * and permits parallel edges.
 */
public class UndirectedSparseMultigraph<V,E> extends AbstractTypedGraph<V,E> 
    implements UndirectedGraph<V,E>, MultiGraph<V,E> {
    
    /**
     * Creates a new instance of UndirectedSparseMultigraph
     */
    public UndirectedSparseMultigraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for UndirectedSparseMultigraph instances
     */
    public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
    
    // Core graph operations
    public boolean addEdge(E edge, V v1, V v2, EdgeType edgeType);
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edge_type);
    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();
    
    // Undirected graph operations
    public Collection<E> getInEdges(V vertex);      // Same as getIncidentEdges
    public Collection<E> getOutEdges(V vertex);     // Same as getIncidentEdges
    public Collection<V> getPredecessors(V vertex); // Same as getNeighbors
    public Collection<V> getSuccessors(V vertex);   // Same as getNeighbors
    public Collection<V> getNeighbors(V vertex);
    public Collection<E> getIncidentEdges(V vertex);
    
    // Edge finding and endpoints
    public E findEdge(V v1, V v2);
    public Pair<V> getEndpoints(E edge);
    
    // Direction queries (no directional information in undirected graphs)
    public V getDest(E directed_edge);      // Returns null
    public V getSource(E directed_edge);    // Returns null
    public boolean isDest(V vertex, E edge);   // Returns false
    public boolean isSource(V vertex, E edge); // Returns false
}

Usage Examples:

import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;
import edu.uci.ics.jung.graph.UndirectedGraph;

// Create an undirected multigraph
UndirectedGraph<String, String> multigraph = new UndirectedSparseMultigraph<>();

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> incidentEdges = multigraph.getIncidentEdges("A"); 
// ["edge1", "edge2", "edge3"]

Collection<String> neighbors = multigraph.getNeighbors("A"); // ["B"]
int edgeCount = multigraph.getEdgeCount(); // 3

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

UndirectedOrderedSparseMultigraph

Undirected multigraph that maintains insertion order for vertices and edges.

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

Usage Examples:

import edu.uci.ics.jung.graph.UndirectedOrderedSparseMultigraph;
import edu.uci.ics.jung.graph.UndirectedGraph;

// Create an ordered undirected multigraph
UndirectedGraph<String, String> orderedGraph = new UndirectedOrderedSparseMultigraph<>();

// 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> neighbors = orderedGraph.getNeighbors("First");
// Order: ["Second", "Third"] (insertion order preserved)

Key Differences from Directed Graphs

Symmetric Relationships

In undirected graphs, all relationships are bidirectional:

  • If vertex A is connected to vertex B, then B is also connected to A
  • getNeighbors(), getPredecessors(), and getSuccessors() return identical results
  • getInEdges(), getOutEdges(), and getIncidentEdges() return identical results

No Directional Information

Undirected graphs have no concept of edge direction:

  • getSource() and getDest() always return null
  • isSource() and isDest() always return false
  • Edge endpoints are unordered pairs

Edge Semantics

// In directed graphs:
directedGraph.addEdge("edge", "A", "B");  // A -> B (A is source, B is destination)

// In undirected graphs:
undirectedGraph.addEdge("edge", "A", "B"); // A - B (no direction, mutual connection)

Performance Characteristics

UndirectedSparseGraph

  • 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))

UndirectedSparseMultigraph

  • Parallel Edge Support: Efficient storage of multiple edges between vertices
  • Space Complexity: O(V + E) with set-based edge storage

UndirectedOrderedSparseMultigraph

  • Ordering Guarantee: LinkedHashSet ensures insertion order preservation
  • Memory Overhead: Slightly higher than unordered variants

Common Use Cases

UndirectedSparseGraph

  • Social networks (friendships, connections), computer networks, molecular structures
  • Collaboration networks, transportation infrastructure, communication networks

UndirectedSparseMultigraph

  • Transportation networks with multiple routes between locations
  • Communication networks with redundant connections, weighted edges represented as parallel edges

UndirectedOrderedSparseMultigraph

  • Networks where connection order matters, temporal analysis of relationship formation
  • Ordered traversals, maintaining historical context of connections

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