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 theComparable
interface.L2-3
: the source and target vertices are represented by unique IDs inint
.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
: returns1
if the weight of this edge is greater.L5
: returns-1
if the weight of the other edge is greater.L6
: returns0
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 fromg
to this graph.L13
: returns true if all incoming edge lists are empty using theallMatch()
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 oftarget
, 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 theflatMap()
method that merges the list of edge lists into one list of 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?
Last updated
Was this helpful?