# 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: ``````Original Graph:
0 -> 0, 3
1 -> 0
2 -> 1
3 -> 1, 2``````

After transposing, the graph should become: ``````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:

for each edge in edges:

## 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)
{

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
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");

}
}

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)
{
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

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 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
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
{
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;
}
}

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)
{
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();

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].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;
}
}
{
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)
{
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

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`````` ``````#Python program
#Detect Cycle in a Undirected Graph
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):
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

#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):
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

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;
}
}
{
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)
{
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

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;
}
}
{
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)
{
\$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

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.

## 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.