Reverse the directed graph

Question

I have to reverse a given directed graph, so that the vertices remain the same, but edges are in opposite direction. My graph is represented with a Graph class, which contains an ArrayList of vertices, and each Vertex object has it's number and ArrayList of it's adjacent vertices. My code gives wrong answer, because in each iteration of loop, vertex's adjacent list's size changes. How can I fix my code?

public void reverse() {
    ArrayList < Vertex > adjacentOfi = new ArrayList < Vertex > ();
    int k;
    for (int i = 1; i < verticesSize; i++) {
        adjacentOfi = vertices.get(i).getAdjacent();
        for (int j = 0; j < adjacentOfi.size(); j++) {
            k = adjacentOfi.get(j).getNumber();
            adjacentOfi.remove(j);
            vertices.get(k).getAdjacent().add(vertices.get(i));
        }
    }
}

Here is Vertex class

public class Vertex {
    private int number;
    private boolean marked;
    private int finishingTime;
    private ArrayList<Vertex> adjacent;

    public Vertex(int num) {
        this.number = num;
        this.marked = false;
        this.finishingTime = 0;
        this.adjacent = new ArrayList<Vertex>();
    }
}

plus of course it's getters and setters. Problem is that when the loops starts from Vertex number 1, and it's adjacency list contains Vertex 5, it adds 1 to 5's adjacency list and deletes 5 from 1's adjacency list. Next time, when loop reaches 5, it adds 5 to 1'a adjacency list and deletes 1 from 5's adjacency list. I need to maintain the initial size of each list, before the loop modifies it.

Answer 1

Goal: performing an atomic operation one time on every edge in a graph.

Pseudocode:

function reverse(graph G)
    v = any vertex in G
    reverseVertex(v)
end function

function reverseVertex(vertex v)
    mark v as visited
    E = set of all outward edges from v
    N = { } // empty set, will contain all neighbors
    for each edge e in E,
         q = vertex reached by e from v
         if q is not visited,
             add q to N
             reverse direction of e
         end if
    end for

    for each vertex q in N,
         reverseVertex(q)
end function

What you should do: Since I assume you're a student with an assignment (usually the case with questions beginning with "I have to..."), I'll quickly explain my pseudocode so you get the overarching idea and have the ability to implement it yourself.

You can't just loop through the vertices and reverse each edge, because reversing an edge makes it an outgoing edge to some other vertex, and if you haven't looked at that other vertex yet with your loop, you'll end up reversing it again, which will result in the edge being the same direction as it started. Or, you'll have already looked at the other vertex, in which case it will be fine. But both possibilities exist if you're looping randomly through the vertices, so looping randomly through all the vertices doesn't work.

A more intuitive solution would be to start at any vertex in the graph, and label it visited. Then, for each unvisited neighbor of the vertex, add the neighbor to a list and reverse the edge going to the neighbor (i.e. by deleting it and adding it as you've done in your code). Then, call this function recursively on all the neighbors in the list of unvisited neighbors. Eventually, the recursive calls will terminate once you reach a vertex with all of its neighbors visited, or a leaf. I'm sure that an inductive proof of this algorithm wouldn't be too hard to come up with.

Hope this helps!

Answer 2

Don't change your Graph representation, but build a new one.

If it is a requirement that you actually change the Graph object, you should still create a new set of adjacency lists and in the final step replace the original lists with the new ones

Answer 3

basically you have to make a temporary new list for the reversed vertices and only after all have been reversed exchange them for the original list. The list used as iterator for the for loop should never change as long as the for loop is running.

Also where do you get the verticesSize and vertices object from? It should be given as parameter, even if it is a class parameter, in which case at least it should be called by this.vertices and this.verticesSize. The last one should also be avoided and always calculated right before usage from the current list object ...

Answer 4

Here is one implementation based on the algorithm mentioned in https://stackoverflow.com/a/15084366/574776

static class Vertex {
    final int data;
    final List<Edge> edges;
}

static class Edge {
    Vertex source, destination;

    public void reverse() {
        source.edges.remove(this);
        destination.edges.add(this);

        Vertex temp = source;
        source = destination;
        destination = temp;
    }
}

static class Graph {
    final Map<Integer, Vertex> vertices;

    public Vertex getVertex(Integer data) {
        if (!vertices.containsKey(data)) {
            vertices.put(data, new Vertex(data));
        } 

        return vertices.get(data);
    }

    public void addEdge(Vertex source, Vertex destination) {
        Edge e = new Edge(source, destination);
        source.edges.add(e);
    }

    public void reverse() {
        System.out.println("reversing graph ... ");
        BitSet visited = new BitSet(vertices.size() + 1);
        for (Vertex v : vertices.values()) {
            if (!visited.get(v.data)) {
                reverse(v, visited);
            }
        }
    }

    private void reverse(Vertex v, BitSet visited) {
        if (DEBUG)  System.out.println("reversing " + v);
        visited.set(v.data);
        List<Vertex> neigbors = new ArrayList<Vertex>();
        List<Edge> toReverse = new ArrayList<Edge>();
        for (Edge e : v.edges) {
            Vertex destination = e.destination;
            if (!visited.get(destination.data)) {
                neigbors.add(destination);
            }
            toReverse.add(e);
        }

        for (Vertex n : neigbors) {
            reverse(n, visited);
        }

        for (Edge e : toReverse) {
            e.reverse();
        }

        if (DEBUG)  System.out.println("reversed " + v);
    }
}