Specialized Graph Types

/**
 * An implementation of Hypergraph that is suitable for sparse graphs and permits parallel edges.
 * Hyperedges can connect multiple vertices (not just pairs).
 */
public class SetHypergraph<V,H> implements Hypergraph<V,H>, MultiGraph<V,H>, Serializable {
    
    /**
     * Creates a SetHypergraph and initializes the internal data structures
     */
    public SetHypergraph();
    
    /**
     * Returns a Factory which creates instances of this hypergraph type
     * @return Factory supplier for SetHypergraph instances
     */
    public static <V,H> Supplier<Hypergraph<V,H>> getFactory();
    
    // Hypergraph-specific edge addition
    public boolean addEdge(H hyperedge, Collection<? extends V> to_attach);
    public boolean addEdge(H hyperedge, Collection<? extends V> to_attach, EdgeType edge_type);
    
    // Core graph operations
    public boolean addVertex(V vertex);
    public boolean removeVertex(V vertex);
    public boolean removeEdge(H hyperedge);
    
    // Vertex and edge queries
    public Collection<H> getEdges();
    public Collection<V> getVertices();
    public boolean containsVertex(V vertex);
    public boolean containsEdge(H edge);
    public int getEdgeCount();
    public int getVertexCount();
    
    // Hypergraph navigation
    public Collection<V> getNeighbors(V vertex);      // All vertices connected via hyperedges
    public Collection<H> getIncidentEdges(V vertex);  // All hyperedges containing vertex
    public Collection<V> getIncidentVertices(H edge); // All vertices in hyperedge
    
    // Edge finding between vertices
    public H findEdge(V v1, V v2);
    public Collection<H> findEdgeSet(V v1, V v2);
    
    // Relationship queries
    public boolean isNeighbor(V v1, V v2);
    public boolean isIncident(V vertex, H edge);
    public int degree(V vertex);
    public int getNeighborCount(V vertex);
    public int getIncidentCount(H edge); // Number of vertices in hyperedge
    
    // Edge type operations (hypergraphs are always undirected)
    public EdgeType getEdgeType(H edge);      // Always EdgeType.UNDIRECTED
    public int getEdgeCount(EdgeType edge_type);
    public Collection<H> getEdges(EdgeType edge_type);
    public EdgeType getDefaultEdgeType();    // Returns EdgeType.UNDIRECTED
    
    // Directed graph interface (not applicable to hypergraphs)
    public Collection<H> getInEdges(V vertex);    // Same as getIncidentEdges
    public Collection<H> getOutEdges(V vertex);   // Same as getIncidentEdges  
    public int inDegree(V vertex);                 // Same as degree
    public int outDegree(V vertex);                // Same as degree
    public V getDest(H directed_edge);             // Always returns null
    public V getSource(H directed_edge);           // Always returns null
    public Collection<V> getPredecessors(V vertex); // Same as getNeighbors
    public Collection<V> getSuccessors(V vertex);   // Same as getNeighbors
}

import edu.uci.ics.jung.graph.SetHypergraph;
import edu.uci.ics.jung.graph.Hypergraph;
import java.util.Arrays;

// Create a hypergraph
Hypergraph<String, String> hypergraph = new SetHypergraph<>();

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

// Add hyperedges connecting multiple vertices
hypergraph.addEdge("hyperedge1", Arrays.asList("A", "B", "C"));      // 3-way connection
hypergraph.addEdge("hyperedge2", Arrays.asList("B", "C", "D"));      // Another 3-way
hypergraph.addEdge("hyperedge3", Arrays.asList("A", "D"));           // Standard edge (2-way)

// Query hyperedge contents
Collection<String> vertices1 = hypergraph.getIncidentVertices("hyperedge1"); // ["A", "B", "C"]
int edgeSize = hypergraph.getIncidentCount("hyperedge1");                     // 3

// Query vertex connections
Collection<String> incidentEdges = hypergraph.getIncidentEdges("B");         // ["hyperedge1", "hyperedge2"]
Collection<String> neighbors = hypergraph.getNeighbors("B");                 // ["A", "C", "D"]

// Vertex degree in hypergraph context
int degree = hypergraph.degree("B"); // Number of hyperedges containing B: 2

// Find hyperedges between vertices
String edge = hypergraph.findEdge("A", "B"); // Returns one of: "hyperedge1" 
Collection<String> edges = hypergraph.findEdgeSet("A", "B"); // All edges containing both A and B

/**
 * An implementation of Graph that orders its vertex and edge collections 
 * according to insertion time, is suitable for sparse graphs, and permits 
 * directed, undirected, and parallel edges.
 */
public class OrderedSparseMultigraph<V,E> extends SparseMultigraph<V,E> implements MultiGraph<V,E> {
    
    /**
     * Creates a new instance of OrderedSparseMultigraph
     */
    public OrderedSparseMultigraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for OrderedSparseMultigraph instances
     */
    public static <V,E> Supplier<Graph<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);
}

/**
 * An implementation of Graph suitable for sparse graphs, orders its vertex 
 * and edge collections according to specified Comparator instances or natural 
 * ordering, and permits directed, undirected, and parallel edges.
 */
public class SortedSparseMultigraph<V,E> extends OrderedSparseMultigraph<V,E> implements MultiGraph<V,E> {
    
    /**
     * Creates new instance with specified comparators
     * @param vertex_comparator Comparator for ordering vertices
     * @param edge_comparator Comparator for ordering edges
     */
    public SortedSparseMultigraph(Comparator<V> vertex_comparator, Comparator<E> edge_comparator);
    
    /**
     * Creates new instance that sorts according to natural ordering
     */
    public SortedSparseMultigraph();
    
    /**
     * Returns a Supplier that creates instances of this graph type
     * @return Factory supplier for SortedSparseMultigraph instances
     */
    public static <V,E> Supplier<Graph<V,E>> getFactory();
    
    /**
     * Provides new Comparator for sorting vertices
     * @param vertex_comparator New comparator for vertex ordering
     */
    public void setVertexComparator(Comparator<V> vertex_comparator);
    
    // Overridden method for sorted vertex addition
    public boolean addVertex(V vertex);
    
    // Protected fields for custom ordering
    protected Comparator<V> vertex_comparator;
    protected Comparator<E> edge_comparator;
}

import edu.uci.ics.jung.graph.SortedSparseMultigraph;
import java.util.Comparator;

// Create sorted graph with custom comparators
SortedSparseMultigraph<String, String> sortedGraph = new SortedSparseMultigraph<>(
    String::compareTo,                    // Natural string ordering for vertices
    Comparator.comparing(String::length)  // Sort edges by length
);

// Add vertices - automatically sorted
sortedGraph.addVertex("Zebra");
sortedGraph.addVertex("Apple");
sortedGraph.addVertex("Banana");

// Vertices returned in sorted order
Collection<String> vertices = sortedGraph.getVertices(); // ["Apple", "Banana", "Zebra"]

// Add edges with different lengths - sorted by length
sortedGraph.addEdge("a", "Apple", "Banana");      // Length 1
sortedGraph.addEdge("medium", "Banana", "Zebra"); // Length 6
sortedGraph.addEdge("short", "Apple", "Zebra");   // Length 5

// Edges returned sorted by length
Collection<String> edges = sortedGraph.getEdges(); // ["a", "short", "medium"]

// Change vertex sorting dynamically
sortedGraph.setVertexComparator(Comparator.reverseOrder());
// Future vertex operations will use reverse ordering

/**
 * 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> {
    
    public DirectedOrderedSparseMultigraph();
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory();
    
    // Insertion order preserved methods
    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);
}

/**
 * An implementation of UndirectedGraph suitable for sparse graphs that 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> {
    
    public UndirectedOrderedSparseMultigraph();
    public static <V,E> Supplier<UndirectedGraph<V,E>> getFactory();
    
    // Insertion order preserved methods
    public boolean addVertex(V vertex);
    public Collection<V> getNeighbors(V vertex);
}

// Traditional graph: edge connects 2 vertices
graph.addEdge("edge1", "A", "B");

// Hypergraph: hyperedge connects multiple vertices
hypergraph.addEdge("hyperedge1", Arrays.asList("A", "B", "C", "D"));

// Hyperedge connects A, B, C
hypergraph.addEdge("hedge1", Arrays.asList("A", "B", "C"));
// Hyperedge connects B, D, E  
hypergraph.addEdge("hedge2", Arrays.asList("B", "D", "E"));

Collection<String> neighborsB = hypergraph.getNeighbors("B"); // ["A", "C", "D", "E"]