How to reverse a graph in linear time?

Question

I know there are two ways to represent my graph: one is using a matrix, and the other one is using a list.

If I use a matrix, I have to flip all the bits in the matrix. Doesn't that take O(V^2) time?

If I use a list, wouldn't I have to traverse each list, one by one, and create a new set? That would seem to take O(V+E) time which is linear. Am I correct?

So, I got another question here. Consider, for example, that I use the Dijkstra algorithm on my graph (either a matrix or a list), and we use a priority queue for the data structure behind the scene. Is there any relation of graph representation and the use of data structure? Will it affect the performance of the algorithm?

Suppose I were to use a list for representations and a priority queue for the Dijkstra algorithm, would there be a difference between matrix and use priority queue for Dijkstra?

I guess it relates to makeQueue operation only? Or they don't have different at all?

Convivial

Traversal of adjacency lists does Not Happen in linear Time in General as E=O(V^2). – Incentive

@Incentive It always happens in linear time with relation to the vertices and edges. To define time complexity only on a part of the input (i.e. just vertices) (without explicitly stating it) seems somewhat illogical, especially when the time is directly related to another part of the input (but I can't argue that many people may define it as you did). And E = O(V^2) is for dense graphs. Sparse graphs are E = O(V). – Lenity

@dukeling you are right in pointing out that reducing the 'size' of a problem to a single scalar involves a lack of precision. otoh, big-Oh notation describes the worst case and, considering graphs, without additional constraints worst case means E=O(V^2). being precise, O(V^2) is not correct for edge reversal on an adjacency matrix either - if the representation sports a flag row-major vs. col-major, transposition is O(1). – Incentive

> If I use a matrix, I have to flip all the bits in the matrix. \\ Wouldn't you want to transpose it instead? – Gomes

Answer 1

Reversing the adjacency lists of a Directed Graph can be done in linear time. We traverse the graph only once. Order of complexity will be O(|V|+|E|).

1. Maintain a HashMap of Adjaceny Lists where the key is the vertex label and the value is an ArrayList of adjacent vertices of the key vertex.
2. For reversing, create a new HashMap of the same kind. Scan the original hash map and for each key you come across, traverse the corresponding list.
3. For each vertex found in the value list, add a key in the new hashMap, putting the key of the original HashMap as an entry in the ArrayList corresponding to the new key in the new HashMap.

public static HashMap<Character,ArrayList <Character>> getReversedAdjLists(RGraph g)
{
    HashMap <Character, ArrayList<Character>> revAdjListMap = new HashMap <Character, ArrayList<Character>>();
    Set <Character> oldLabelSet = g.adjListMap.keySet();

    for(char oldLabel:oldLabelSet)
    {
        ArrayList<Character> oldLabelList = g.adjListMap.get(oldLabel);

        for (char newLabel : oldLabelList)
        {
            ArrayList<Character> newLabelList = revAdjListMap.get(newLabel);

            if (newLabelList == null)
            {
                newLabelList = new ArrayList<Character>();
                newLabelList.add(oldLabel);
            }
            else if ( ! newLabelList.contains(oldLabel))
            {
                newLabelList.add(oldLabel);
            }

            revAdjListMap.put(newLabel, newLabelList);
        }
    }

    return revAdjListMap;
}

Victorvictoria

Good answer. I was initially trying to do this with a static 2D array, but the transposition of that matrix (to accomplish reversal) is O(n^2) I am pretty sure. – Tevet

Is there any possibility of a constant space solution? Is it possible to reverse the graph in-place? – Societal

Answer 2

I think reversing the graph by traversing the list takes O(V²), since for each vertex you must add or delete (V-1) edges.

As for Dijkstra's algorithm, as I understand it, if you represent the graph as a matrix or list the algorithm takes O(V²), but some other data structures are faster. The fastest known is a Fibonacci heap, which gives O(E + VlogV).

Sear

How about if I keep two lists? The incoming edges list and outgoing edges list, this seems to be a good idea? – Convivial

@TimothyLeung: Why? I don't see how that would give any advantage over one list of outgoing edges. – Sear

@Sear I imagine it would only be O(V^2) when the graph is dense. Consider no edges. You'd only do O(1) work at every vertex, thus O(V). Thus edges has to come into play in the complexity. – Lenity

@Dukeling: are you talking about reversal or Dijkstra? – Sear

@Sear Reversal, as in reverse the direction of all the edges. It looks like you may have interpreted it as a complement operation (removing all existing edges and creating edges where there didn't exist any). Maybe this is what OP wanted, I'm not sure. – Lenity

@Dukeling: the OP said "If I use matrix, I have to flip all bits in the matrix." I inferred that he meant the complement. If he meant reversing the direction of the edges, then yes, it's O(V+E) and keeping two lists might make a difference, depending on how it's implemented. – Sear

@Beta: Keeping a second list is unnecessary. As collapsar mentioned in the comments, reversing edge directions in a matrix can be accomplished by changing from row-major to col-major indexing (or vice-versa) by simply swapping the indices on each lookup. You can use the same logic for an adjacency list and search the (reversed) destination node's list for the (reversed) source node. If an edge exists from node p to node q in the original graph, an edge exists from node q to node p in the edge-direction-reversed graph. – Cress

By the way, just in case the OP really meant complement, you can use similar tricks without duplicating or transforming the matrix/list. – Cress

Answer 3

G = {"A":["B", "C","D"],"B":["C", "E"], "C":["D", "E"],"D":[],"E":["D"] }
res ={}
for k in G.keys():
    for val in G[k]:
        if val not in res.keys():
            res[val] = [k]
        else:
            res[val].append(k)

print(res)

Lightfoot

Answer 4

Since I see a couple of comments asking about an in place graph transpose (reversal), here is my version of it. Please note this will only work on DAGs.Feedback and suggestions for improvement would be welcome

def transpose(G):
    """
    Return the transpose of a directed graph i.e. all the edges are reversed (In Place)
    """
    #note this is not a standard lib function afaik and you would have to 
    #implement topological sort but that should be easy
    topsort = topological_sort(G) 
    topsort.reverse() # we want to process starting from sink node
    for v in topsort:
        for node in G[v]:
            G[node].append(v)
        #  remove all older members of the vertex 'v'  
        G[v] = []
    print(G)

Darbee