4
\$\begingroup\$

Motivation

I do a lot of graph-theoretic code, and, by now, I feel substantial need for data structures that can represent weighted graphs, both directed and undirected. Up till now, I was in a habit of writing a graph node type along with the weight function (in my prior posts, something like DirectedGraphNode and DirectedGraphWeightFunction). So, basically, my "graphs" were just silly Lists of DirectedGraphNode.

Objective

Now, I have this notion that each graph node is represented simply by an integer. For example, in DirectedGraph, a node with integer ID of, say, 123 is mapped into two integer lists: one for incoming nodes (parents) and one for outgoing nodes (children).

Implementation

(If you want to run the unit tests, see this.)

AbstractGraph.java:

package net.coderodde.graph;

import java.util.Set;

/**
 * This class defines the API for graph data structures. The actual nodes are 
 * represented as integers. The client programmer should always be able to map
 * his domain specific nodes to the integers. 
 * <p>
 * Not only the query methods return a boolean value, but any other method
 * returns a boolean value indicating whether the structure of the graph has 
 * changed.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 10, 2016)
 */
public abstract class AbstractGraph {

    protected int edges;

    /**
     * Returns the number of nodes in this graph.
     * 
     * @return the size of this graph. 
     */
    public abstract int size();

    /**
     * Returns the number of edges in this graph.
     * 
     * @return the number of edges. 
     */
    public abstract int getNumberOfEdges();

    /**
     * Adds the node with ID {@code nodeId} to this graph.
     * 
     * @param nodeId the ID of the node to add.
     * @return {@code true} if the structure of this graph has changed, which is
     *         the same as that the added node was not present in the graph.
     */
    public abstract boolean addNode(int nodeId);

    /**
     * Checks whether the given node is present in this graph.
     * 
     * @param nodeId the query node.
     * @return {@code true} if the query node is in this graph. {@code false} 
     *         otherwise.
     */
    public abstract boolean hasNode(int nodeId);

    /**
     * If {@code nodeId} is present in this graph, removes all edges incident on
     * {@code nodeId}.
     * 
     * @param nodeId the node to clear.
     * @return {@code true} if the node {@code nodeId} had at least one incident
     *         edge and, thus, the structure of the graph changed.
     */
    public abstract boolean clearNode(int nodeId);

    /**
     * Removes the argument node from this graph.
     * 
     * @param nodeId the node to remove.
     * @return {@code true} only if the node was present in the graph which 
     *         means that the structure of the graph has changed.
     */
    public abstract boolean removeNode(int nodeId);

    /**
     * Creates an edge between {@code tailNodeId} and {@code headNodeId} with 
     * weight {@code weight}. It depends on the concrete implementation of this
     * abstract class what an edge {@code (tailNodeId, headNodeId)}. Two
     * possible cases are an undirected edge and a directed edge. Refer to the 
     * documentation of the implementing graph type.
     * <p>
     * If some of the input nodes are not present in this graph, it will be 
     * created silently.
     * 
     * @param tailNodeId the tail node of the edge.
     * @param headNodeId the head node of the edge.
     * @param weight the weight of the edge.
     * @return {@code true} only if the edge was not present in the graph, or
     *         the weight of the edge has changed.
     */
    public abstract boolean addEdge(int tailNodeId, 
                                    int headNodeId, 
                                    double weight);

    /**
     * Creates an edge between {@code tailNodeId} and {@code headNodeId} with
     * the default weight of 1.0. This method is a shortcut for constructing
     * (virtually) unweighted graphs.
     * 
     * @param tailNodeId the tail node of the edge.
     * @param headNodeId the head node of the edge.
     * @return {@code true}  only if the edge was not present in the graph, or
     *         the weight of the edge has changed.
     */
    public boolean addEdge(int tailNodeId, int headNodeId) {
        return addEdge(tailNodeId, headNodeId, 1.0);
    }

    /**
     * Returns a boolean value indicating whether this graph contains an edge
     * from {@code tailNodeId} to {@code headNodeId}. 
     * 
     * @param tailNodeId the tail node of the query edge.
     * @param headNodeId the head node of the query edge.
     * @return {@code true} only if the query edge is in this graph.
     */
    public abstract boolean hasEdge(int tailNodeId, int headNodeId);

    /**
     * Returns the weight of the edge {@code (tailNodeId, headNodeId)}. If the
     * query edge does not exist, returns {@link java.lang.Double#NaN}.
     * 
     * @param tailNodeId the tail node of the query edge.
     * @param headNodeId the head node of the query edge.
     * @return the weight of the edge.
     */
    public abstract double getEdgeWeight(int tailNodeId, int headNodeId);

    /**
     * Removes the edge from {@code tailNodeId} and {@code headNodeId}.
     * 
     * @param tailNodeId the tail node of the edge to remove.
     * @param headNodeId the head node of the edge to remove.
     * @return {@code true} if the target edge was in this graph, and thus is
     *         removed.
     */
    public abstract boolean removeEdge(int tailNodeId, int headNodeId);

    /**
     * Returns the set of all nodes that are children of the node 
     * {@code nodeId}. It depends on the actual graph implementation what is 
     * understood by the termin <i>child</i>. In unweighted graphs, every child 
     * is also a parent of a node, which is not necessarily true in directed 
     * graphs.
     * 
     * @param nodeId the query node.
     * @return set of nodes that are children on the argument node.
     */
    public abstract Set<Integer> getChildrenOf(int nodeId);

    /**
     * Returns the set of all nodes that are parents of the node {@code nodeId}.
     * 
     * @see #getChildrenOf(int) 
     * @param nodeId the query node.
     * @return set of nodes that are parent of the arugment node.
     */
    public abstract Set<Integer> getParentsOf(int nodeId);

    /**
     * Returns the set of all nodes stored in this graph.
     * 
     * @return the set of all nodes.
     */
    public abstract Set<Integer> getAllNodes();

    /**
     * Removes all nodes and edges from this graph.
     */
    public abstract void clear();
}

UndirectedGraph.java:

package net.coderodde.graph;

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * This class implements an undirected graph.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 10, 2016)
 */
public class UndirectedGraph extends AbstractGraph {

    private final Map<Integer, Map<Integer, Double>> map = 
            new LinkedHashMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public int getNumberOfEdges() {
        return edges;
    }

    @Override
    public boolean addNode(int nodeId) {
        if (map.containsKey(nodeId)) {
            return false;
        }

        map.put(nodeId, new LinkedHashMap<Integer, Double>());
        return true;
    }

    @Override
    public boolean hasNode(int nodeId) {
        return map.containsKey(nodeId);
    }

    @Override
    public boolean clearNode(int nodeId) {
        if (!hasNode(nodeId)) {
            return false;
        }

        Map<Integer, Double> neighbors = map.get(nodeId);

        if (neighbors.isEmpty()) {
            return false;
        }

        for (Integer neighborId : neighbors.keySet()) {
            map.get(neighborId).remove(nodeId);
        }

        edges -= neighbors.size();
        neighbors.clear();
        return true;
    }

    @Override
    public boolean removeNode(int nodeId) {
        if (!hasNode(nodeId)) {
            return false;
        }

        clearNode(nodeId);
        map.remove(nodeId);
        return true;
    }

    @Override
    public boolean addEdge(int tailNodeId, int headNodeId, double weight) {
        if (tailNodeId == headNodeId) {
            // Undirected graph are not allowed to contain self-loops.
            return false;
        }

        addNode(tailNodeId);
        addNode(headNodeId);

        if (!map.get(tailNodeId).containsKey(headNodeId)) {
            map.get(tailNodeId).put(headNodeId, weight);
            map.get(headNodeId).put(tailNodeId, weight);
            ++edges;
            return true;
        } else {
            double oldWeight = map.get(tailNodeId).get(headNodeId);
            map.get(tailNodeId).put(headNodeId, weight);
            map.get(headNodeId).put(tailNodeId, weight);
            return oldWeight != weight;
        }
    }

    @Override
    public boolean hasEdge(int tailNodeId, int headNodeId) {
        if (!map.containsKey(tailNodeId)) {
            return false;
        }

        return map.get(tailNodeId).containsKey(headNodeId);
    }

    @Override
    public double getEdgeWeight(int tailNodeId, int headNodeId) {
        if (!hasEdge(tailNodeId, headNodeId)) {
            return Double.NaN;
        } 

        return map.get(tailNodeId).get(headNodeId);
    }

    @Override
    public boolean removeEdge(int tailNodeId, int headNodeId) {
        if (!map.containsKey(tailNodeId)) {
            return false;
        }

        if (!map.get(tailNodeId).containsKey(headNodeId)) {
            return false;
        }

        map.get(tailNodeId).remove(headNodeId);
        map.get(headNodeId).remove(tailNodeId);
        --edges;
        return true;
    }

    @Override
    public Set<Integer> getChildrenOf(int nodeId) {
        if (!map.containsKey(nodeId)) {
            return Collections.<Integer>emptySet();
        }

        return Collections.<Integer>unmodifiableSet(map.get(nodeId).keySet());
    }

    @Override
    public Set<Integer> getParentsOf(int nodeId) {
        if (!map.containsKey(nodeId)) {
            return Collections.<Integer>emptySet();
        }

        return Collections.<Integer>unmodifiableSet(map.get(nodeId).keySet());    
    }

    @Override
    public Set<Integer> getAllNodes() {
        return Collections.<Integer>unmodifiableSet(map.keySet());
    }

    @Override
    public void clear() {
        map.clear();
        edges = 0;
    }
}

DirectedGraph.java:

package net.coderodde.graph;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * This class implements a directed graph.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 11, 2016)
 */
public class DirectedGraph extends AbstractGraph {

    private final Map<Integer, 
                      Map<Integer, 
                          Double>> parentMap = new LinkedHashMap<>();

    private final Map<Integer, 
                      Map<Integer, 
                          Double>> childMap = new LinkedHashMap<>();

    @Override
    public int size() {
        return parentMap.size();
    }

    @Override
    public int getNumberOfEdges() {
        return edges;
    }

    @Override
    public boolean addNode(int nodeId) {
        if (parentMap.containsKey(nodeId)) {
            return false;
        }

        parentMap.put(nodeId, new LinkedHashMap<Integer, Double>());
        childMap.put(nodeId, new LinkedHashMap<Integer, Double>());
        return true;
    }

    @Override
    public boolean hasNode(int nodeId) {
        return parentMap.containsKey(nodeId);
    }

    @Override
    public boolean clearNode(int nodeId) {
        if (!hasNode(nodeId)) {
            return false;
        }

        Map<Integer, Double> parents = parentMap.get(nodeId);
        Map<Integer, Double> children = childMap.get(nodeId);

        if (parents.isEmpty() && children.isEmpty()) {
            return false;
        }

        for (Integer childId : children.keySet()) {
            parentMap.get(childId).remove(nodeId);
        }

        for (Integer parentId : parents.keySet()) {
            childMap.get(parentId).remove(nodeId);
        }

        edges -= parents.size();
        edges -= children.size();
        parents.clear();
        children.clear();
        return true;
    }

    @Override
    public boolean removeNode(int nodeId) {
        if (!hasNode(nodeId)) {
            return false;
        }

        clearNode(nodeId);
        parentMap.remove(nodeId);
        childMap.remove(nodeId);
        return true;
    }

    @Override
    public boolean addEdge(int tailNodeId, int headNodeId, double weight) {
        addNode(tailNodeId);
        addNode(headNodeId);

        if (childMap.get(tailNodeId).containsKey(headNodeId)) {
            double oldWeight = childMap.get(tailNodeId).get(headNodeId);
            childMap.get(tailNodeId).put(headNodeId, weight);
            parentMap.get(headNodeId).put(tailNodeId, weight);
            return oldWeight != weight;
        } else {
            childMap.get(tailNodeId).put(headNodeId, weight);
            parentMap.get(headNodeId).put(tailNodeId, weight);
            ++edges;
            return true;
        }
    }

    @Override
    public boolean hasEdge(int tailNodeId, int headNodeId) {
        if (!childMap.containsKey(tailNodeId)) {
            return false;
        }

        return childMap.get(tailNodeId).containsKey(headNodeId);
    }

    @Override
    public double getEdgeWeight(int tailNodeId, int headNodeId) {
        if (!hasEdge(tailNodeId, headNodeId)) {
            return Double.NaN;
        }

        return childMap.get(tailNodeId).get(headNodeId);
    }

    @Override
    public boolean removeEdge(int tailNodeId, int headNodeId) {
        if (!childMap.containsKey(tailNodeId)) {
            return false;
        }

        if (!childMap.get(tailNodeId).containsKey(headNodeId)) {
            return false;
        }

        childMap.get(tailNodeId).remove(headNodeId);
        parentMap.get(headNodeId).remove(tailNodeId);
        --edges;
        return true;
    }

    @Override
    public Set<Integer> getChildrenOf(int nodeId) {
        if (!childMap.containsKey(nodeId)) {
            return Collections.<Integer>emptySet();
        }

        return Collections.
                <Integer>unmodifiableSet(childMap.get(nodeId).keySet());
    }

    @Override
    public Set<Integer> getParentsOf(int nodeId) {
        if (!parentMap.containsKey(nodeId)) {
            return Collections.<Integer>emptySet();
        }

        return Collections.
                <Integer>unmodifiableSet(parentMap.get(nodeId).keySet());
    }

    @Override
    public Set<Integer> getAllNodes() {
        return Collections.<Integer>unmodifiableSet(childMap.keySet());
    }

    @Override
    public void clear() {
        childMap.clear();
        parentMap.clear();
        edges = 0;
    }
}

Critique request

Is there anything I could improve/add/remove?

\$\endgroup\$
  • 2
    \$\begingroup\$ Guava 20 will include a graph library. It may be worth looking at their API for comparison/inspiration. \$\endgroup\$ – Tavian Barnes Jan 13 '16 at 18:07
2
\$\begingroup\$

I am not sure if using parent/child for in/out is a good idea. I would throw illegal argument exception from addEdge() instead of returning false for self-loops. Same with getEdgeWeight() - if user forgets to check returned value that NaN might propagate through lots of code and it will be hard to track where did it come from.

Are you sure that DirectedGraph.clearNode() updates edge count correctly? You also might consider using internal Node class for DirectedGraph, something like:

static class Node {
    Map<Integer, Double> outEdges;
    Map<Integer, Double> inEdges;
}
Map<Integer, Node> nodes;

instead of

Map<Integer, Map<Integer, Double>> parentMap;
Map<Integer, Map<Integer, Double>> childMap;

You might also want to extract common set of tests that should be valid for both UndirectedGraph and DirectedGraph instead of having just separate test files.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.