7.1. Implementation

This section describes how to implement a graph structure.

Types of Graphs

There are several types of graphs:

Can we represent undirected graphs using an implementation of directed graphs?

Edge

Let us create the Edge class representing a directed edge under the graph package:

public class Edge implements Comparable<Edge> {
    private int source;
    private int target;
    private double weight;

    public Edge(int source, int target, double weight) {
        init(source, target, weight);
    }

    public Edge(int source, int target) {
        this(source, target, 0);
    }

    public Edge(Edge edge) {
        this(edge.getSource(), edge.getTarget(), edge.getWeight());
    }
}

• L1: inherits the Comparable interface.

• L2-3: the source and target vertices are represented by unique IDs in int.

• L10: constructor overwriting.

• L14: copy constructor.

Let us the define the init() method, getters, and setters:

private void init(int source, int target, double weight) {
    setSource(source);
    setTarget(target);
    setWeight(weight);
}

public int getSource() { return source; }
public int getTarget() { return target; }
public double getWeight() { return weight; }

public void setSource(int vertex) { source = vertex; }
public void setTarget(int vertex) { target = vertex; }
public void setWeight(double weight) { this.weight = weight; }
public void addWeight(double weight) { this.weight += weight; }

Let us override the compareTo() method that compares this edge to another edge by their weights:

@Override
public int compareTo(Edge edge) {
    double diff = weight - edge.weight;
    if (diff > 0) return 1;
    else if (diff < 0) return -1;
    else return 0;
}

• L4: returns 1 if the weight of this edge is greater.

• L5: returns -1 if the weight of the other edge is greater.

• L6: returns 0 is the weights of both edges are the same.

Graph

Let us create the Graph class under the graph package:

public class Graph {
    private final List<List<Edge>> incoming_edges;

    public Graph(int size) {
        incoming_edges = Stream.generate(ArrayList<Edge>::new).limit(size).collect(Collectors.toList());
    }
    
    public Graph(Graph g) {
        incoming_edges = g.incoming_edges.stream().map(ArrayList::new).collect(Collectors.toList());
    }
    
    public boolean hasNoEdge() {
        return IntStream.range(0, size()).allMatch(i -> getIncomingEdges(i).isEmpty());
    }
    
    public int size() {
        return incoming_edges.size();
    }
}

• L2: a list of edge lists where each dimension of the outer list indicates a target vertex and the inner list corresponds to the list of incoming edges to that target vertex.

• L5: creates an empty edge list for each target vertex.

• L9: copies the list of edge lists from g to this graph.

• L13: returns true if all incoming edge lists are empty using the allMatch() method.

• L17: the size of the graph is the number of vertices in the graph.

For example, a graph with 3 vertices 0, 1, and 2 and 3 edges 0 -> 1, 2 -> 1, and 0 -> 2, the incoming_edges is as follows:

incoming_edges.set(0, new ArrayList());
incoming_edges.set(1, new ArrayList(new Edge(0, 1), new Edge(2, 1));
incoming_edges.set(2, new ArrayList(new Edge(0, 2)));

Let us define setters for edges:

public Edge setDirectedEdge(int source, int target, double weight) {
    List<Edge> edges = getIncomingEdges(target);
    Edge edge = new Edge(source, target, weight);
    edges.add(edge);
    return edge;
}

public void setUndirectedEdge(int source, int target, double weight) {
    setDirectedEdge(source, target, weight);
    setDirectedEdge(target, source, weight);
}

• L2-4: retrieves the incoming edge list of target, and adds the new edge to the edge list.

• L9-10: add edges to both directions.

Let us then define getters:

public List<Edge> getIncomingEdges(int target) {
    return incoming_edges.get(target);
}

public List<Edge> getAllEdges() {
    return incoming_edges.stream().flatMap(List::stream).collect(Collectors.toList());
}

public Deque<Integer> getVerticesWithNoIncomingEdges() {
    return IntStream.range(0, size()).filter(i -> getIncomingEdges(i).isEmpty()).boxed().collect(Collectors.toCollection(ArrayDeque::new));
}

• L6: uses the flatMap() method that merges the list of edge lists into one list of edges.

• L10: uses the filter() and boxed() methods to find vertices with no incoming edges.

What is the worst-case complexity of the getVerticesWithNoIncomingEdges() method?

Let us define the getOutgoingEdges() method that returns the list of outgoing edges:

public List<Deque<Edge>> getOutgoingEdges() {
    List<Deque<Edge>> outgoing_edges = Stream.generate(ArrayDeque<Edge>::new).limit(size()).collect(Collectors.toList());

    for (int target = 0; target < size(); target++) {
        for (Edge incoming_edge : getIncomingEdges(target))
            outgoing_edges.get(incoming_edge.getSource()).add(incoming_edge);
    }

    return outgoing_edges;
}

• L1: returns a list of edge deque, where each dimension in the outer list represents the deque of outgoing edges for the corresponding source vertex.

• L2: generates the list of empty edge deques.

• L4-7: visits every target vertex to retrieve the incoming edge lists, and assigns edges to appropriate source vertices.

What is the worst-case complexity of the getOutgoingEdges() method?