Contents

1. Implementation

2. Cycle Detection

3. Topological Sorting

4. Quiz

References

• Cycle Detection

• Topological Sorting

Implementation

• Create the GraphQuiz class under the graph package.

• Update the numberOfCycles() method that returns the number of all cycles in the graph.

• Make sure to find all atomic cycles; do not count cycles that can be created by simply combining other cycles.

Report

Write a report quiz6.pdf that includes the followings:

• Explain the worst-case complexity of the algorithm for your numberOfCycle() method.

• For the topological_sort() method in the Graph class, explain why the condition for the exception indicates that the graph includes a cycle.

A cycle in a graph can be detected by traversing through the graph:

Let us define the containsCycle() method under the Graph class that returns true if the graph contains any cycle; otherwise, false:

• L2: initially all vertices are not visited.

• L4: iterates until all vertices are visitied:

  • L5-6: if the recursive call finds a cycle, returns true.

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

• L2-3: marks the target vertex visited.

• L5: for each incoming edge of the target vertex:

  • L6-7: returns true if the source vertex of this edge has seen before.

  • L9-10: returns true if the recursive call finds a cycle.

Why do we need to pass the new HashSet for every call in L5?

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?

The task of topological sorting is to sort vertices in a linear order such that for each vertex, all target vertices associated with its incoming edges must appear prior to it.

By Incoming Scores

The followings demonstrate how to perform a topological sort by incoming scores, where the incoming score of a vertex is define as the sum of all source vertices:

By Depth-First

The followings demonstrate how to perform a topological sort by depth-first traversing:

Implementation

Let us define the topological_sort() method under the Graph class that performs topological sort by either incoming scores or depth-first search:

• L2: starts with vertices with no incoming edges.

• L3: retrieves outgoing edges of each source vertex.

• L4: consists of the list of vertices in topological order.

• L6: iterates until no more vertex to visit:

  • L8-9: adds a source vertex to order.

  • L12: iterates through all the outgoing edges of the source vertex:

    • L17: removes the outgoing edge from the graph.

    • L20-21: adds the target vertex if it has no incoming edge left to local.

  • L25-27: adds all vertices in local to global.

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