Remove transitive edges in graph

Question

I have a graph

Since I can go from 1 to 2 to 3 (i.e. from 1 to 3 through 2), the edge from 1 to 3 is unnecessary.

Therefore, I want to remove the edge directly between 1 and 3.

How would I do this? I guess I should do breadth-first search to decide where I can go from 1.

So if I have all my nodes and edges

nodes = [1, 2, 3]
edges = [
  {source: 1, target: 2},
  {source: 1, target: 3},
  {source: 2, target: 3}
]

I want to remove

  {source: 1, target: 3},

since it is unnecessary because of transitivity, but how could I determine whether I should remove

  {source: 1, target: 3},

instead of

  {source: 2, target: 3}

?

Minimum spanning tree of a digraph: http://stackoverflow.com/questions/21991823/finding-a-minimum-spanning-tree-on-a-directed-graph — Dave, Nov 23 '16 at 17:57

score 0 · Answer 1 · answered Nov 23 '16 at 17:57

0

You are looking for the transitive reduction of the graph, this article should help.

answered Nov 23 '16 at 17:57

hbejgel

I have already implemented a BFS. Would it be possible to use it for this? – Jamgreen Nov 23 '16 at 20:30
BFS can help you achieving the solution, but you will need more than that. – hbejgel Nov 24 '16 at 03:42

1 Answers1