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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/graphs/implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.