> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/graphs/implementation.md).

# 7.1. Implementation

## Types of Graphs

There are several types of graphs:

{% embed url="<https://www.slideshare.net/jchoi7s/types-of-graphs-238933861>" %}

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

## Edge

Let us create the [`Edge`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/Edge.java) class representing a directed edge under the [`graph`](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/graph) package:

```java
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`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/Comparable.html) 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:

```java
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:

```java
@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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/Graph.java) class under the [`graph`](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/graph) package:

```java
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()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/stream/Stream.html#allMatch\(java.util.function.Predicate\)) 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:

```java
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:

```java
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:

```java
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()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/stream/Stream.html#flatMap\(java.util.function.Function\)) method that merges the list of edge lists into one list of edges.
* `L10`: uses the [`filter()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/stream/Stream.html#filter\(java.util.function.Predicate\)) and [`boxed()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/stream/IntStream.html#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:

```java
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?