Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)?
similar question here
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Note that for an undirected graph, the adjacency matrix is symmetric, i.e.
A[i,j] == A[j,i].
From this, we can see that we can simply compute the new value of
A[i,j] = A[j,i] depending if
A[j,i] is set. Assuming the graph is unweighted, we can do:
for i from 0 to n-1 for j from 0 to i if A[i,j] == 1 OR A[j,i] == 1 A[i,j] = A[j,i] = 1 else A[i,j] = A[j,i] = 0
Note that we only have to consider 1 + 2 + 3 + ... + n-1 entries since the resultant adjacency matrix is symmetric.
If we have a weighted graph, we now have the problem of which edge weight to take as the new undirected graph edge weight. For example, if w(2,5) = 5 but w(5,2) = 10, the resultant edge weight is ambiguous. However, this is enough for you to figure out what else you need from here.