4
\$\begingroup\$

Intro

(Repo here.)

A non-uniform undirected hypergraph is a generalization of an undirected graph. It is defined as \$H = (X, E)\$, where \$X\$ is the set of vertices and \$E \subseteq \mathcal{P}(X)\$ is the set of undirected hyperedges. In this setting, we equip \$E\$ with a weight function \$W \colon E \rightarrow \mathbb{R}_{>0}\$. Non-uniformity simply implies that the sizes of hyperedges may vary throughout the hypergraph.

A path in a hypergraph is a sequence \$P = (v_1, e_1, v_2, e_2, \ldots, e_{n-1}, v_n), v_i \in X, e_i \in E\$, and its weight is $$ W(P) = \sum_{i = 1}^{n - 1} E(e_i). $$

This post is about building the hypergraphs and doing shortest path searches via Dijkstra's algorithm.

Code

io.github.coderodde.graph.hyper.HyperGraphEdge.java:

package io.github.coderodde.graph.hyper;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * This class defines a hyperedge in a hypergraph.
 * 
 * @param <I> the type of the node identity object.
 * @param <J> the type of the edge identity object.
 * @param <W> the type of the weights.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 24, 2025)
 * @since 1.0.0 (Sep 24, 2025)
 */
public final class HyperGraphEdge<I, J, W> {
    
    private final J id;
    private final W weight;
    final List<HyperGraphNode<I, J, W>> edgeNodes = new ArrayList<>();
    
    public HyperGraphEdge(J id, W weight) {
        this.id = Objects.requireNonNull(id);
        this.weight = Objects.requireNonNull(weight);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        
        boolean first = true;
        
        for (HyperGraphNode<I, J, W> node : edgeNodes) {
            if (first) {
                first = false;
            } else {
                sb.append(", ");
            }
            
            sb.append(node.toString());
        }
        
        sb.append(": weight = ");
        sb.append(weight);
        sb.append("}");
        return sb.toString();
    }
    
    @Override
    public int hashCode() {
        return id.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        
        if (obj == null) {
            return false;
        }
        
        if (!getClass().equals(obj.getClass())) {
            return false;
        }
        
        HyperGraphEdge<I, J, W> other = (HyperGraphEdge<I, J, W>) obj;
        return id.equals(other.id) && weight.equals(other.weight);
    }
    
    public J getId() {
        return id;
    }
    
    public W getWeight() {
        return weight;
    }
    
    public void connectNode(HyperGraphNode<I, J, W> node) {
        Objects.requireNonNull(node);
        edgeNodes.add(node);
        node.edges.add(this);
    }
    
    public boolean containsNode(HyperGraphNode<I, J, W> node) {
        return edgeNodes.contains(node);
    }
    
    public void disconnectNode(HyperGraphNode<I, J, W> node) {
        Objects.requireNonNull(node);
        edgeNodes.remove(node);
        node.edges.remove(this);
    }
    
    public void clear() {
        for (HyperGraphNode<I, J, W> node : edgeNodes) {
            node.edges.remove(this);
        }
        
        edgeNodes.clear();
    }
    
    public List<HyperGraphNode<I, J, W>> getIncidentHyperNodes() {
        return Collections.unmodifiableList(edgeNodes);
    }
}

io.github.coderodde.graph.hyper.HyperGraphNode.java:

package io.github.coderodde.graph.hyper;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * This class defines a node in a hypergraph.
 * 
 * @param <I> the type of the identity object.
 * @param <W> the type of the weights.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 24, 2025)
 * @since 1.0.0 (Sep 24, 2025)
 */
public final class HyperGraphNode<I, J, W> {
   
    private final I id;
    protected final List<HyperGraphEdge<I, J, W>> edges = new ArrayList<>();
    
    public HyperGraphNode(I id) {
        this.id = Objects.requireNonNull(id);
    }
    
    public I getId() {
        return id;
    }
    
    @Override
    public String toString() {
        return id.toString();
    }
    
    @Override
    public int hashCode() {
        return id.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        
        if (obj == null) {
            return false;
        }
        
        if (!getClass().equals(obj.getClass())) {
            return false;
        }
        
        HyperGraphNode<I, J, W> other = (HyperGraphNode<I, J, W>) obj;
        return id.equals(other.id);
    }
    
    public List<HyperGraphEdge<I, J, W>> getIncidentHyperEdges() {
        return Collections.unmodifiableList(edges);
    }
}

io.github.coderodde.graph.hyper.HyperGraphPath.java:

package io.github.coderodde.graph.hyper;

import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * This class implements a hypergraph path, which is a list of nodes and a list
 * of hyperedges.
 * 
 * @param <I> the identity object type.
 * @param <W> the weight type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 1, 2025)
 * @since 1.0.0 (Oct 1, 2025)
 */
public final class HyperGraphPath<I, J, W> {
   
    private final W weight;
    private final List<HyperGraphNode<I, J, W>> nodes;
    private final List<HyperGraphEdge<I, J, W>> edges;
    
    public HyperGraphPath(List<HyperGraphNode<I, J, W>> nodes,
                          List<HyperGraphEdge<I, J, W>> edges,
                          WeightFunction<W> weightFunction) {
        
        Objects.requireNonNull(nodes);
        Objects.requireNonNull(edges);
        
        if (nodes.isEmpty()) {
            if (!edges.isEmpty()) {
                throw new IllegalArgumentException("Invalid hyper graph path");
            } else {
                this.nodes = nodes;
                this.edges = edges;
                this.weight = weightFunction.zero();
            }
        } else {
            if (nodes.size() - 1 != edges.size()) {
                throw new IllegalArgumentException(
                        "Node count, edge count mismatch");
            }
            
            check(nodes, edges);
            this.nodes = nodes;
            this.edges = edges;
            
            W w = weightFunction.zero();
            
            for (HyperGraphEdge<I, J, W> edge : edges) {
                w = weightFunction.apply(w, edge.getWeight());
            }
            
            this.weight = w;
        }
    }
    
    @Override
    public String toString() {
        if (isNonExistent()) {
            return "[: weight = 0]";
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        boolean first = true;
        
        for (int i = 0; i < edges.size(); ++i) {
            if (first) {
                first = false;
            } else {
                sb.append(", ");
            }
            
            HyperGraphNode<I, J, W> node = nodes.get(i);
            HyperGraphEdge<I, J, W> edge = edges.get(i);
            
            sb.append(node.toString());
            sb.append(", ");
            sb.append(edge.toString());
        }
        
        sb.append(", ");
        sb.append(nodes.get(nodes.size() - 1).toString());
        sb.append(": total weight = ");
        sb.append(weight);
        sb.append("]");
        return sb.toString();
    }
    
    public W getWeight() {
        return weight;
    }
    
    public boolean isNonExistent() {
        return nodes.isEmpty();
    }
    
    public List<HyperGraphNode<I, J, W>> getPathHyperNodes() {
        return Collections.unmodifiableList(nodes);
    }
    
    public List<HyperGraphEdge<I, J, W>> getPathHyperEdges() {
        return Collections.unmodifiableList(edges);
    }
    
    private static <I, J, W> void check(List<HyperGraphNode<I, J, W>> nodes,
                                        List<HyperGraphEdge<I, J, W>> edges) {
            
        for (int i = 0; i < nodes.size() - 1; ++i) {
            HyperGraphNode<I, J, W> node1 = nodes.get(i);
            HyperGraphNode<I, J, W> node2 = nodes.get(i + 1);
            HyperGraphEdge<I, J, W> edge = edges.get(i);
            
            if (!edge.containsNode(node1)) {
                throw new IllegalArgumentException("Invalid hyper graph path");
            }
            
            if (!edge.containsNode(node2)) {
                throw new IllegalArgumentException("Invalid hyper graph path");
            }
        }
        
        if (!edges.get(edges.size() - 1)
                .containsNode(nodes.get(nodes.size() - 1))) {
            throw new IllegalArgumentException("Invalid hyper graph path");
        }
    }
}

io.github.coderodde.graph.hyper.HyperGraphPathfinder.java:

package io.github.coderodde.graph.hyper;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * This class implements a point-to-point Dijkstra's algorithm over a 
 * hypergraph.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 1, 2025)
 * @since 1.0.0 (Oct 1, 2025)
 */
public final class HyperGraphPathfinder {
    
    public static <I, J, W>
         HyperGraphPath<I, J, W> find(HyperGraphNode<I, J, W> source,
                                      HyperGraphNode<I, J, W> target,
                                      WeightFunction<W> weights) {
        
        Queue<HeapNode<I, J, W>> open             = new PriorityQueue<>();
        Set<HyperGraphNode<I, J, W>> closed       = new HashSet<>();
        Map<HyperGraphNode<I, J, W>, W> distances = new HashMap<>();
        
        Map<HyperGraphNode<I, J, W>, HyperGraphNode<I, J, W>> parents = 
                new HashMap<>();
        
        open.add(new HeapNode(source, weights.zero(), weights));
        distances.put(source, weights.zero());
        parents.put(source, null);
        
        while (!open.isEmpty()) {
            HyperGraphNode<I, J, W> current = open.remove().node;
            
            if (current.equals(target)) {
                List<HyperGraphNode<I, J, W>> shortestPathNodes = 
                        tracebackPath(current, parents);
                
                List<HyperGraphEdge<I, J, W>> shortestPathHyperEdges = 
                        inferPathEdges(shortestPathNodes, weights);
                
                return new HyperGraphPath<>(shortestPathNodes,
                                            shortestPathHyperEdges,
                                            weights);
            }
            
            closed.add(current);
            
            for (HyperGraphEdge<I, J, W> edge 
                    : current.getIncidentHyperEdges()) {
                
                for (HyperGraphNode<I, J, W> child 
                        : edge.getIncidentHyperNodes()) {
                    
                    if (closed.contains(child)) {
                        continue;
                    }
                    
                    W tentative = 
                            weights.apply(edge.getWeight(),
                                          distances.get(current));
                    
                    if (!distances.containsKey(child) || 
                            weights.compare(distances.get(child), 
                                            tentative) > 1) {
                        
                        distances.put(child, tentative);
                        parents.put(child, current);
                        open.add(new HeapNode(child, 
                                              tentative, 
                                              weights));
                    }
                }
            }
        }
        
        throw new IllegalStateException("The hyper graph is disconnected");
    }
         
    private static <I, J, W> 
        List<HyperGraphNode<I, J, W>> 
            tracebackPath(HyperGraphNode<I, J, W> target,
                          Map<HyperGraphNode<I, J, W>, 
                              HyperGraphNode<I, J, W>> parents) {
        
        List<HyperGraphNode<I, J, W>> path = new ArrayList<>();
        HyperGraphNode<I, J, W> current = target;
        
        while (current != null) {
            path.addLast(current);
            current = parents.get(current);
        }
        
        Collections.reverse(path);
        return path;
    }
         
    private static <I, J, W> 
        List<HyperGraphEdge<I, J, W>> 
        inferPathEdges(List<HyperGraphNode<I, J, W>> shortestPathNodes, 
                       WeightFunction<W> weights) {
    
        List<HyperGraphEdge<I, J, W>> shortestPathEdges = 
                new ArrayList<>(shortestPathNodes.size() - 1);
        
        for (int i = 0; i < shortestPathNodes.size() - 1; ++i) {
            HyperGraphNode<I, J, W> node1 = shortestPathNodes.get(i);
            HyperGraphNode<I, J, W> node2 = shortestPathNodes.get(i + 1);
            
            HyperGraphEdge<I, J, W> edge = inferPathEdge(node1,
                                                         node2, 
                                                         weights);
            shortestPathEdges.add(edge);
        }
        
        return shortestPathEdges;
    }
        
    private static <I, J, W> HyperGraphEdge<I, J, W> 
        inferPathEdge(HyperGraphNode<I, J, W> node1,
                      HyperGraphNode<I, J, W> node2,
                      WeightFunction<W> weightFunction) {
        
        W smallestWeight = weightFunction.max();
        HyperGraphEdge<I, J, W> smallestHyperEdge = null;
        
        for (HyperGraphEdge<I, J, W> relay : node1.edges) {
            if (relay.edgeNodes.contains(node2)) {
                W currentWeight = relay.getWeight();
                
                if (weightFunction.compare(smallestWeight, currentWeight) > 0) {
                    smallestWeight = currentWeight;
                    smallestHyperEdge = relay;
                }
            }
        }
        
        if (smallestWeight == null) {
            throw new IllegalStateException("Should not get here");
        }
        
        return smallestHyperEdge; 
    }
            
    private static final class HeapNode<I, J, W> 
            implements Comparable<HeapNode<I, J, W>> {
        
        HyperGraphNode<I, J, W> node;
        W g;
        WeightFunction<W> weightFunction;
        
        HeapNode(HyperGraphNode<I, J, W> node, 
                 W g, 
                 WeightFunction<W> weightFunction) {
            this.node = node;
            this.g = g;
            this.weightFunction = weightFunction;
        }

        @Override
        public int compareTo(HeapNode<I, J, W> o) {
            return weightFunction.compare(g, o.g);
        }
    }
}

io.github.coderodde.graph.hyper.WeightFunction.java:

package io.github.coderodde.graph.hyper;

/**
 * This interface defines the API for the weight functions.
 * 
 * @param <W> the type of the weight.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 2, 2025)
 * @since 1.0.0 (Oct 2, 2025)
 */
public interface WeightFunction<W> {
   
    W zero();
    W max();
    W apply(W w1, W w2);
    int compare(W weight1, W weight2);
}

io.github.coderodde.graph.hyper.demo.Demo.java:

package io.github.coderodde.graph.hyper.demo;

import io.github.coderodde.graph.hyper.HyperGraphEdge;
import io.github.coderodde.graph.hyper.HyperGraphNode;
import io.github.coderodde.graph.hyper.HyperGraphPath;
import io.github.coderodde.graph.hyper.HyperGraphPathfinder;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 *
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 1, 2025)
 * @since 1.0.0 (Oct 1, 2025)
 */
public final class Demo {
    
    private static final int HYPER_NODES = 1_000_000;
    private static final int HYPER_EDGES = 400_000;
    private static final int MINIMUM_HYPER_EDGE_SIZE = 2;
    private static final int MAXIMUM_HYPER_EDGE_SIZE = 8;
    private static final int MINIMUM_HYPER_EDGE_WEIGHT = 1;
    private static final int MAXIMUM_HYPER_EDGE_WEIGHT = 10;
    
    private static final Random RND = new Random(13L);
    
    public static void main(String[] args) {
        long ta = System.currentTimeMillis();
        
        List<HyperGraphNode<Integer, Integer, Integer>> hyperGraph = 
                getRandomHyperGraph();

        long tb = System.currentTimeMillis();
        
        System.out.println(
                "Constructed the demo hyper graph in " 
                        + (tb - ta)
                        + " milliseconds.");
        
        HyperGraphNode<Integer, Integer, Integer> source = choose(hyperGraph);
        HyperGraphNode<Integer, Integer, Integer> target = choose(hyperGraph);
        
        ta = System.currentTimeMillis();
        
        HyperGraphPath<Integer, Integer, Integer> path =
                HyperGraphPathfinder.find(source, 
                                          target,
                                          new IntegerWeightFunction());
        tb = System.currentTimeMillis();
        
        printPath(path);
        
        System.out.println("Duration: " + (tb - ta) + " milliseconds.");
    }
    
    private static void printPath(HyperGraphPath<Integer, 
                                                 Integer, 
                                                 Integer> path) {
        for (int i = 0; i < path.getPathHyperEdges().size(); ++i) {
            System.out.println(path.getPathHyperNodes().get(i));
            System.out.println(path.getPathHyperEdges().get(i));
        }
        
        System.out.println(
                path.getPathHyperNodes()
                    .get(path.getPathHyperNodes().size() - 1)
                    .toString());
        
        System.out.println("Path weight = " + path.getWeight());
    }
    
    private static List<HyperGraphNode<Integer, 
                                       Integer, 
                                       Integer>> getRandomHyperGraph() {
                                           
        List<HyperGraphNode<Integer, Integer, Integer>> nodes =
                new ArrayList<>();
        
        createHyperNodes(nodes);
        createHyperEdges(nodes);
        
        return nodes;
    }
    
    private static 
        void createHyperNodes(List<HyperGraphNode<Integer, 
                                                  Integer, 
                                                  Integer>> nodes) {
            
        for (int id = 0; id < HYPER_NODES; ++id) {
            nodes.add(new HyperGraphNode<>(id));
        }
    }
    
    private static 
        void createHyperEdges(List<HyperGraphNode<Integer,
                                                  Integer, 
                                                  Integer>> nodes) {
            
        for (int i = 0; i < HYPER_EDGES; ++i) {
            Integer weight = getRandomWeight();
            
            HyperGraphEdge<Integer, Integer, Integer> edge =
                    new HyperGraphEdge<>(i, weight);
            
            int hyperEdgeSize = getHyperEdgeSize();
            
            for (int j = 0; j < hyperEdgeSize; ++j) {
                HyperGraphNode<Integer, Integer, Integer> node = choose(nodes);
                edge.connectNode(node);
            }
        }
    }
        
    private static int getRandomWeight() {
        return MINIMUM_HYPER_EDGE_WEIGHT + 
               RND.nextInt(MAXIMUM_HYPER_EDGE_WEIGHT + 1);
    }
        
    private static int getHyperEdgeSize() {
        return MINIMUM_HYPER_EDGE_SIZE + RND.nextInt(MAXIMUM_HYPER_EDGE_SIZE -
                                                     MINIMUM_HYPER_EDGE_SIZE +
                                                     1);
    }
    
    private static HyperGraphNode<Integer, Integer, Integer> 
        choose(List<HyperGraphNode<Integer, Integer, Integer>> nodes) {
            
        return nodes.get(RND.nextInt(nodes.size()));
    }
}

io.github.coderodde.graph.hyper.demo.IntegerWeightFunction.java:

package io.github.coderodde.graph.hyper.demo;

import io.github.coderodde.graph.hyper.WeightFunction;

/**
 * This class defines a weight function over integer valued weights.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 1, 2025)
 * @since 1.0.0 (Oct 1, 2025)
 */
public final class IntegerWeightFunction implements WeightFunction<Integer> {

    @Override
    public Integer zero() {
        return 0;
    }

    @Override
    public Integer max() {
        return Integer.MAX_VALUE;
    }    

    @Override
    public Integer apply(Integer w1, Integer w2) {
        return w1 + w2;
    }

    @Override
    public int compare(Integer weight1, Integer weight2) {
        return Integer.compare(weight1,
                               weight2);
    }
}

io.github.coderodde.graph.hyper.HyperGraphPathfinderTest.java:

package io.github.coderodde.graph.hyper;

import io.github.coderodde.graph.hyper.demo.IntegerWeightFunction;
import org.junit.Test;
import static org.junit.Assert.*;

public class HyperGraphPathfinderTest {
    
    private final IntegerWeightFunction weightFunction =
            new IntegerWeightFunction();
    
    @Test
    public void find() {
        HyperGraphNode<Integer, Integer, Integer> node1 = new HyperGraphNode<>(1);
        HyperGraphNode<Integer, Integer, Integer> node2 = new HyperGraphNode<>(2);
        HyperGraphNode<Integer, Integer, Integer> node3 = new HyperGraphNode<>(3);
        
        HyperGraphEdge<Integer, Integer, Integer> edge1 = new HyperGraphEdge<>(1, 3);
        HyperGraphEdge<Integer, Integer, Integer> edge2 = new HyperGraphEdge<>(2, 4);
        
        edge1.connectNode(node1);
        edge1.connectNode(node2);
        edge2.connectNode(node2);
        edge2.connectNode(node3);
        
        HyperGraphPath<Integer, Integer, Integer> path = 
                HyperGraphPathfinder.find(node1,
                                          node3, 
                                          weightFunction);
        
        assertEquals(3, path.getPathHyperNodes().size());
        assertEquals(2, path.getPathHyperEdges().size());
        assertEquals((Integer) 7, path.getWeight());
        
        assertEquals(node1, path.getPathHyperNodes().get(0));
        assertEquals(node2, path.getPathHyperNodes().get(1));
        assertEquals(node3, path.getPathHyperNodes().get(2));
        
        assertEquals(edge1, path.getPathHyperEdges().get(0));
        assertEquals(edge2, path.getPathHyperEdges().get(1));
    }
    
    @Test(expected = IllegalStateException.class)
    public void throwOnDisconnectedGraph() {
        HyperGraphNode<Integer, Integer, Integer> node1 = new HyperGraphNode<>(1);
        HyperGraphNode<Integer, Integer, Integer> node2 = new HyperGraphNode<>(2);
        
        HyperGraphPathfinder.find(node1, node2, weightFunction);
    }
}

Typical output

Upon running the demo, you may see something like this:

Constructed the demo hyper graph in 1608 milliseconds.
390911
{390911, 849968, 177123, 682640, 746861, 103098, 771371: weight = 7}
746861
{216808, 292096, 857104, 670690, 664252, 746861, 177132, 271731: weight = 3}
857104
{857104, 182243, 151240, 315206, 358042, 766286, 671534, 423391: weight = 2}
182243
{669894, 861245, 838714, 786917, 419295, 182243, 451992: weight = 3}
786917
{446311, 379586, 450054, 210074, 38918, 159222, 786917, 338431: weight = 1}
210074
{586810, 973842, 210074, 666084, 925230, 258039: weight = 3}
586810
{16707, 899620, 657094, 105614, 463659, 837351, 586810: weight = 1}
657094
{518289, 720484, 361585, 610, 657094, 200696: weight = 1}
720484
{430901, 418517, 433285, 184287, 765154, 830803, 720484, 581154: weight = 3}
430901
{132047, 286114, 254149, 430901: weight = 10}
132047
Path weight = 34
Duration: 4659 milliseconds.

Critique request

As always, tell me anything that comes to mind.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ What even is a "Path" under the concept of hyperedges? The formalism is not really intuitively expandable IMO. Effectively the question boils down to whether adding an edge with more than two nodes affected opens a "frontier". This also makes for an interesting question about what the weight of a path is: Would it be sensible to scale the weights of an edge with the number of nodes it encompasses or how does this work? \$\endgroup\$ Commented Oct 3 at 10:56
  • \$\begingroup\$ @Vogel612 I will elaborate on that later. \$\endgroup\$ Commented Oct 3 at 11:01
  • \$\begingroup\$ @Vogel612 I have specified the notion of a path in a hypergraph and defined its weight. \$\endgroup\$ Commented Oct 4 at 7:52

2 Answers 2

Reset to default
4
\$\begingroup\$

It doesn't seem like a hyperedge cares about the order in which its nodes are connected or vice versa, and it doesn't seem like the same node should be able to appear multiple times on the same hyperedge. If so I would expect HyperGraphEdge.edgeNodes and HyperGraphNode.edges to be Sets rather than Lists.

If we can make that change, I'm also curious if we need to support the use case where someone re-uses the same graph with several different weight functions? If not, we might able to store HyperGraphNode.edges as a SortedSet (ordered by something like Comparator.comparing(HyperGraphEdge::getWeight, weightFunction::compare)), and simplify HyperGraphPathfinder::inferPathEdge to something like

private static <I, J, W> HyperGraphEdge<I, J, W> 
    inferPathEdge(HyperGraphNode<I, J, W> node1,
                  HyperGraphNode<I, J, W> node2) {

    for (HyperGraphEdge<I, J, W> relay : node1.edges) {
        if (relay.edgeNodes.contains(node2)) {
            return relay; // Known to have the smallest weight as we iterate in weight order
        }
    }

    throw new IllegalStateException("No edge connects " + node1.toString() + " and " + node2.toString());
}

If we can do that, I'd even be tempted to move that function into HyperGraphNode, make it public, and perhaps let it return an Optional<HyperGraphEdge<I, J, W>> instead of throwing.

In HyperGraphPath.check, "Invalid hyper graph path" is not a very descriptive error message. Something like "(node1) can't be connected to (node2) via (edge) as it does not contain the former/latter" would be more help when debugging I think.

I personally find the manual string joining loop in HyperGraphEdge.toString a little bit less easy to read than the equivalent sb.append(edgeNodes.stream().collect(Collectors.joining(", ")), but that is very much a matter of personal taste.

In recent versions of Java, someList.get(someList.size() - 1) can be replaced with someList.getLast().

\$\endgroup\$
0
3
\$\begingroup\$

I'll just focus on the code, as math and related subjects are generally better answered by anybody but me. In general the code looks quite good though, so I'll start with that.

The good

Guard statements such as null checks, equals and hashCode are well implemented.

In general, the naming of the identifiers within the code is great. The code is easy to read.

Generally OK use of code blocks, indentation, style, constants etc.

...the bad...

final List<HyperGraphNode<I, J, W>> edgeNodes = new ArrayList<>();

It seems strange and unnecessary to explose the edgenodes, generally all fields should be private unless there are very specific reasons not to do so. Instances of ArrayList are mutable (when created through the given constructor), so this exposes most of the edge (instance) to the outside world, breaking encapsulation.

This is especially grievous in e.g. HyperGraphNode as the class is otherwise immutable, it even has a getIncidentHyperEdges() that returns an unmodifiable list of all the edges.

public HyperGraphEdge(J id, W weight) {

Although some variables are documented, the id for instance is not. This can be confusing as hypergraphs generally do not seem to have an id assigned to them in the literature. It is also not clear how this kind of id needs to be generated by the user / the constraints are not clear.

public boolean isNonExistent() {

I get what is being returned, but this one made me chuckle. A different method name could be thought of.

public final class HyperGraphPathfinder {

The problem with this class name is that you'd expect a finder to be instantiatable. And it can be as no private constructor has been defined on it. However, the class only consists of static methods. That means that either the class name should be changed to FindUtil or similar, or that the static methods are changed into member methods. This would e.g. allow the finder to be made configurable, or overridden in a later version. IMHO this refactor to a normal class should be favorable. In that case the class name should have a capital letter for finder, i.e. HyperGraphPathFinder.

and the questionable

No, not the ugly ;)

I'd refer to specific functions in the literature for the implementations.

The find function is a bit deep, but I'm not sure if it would be easy to divide it up.

The code depends on quite a few type arguments . It seems mostly made for integers, especially when it e.g. comes to the id of the various instances.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You're right that there's no need to expose HyperGraphEdge.edgeNodes, but I disagree with the "especially grievous in e.g. HyperGraphNode" part since HyperGraphNode.edges is mutated in HyperGraphEdge::connectNode and HyperGraphEdge::disconnectNode to keep the lists in sync. Sure, there are ways to do that while making the HyperGraphNode.edges private, but I'm not convinced those are improvements. \$\endgroup\$ Commented Oct 6 at 15:33
  • 1
    \$\begingroup\$ @SaraJ That seems reasonable. I'll create a project out of the source files and see how they're connected. They are at least package-private of course. \$\endgroup\$ Commented Oct 7 at 7:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.