Skip to main content

Transpose a directed graph

The problem addressed in this scenario is that of transposing a directed graph. Transposing a graph involves reversing the direction of all edges while maintaining the structure of the graph. In other words, if there was a directed edge from vertex A to vertex B in the original graph, the transposed graph will have an edge from B to A. This operation can be important in various applications involving graphs, such as pathfinding algorithms, network analysis, and more.

Problem Statement and Description

The task is to write a Java program that can transpose a given directed graph. Given a graph with nodes and directed edges, the program should reverse the direction of all edges while preserving the connections between nodes.

Example

Consider the following directed graph:

Before Transpose a directed graph 
Original Graph:
0 -> 0, 3
1 -> 0
2 -> 1
3 -> 1, 2

After transposing, the graph should become:

After Transpose a directed graph 
Transposed Graph:
0 -> 0, 1
1 -> 2, 3
2 -> 3
3 -> 0

Idea to Solve the Problem

The idea to transpose a directed graph involves reversing the direction of each edge. To achieve this, we can follow these steps:

  1. For each node in the original graph, iterate through its adjacency list.
  2. Remove the edge between the current node and its adjacent node.
  3. Add a new edge between the adjacent node and the current node in the transposed graph.

Standard Pseudocode

procedure transpose_graph(graph):
        for each node in graph:
            edges = node.adjacency_list
            node.adjacency_list = empty_list
            
            for each edge in edges:
                add_edge(transposed_graph, edge.end, node)

Algorithm Explanation

  1. The transpose_graph function takes the original graph as input.
  2. For each node in the original graph, it retrieves its adjacency list of edges.
  3. It then iterates through each edge in the adjacency list and performs the transposition:
    • Remove the edge from the current node's adjacency list.
    • Add a new edge to the transposed graph from the adjacent node to the current node.

Program Solution

//C Program 
//Transpose a directed graph
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
  };

  struct Graph
  {
    int data; //node key value
    struct AjlistNode*next;
  };
  void setData(struct Graph *);
int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
  if(node!=NULL && size>0)
  {
    int index=0;
    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else
  {
    printf("Vertic Node is Empty");
  }
}

void addEdge(struct Graph*node, int V ,int E)
{

  // create Adjacency node
  struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
    sizeof(struct AjlistNode)
    );
  if(newEdge!=NULL)
  {

    newEdge->next=NULL;
    newEdge->vId=E;

    struct AjlistNode *temp=node[V].next;

    if(temp==NULL)
    {
      node[V].next=newEdge;
    }else
    {
      //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }else
  {
    printf("\n Memory overflow");

  }
}


//Display Adjacency list of vertex
void printGraph(struct Graph*node)
{
  if(node!=NULL)
  {
    struct AjlistNode *temp=NULL;
    for(int index=0;index<size;index++)
    {
      printf("\n Adjacency list of vertex %d  :",index);
      temp=node[index].next;
      while(temp!=NULL)
      {
        //temp->vId is graph node vertices
        //in this case temp->vId is same as 
        //node[temp->vId].data

        printf("  %d",node[temp->vId].data);
        temp=temp->next;
      }
    }
  }else
  {
    printf("Empty Graph");
  }
}

//This function are add new edge
void transpose_edge(struct Graph*node,struct AjlistNode*edges,int point)
{
  struct AjlistNode*current=NULL;

  while(edges!=NULL)
  {
    current=edges;
    //visit to next edge
    edges=edges->next;

    //make sure given node is is valid
    if(current->vId < size)
    {
      //add edge to node
      current->next=node[current->vId].next;
      
      //set node key value
      node[current->vId].next=current;

      current->vId=point;

    }
  }
}
//This function are remove node edges
void transpose(struct Graph*node,int point)
{
  if(point<size)
  {
    
    struct AjlistNode *edges=node[point].next;
    //segregating the edge
    node[point].next=NULL;

    //recursively call to next node
    transpose(node,point+1);

    //This method are combine new edges
    transpose_edge(node,edges,point);
  }
}
int main()
{

  size=4;

  struct Graph*node=(struct Graph*)malloc(
    sizeof(struct Graph)*size
    );

  if(node==NULL)
  {
    printf("\n Memory overflow");
  }else
  {
    //First set node keys
    setData(node); 
    //Connected two node with Edges

    addEdge(node,0,0);
    addEdge(node,0,3);
    addEdge(node,1,0);
    addEdge(node,2,1);
    addEdge(node,3,1);
    addEdge(node,3,2);

    printf("\n Before :");
    printGraph(node);
        //Transpose graph edges
    transpose(node,0);
    printf("\n After :");
    printGraph(node);
  }  

  return 0;
}

Output

 Before :
 Adjacency list of vertex 0  :  0  3
 Adjacency list of vertex 1  :  0
 Adjacency list of vertex 2  :  1
 Adjacency list of vertex 3  :  1  2
 After :
 Adjacency list of vertex 0  :  0  1
 Adjacency list of vertex 1  :  2  3
 Adjacency list of vertex 2  :  3
 Adjacency list of vertex 3  :  0
//C++ program
//Transpose a directed graph
#include<iostream>
using namespace std;

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Vertices
{
    int data; //node key value
    struct AjlistNode*next;
};

class Graph
{
	Vertices *node;
    int size;//number of 
public:
	Graph(int);
	void setData();
	void addEdge(int,int);
	void printGraph();
	void transpose_edge(AjlistNode*,int);
	void transpose(int );
	void connect(int ,int );
};
Graph::Graph(int size)
{
	this->size = size;
    //set number of nodes
	node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
	if(node!=NULL)
	{
		int index=0;

		for(index;index<size;index++)
		{
			//set vertic node data
			node[index].data=index;//set node key
			//Initial no AjlistNode
			//set NULL Value
			node[index].next=NULL;
		}
	}
	else
	{
		cout<<"Vertic Node is Empty"<<endl;
	}
}
//Add Edge from Two given Nodes
void Graph ::connect(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    //first create Adjacency node
	AjlistNode *newEdge=new AjlistNode;

	if(newEdge!=NULL)
	{

		newEdge->next=NULL;
		newEdge->vId=E;

		AjlistNode *temp=node[V].next;

		if(temp==NULL)
		{
			node[V].next=newEdge;
		}else
		{
            //Add node at last
			while(temp->next!=NULL)
			{
				temp=temp->next;
			}      
			temp->next=newEdge;          
		}
	}

}


void Graph ::addEdge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
	if(V<size && E <size)
	{
		connect(V,E);

    }else
    {
        //not valid Vertices
    	cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}

//Display Adjacency list of vertex
void Graph::printGraph()
{
	if(node!=NULL)
	{
		AjlistNode *temp=NULL;
		for(int index=0; index < size; index++)
		{
			cout<<"\n Adjacency list of vertex "<<index<<" :";
			temp=node[index].next;
			while(temp!=NULL)
			{
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data

				cout<<" "<<node[temp->vId].data;
				temp=temp->next;
			}
		}
	}else
	{
		cout<<"Empty Graph"<<endl;
	}
}
//This function are add new edge
void Graph:: transpose_edge(struct AjlistNode*edges,int point)
{
  struct AjlistNode*current=NULL;

  while(edges!=NULL)
  {
    current=edges;
    //visit to next edge
    edges=edges->next;

    //make sure given node is is valid
    if(current->vId < size)
    {
      //add edge to node
      current->next=node[current->vId].next;
      
      //set node key value
      node[current->vId].next=current;

      current->vId=point;

    }
  }
}
//This function are remove node edges
void Graph:: transpose(int point)
{
  if(point<size)
  {
    
    AjlistNode *edges=node[point].next;
    //segregating the edge
    node[point].next=NULL;

    //recursively call to next node
    transpose(point+1);

    //This method are combine new edges
    transpose_edge(edges,point);
  }
}
int main()
{
    //Create Object
	Graph g=Graph(4);
    //First set node keys
	g.setData();

	g.addEdge(0,0);
	g.addEdge(0,3);
	g.addEdge(1,0);
	g.addEdge(2,1);
	g.addEdge(3,1);
	g.addEdge(3,2);

    cout<<("\n Before :");
    g.printGraph();
        //Transpose graph edges
    g.transpose(0);
    cout<<("\n After :");
    g.printGraph();

	return 0;
}

Output

 Before :
 Adjacency list of vertex 0 : 0 3
 Adjacency list of vertex 1 : 0
 Adjacency list of vertex 2 : 1
 Adjacency list of vertex 3 : 1 2
 After :
 Adjacency list of vertex 0 : 0 1
 Adjacency list of vertex 1 : 2 3
 Adjacency list of vertex 2 : 3
 Adjacency list of vertex 3 : 0
//Java program
//Transpose a directed graph
public class MyGraph
{

    static class AjlistNode
    {
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices
    {
        int data;
        AjlistNode next;
    }

    //number of Vertices
    static int size;
    Vertices node[];

    MyGraph(int size)
    {
        //set value
        this.size = size;
        node = new Vertices[size];
        
    }

    //set initial node value
    public void setData()
    {
        if(node == null)
        {
            System.out.println("\nEmpty Graph");
        }else
        {
            for(int index = 0; index < size; index++)
            {
                // avoid java.lang.nullPointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }
    //connect two nodes
    public void connect(int start,int end)
    {
        AjlistNode newEdge=new AjlistNode();
            newEdge.id=end;//end node
            newEdge.next=null;
            if(node[start].next==null)
            {
                node[start].next=newEdge;
            }else
            {
                AjlistNode temp=node[start].next;

                while(temp.next!=null)
                {
                    temp=temp.next;
                }
                temp.next=newEdge;
            }
    }
    //Add edge at the end
    public void addEdge(int start,int end)
    {
        if(start < size && end < size && node != null)
        {
           connect(start,end);

        }else{
            System.out.println("\nEmpty Graph");
        }
    }

    public void printGraph()
    {

        if(size>0 && node!=null)
        {
            for(int index=0;index<size;index++)
            {
                System.out.print("\nAdjacency list of vertex "+index+" :");
                
                AjlistNode temp=node[index].next;

                while(temp!=null)
                {
                    System.out.print(" "+node[temp.id].data);

                    temp=temp.next;
                }
            }
        }
    }
    //This function are add new edge
    public void  transpose_edge( AjlistNode edges,int point)
    {
       AjlistNode current = null;

      while(edges != null)
      {
        current = edges;
        //visit to next edge
        edges = edges.next;

        //make sure given node is is valid
        if(current.id < size)
        {
          //add edge to node
          current.next = node[current.id].next;
          
          //set node key value
          node[current.id].next = current;

          current.id = point;

        }
      }
    }
    //This function are remove node edges
    public void  transpose(int point)
    {
      if(point<size)
      {
        
        AjlistNode edges = node[point].next;
        //segregating the edge
        node[point].next = null;

        //recursively call to next node
        transpose(point+1);

        //This method are combine new edges
        transpose_edge(edges,point);
      }
    }

    public static void main(String[] args) 
    {
        int totalNode=4;

        MyGraph g=new MyGraph(totalNode);
        g.setData();
        //Connected two node with Edges
        g.addEdge(0,0);
        g.addEdge(0,3);
        g.addEdge(1,0);
        g.addEdge(2,1);
        g.addEdge(3,1);
        g.addEdge(3,2);

        
        System.out.print("Before :");
        g.printGraph();
        //Transpose graph edges
        g.transpose(0);
        System.out.print("\nAfter :");
        g.printGraph();

    }
}

Output

Before :
Adjacency list of vertex 0 : 0 3
Adjacency list of vertex 1 : 0
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 1 2
After :
Adjacency list of vertex 0 : 0 1
Adjacency list of vertex 1 : 2 3
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0
Transpose a directed graph in java 
#Python program
#Detect Cycle in a Undirected Graph
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]
    

  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1


  #connect two node with  edge
  def connect(self,start,end):
    new_edge=AjLinkeNode(end)
    if(self.node[start].next==None):
      self.node[start].next=new_edge
    else:
      temp=self.node[start].next
      while(temp.next!=None):
        temp=temp.next
      temp.next=new_edge  

  #add edge
  def addEdge(self,start,end):

    #start,end is two nodes
    if(self.size>start and self.size>start):
      
      self.connect(start,end)
  
    else:
      print("Invalid nodes")


  def printGraph(self):

    if(self.size>0 and self.node!=None):

      index=0

      while(index<self.size):

        print("\nAdjacency list of vertex  {0} :".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print("  {0}".format(temp.id),end=" ")

          temp=temp.next

        index+=1

  #Detect cycle using DFS
  def detectCycle(self, point, visit):


    if(visit[point] >= 1):
      visit[point]=visit[point]+1
      return
    
    visit[point]=1

    temp=self.node[point].next
    counter=0
    while(temp!=None):
      counter+=1
      self.detectCycle(temp.id,visit) 
      temp=temp.next
    

    if(counter>0):
      visit[point] = visit[point]-counter

      if(visit[point]<0):
        visit[point]=-visit[point]
        


  #This function are add new edge
  def  transpose_edge(self,edges,point):
      current = None;

      while(edges != None):
        current = edges;
        #visit to next edge
        edges = edges.next;

        #make sure given node is is valid
        if(current.id < self.size):
          #add edge to node
          current.next = self.node[current.id].next;
          
          #set node key value
          self.node[current.id].next = current;

          current.id = point;

        
      
    
    #This function are remove node edges
  def  transpose(self,point):
      if(point<self.size):
        
        edges = self.node[point].next;
        #segregating the edge
        self.node[point].next = None;

        #recursively call to next node
        self.transpose(point+1);

        #This method are combine new edges
        self.transpose_edge(edges,point);
      

    
def main():
  g=Graph(4)
  g.setData() 
  #Connected two node with Edges

  g.addEdge(0,0);
  g.addEdge(0,3);
  g.addEdge(1,0);
  g.addEdge(2,1);
  g.addEdge(3,1);
  g.addEdge(3,2);

  
  print("Before :");
  g.printGraph();
  #Transpose graph edges
  g.transpose(0);
  print("\nAfter :");
  g.printGraph();

if __name__=="__main__":
    main()

Output

Before :

Adjacency list of vertex  0 :   0   3 
Adjacency list of vertex  1 :   0 
Adjacency list of vertex  2 :   1 
Adjacency list of vertex  3 :   1   2 
After :

Adjacency list of vertex  0 :   0   1 
Adjacency list of vertex  1 :   2   3 
Adjacency list of vertex  2 :   3 
Adjacency list of vertex  3 :   0 
//C# Graph 
//Transpose a directed graph
using System;
class AjlistNode
{
	public int key;
	public AjlistNode next;
	public AjlistNode(int key)
	{
		this.key=key;
		this.next=null;
	}
}
class Node
{
	public int data;
	public AjlistNode next;
	public Node(int data)
	{
		this.data=data;
		this.next=null;

	}
}
class MyGraph
{
	//empty array
	public Node[]node= new Node[] {};
	public int size;
	public MyGraph(int size)
	{
		this.size=size;
		node=new Node[size];
	}
	//set initial node value
	public void setData()
	{
		if(node == null)
		{
			Console.WriteLine("\nEmpty Graph");
		}else
		{
			for(int index = 0; index < size; index++)
			{
				// avoid java.lang.nullPointerException
				node[index]=new Node(index); 

			}
		}
	}
	//connect two nodes
	public void connect(int start,int end)
	{
		AjlistNode newEdge=new AjlistNode(end);

		if(node[start].next==null)
		{
			node[start].next=newEdge;
		}else
		{
			AjlistNode temp=node[start].next;

			while(temp.next!=null)
			{
				temp=temp.next;
			}
			temp.next=newEdge;
		}
	}
	//Add edge at the end
	public void addEdge(int start,int end)
	{
		if(start < size && end < size && node != null)
		{
			connect(start,end);

		}else{
			Console.WriteLine("\nEmpty Graph");
		}
	}

	public void printGraph()
	{

		if(size>0 && node!=null)
		{
			for(int index=0;index<size;index++)
			{
				Console.Write("\nAdjacency list of vertex "+index+" :");

				AjlistNode temp=node[index].next;

				while(temp!=null)
				{
					Console.Write(" "+node[temp.key].data);

					temp=temp.next;
				}
			}
		}
	}
	//This function are add new edge
	public void  transpose_edge( AjlistNode edges,int point)
	{
		AjlistNode current = null;

		while(edges != null)
		{
			current = edges;
			//visit to next edge
			edges = edges.next;

			//make sure given node is is valid
			if(current.key < size)
			{
				//add edge to node
				current.next = node[current.key].next;

				//set node key value
				node[current.key].next = current;

				current.key = point;

			}
		}
	}
	//This function are remove node edges
	public void  transpose(int point)
	{
		if(point<size)
		{

			AjlistNode edges = node[point].next;
			//segregating the edge
			node[point].next = null;

			//recursively call to next node
			transpose(point+1);

			//This method are combine new edges
			transpose_edge(edges,point);
		}
	}

}
class Program
{

	static void Main(string[] args)
	{
		//create object
		MyGraph g=new MyGraph(4);
		g.setData();
		//Connected two node with Edges



		g.addEdge(0,0);
		g.addEdge(0,3);
		g.addEdge(1,0);
		g.addEdge(2,1);
		g.addEdge(3,1);
		g.addEdge(3,2);


		Console.Write("Before :");
		g.printGraph();
		//Transpose graph edges
		g.transpose(0);
		Console.Write("\nAfter :");
		g.printGraph();

	}
}

Output

Before :
Adjacency list of vertex 0 : 0 3
Adjacency list of vertex 1 : 0
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 1 2
After :
Adjacency list of vertex 0 : 0 1
Adjacency list of vertex 1 : 2 3
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0

<?php 
/*
* PHP Program 
* Transpose a directed graph
*/

class AjlistNode
{
  public $key;
  public $next;
  function __construct($key)
  {
    $this->key=$key;
    $this->next=NULL;
}
}
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;

}
}
class MyGraph
{

    public $node;
    public $size;
    function __construct($size)
    {
        $this->size=$size;
        $this->node=[];  //empty array
    }
    public function setData()
    {
        if($this->size>0)
        {
            for($index=0;$index<$this->size;$index++)
            {
                $this->node[$index]=new Node($index);
            }

        }
    }
    public function connect($start,$end)
    {
        $newEdge=new AjlistNode($end);
        if($this->node[$start]->next==NULL)
        {
            $this->node[$start]->next=$newEdge;
        }
        else
        {

            $temp=$this->node[$start]->next;
            while($temp->next!=NULL)
            {
                $temp=$temp->next;
            }
            $temp->next= $newEdge;
        }
    }
    public function addEdge($start,$end)
    {
        if($this->size > $start && $this->size>$end)
        {
            $this->connect($start,$end);

        }
        else
        {
            echo "\n Invalid node";
        }
    }
    public function printGraph()
    {
        if($this->size>0 && count($this->node)>0 && $this->node!=NULL)
        {
            for($index=0;$index<$this->size;$index++)
            {
                echo ("\nAdjacency list of vertex ".$index." : ");
                $temp=$this->node[$index]->next;
                while($temp!=NULL)
                {
                    echo (" ".$this->node[$temp->key]->data);
                    $temp=$temp->next;
                }
            }
        }
    }
        //This function are add new edge
    public function  transpose_edge( $edges,$point)
    {
       $current = null;

      while($edges != null)
      {
        $current = $edges;
        //visit to next edge
        $edges = $edges->next;

        //make sure given node is is valid
        if($current->key < $this->size)
        {
          //add edge to node
          $current->next = $this->node[$current->key]->next;
          
          //set node key value
          $this->node[$current->key]->next = $current;

          $current->key = $point;

        }
      }
    }
    //This function are remove node edges
    public function  transpose($point)
    {
      if($point<$this->size)
      {
        
        $edges = $this->node[$point]->next;
        //segregating the edge
        $this->node[$point]->next = null;

        //recursively call to next node
        $this->transpose($point+1);

        //This method are combine new edges
        $this->transpose_edge($edges,$point);
      }
    }

}


function main()
{
    //create object
    $g=new MyGraph(4);
    $g->setData();

    //Connected two node with Edges
    $g->addEdge(0,0);
    $g->addEdge(0,3);
    $g->addEdge(1,0);
    $g->addEdge(2,1);
    $g->addEdge(3,1);
    $g->addEdge(3,2);

    
    print("Before :");
    $g->printGraph();
    //Transpose graph edges
    $g->transpose(0);
    print("\nAfter :");
    $g->printGraph();

}
main();
?>

Output

Before :
Adjacency list of vertex 0 :  0 3
Adjacency list of vertex 1 :  0
Adjacency list of vertex 2 :  1
Adjacency list of vertex 3 :  1 2
After :
Adjacency list of vertex 0 :  0 1
Adjacency list of vertex 1 :  2 3
Adjacency list of vertex 2 :  3
Adjacency list of vertex 3 :  0

Time Complexity

The iteration through each node and its adjacency list takes O(V + E) time, where V is the number of vertices and E is the number of edges.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment