CODEWITHSUNDEEP
algorithmgraph-algorithmundirected-graph
MAG
MAG

Reputation: 3075

cycle detection undirected graph with unused edges

I have an undirected graph with edges. Each edge has certain properties like one of edge between Point A and Point B is 

{
travelTime :10hours
travelPath : air
}

Another between Point C and Point D could be 

{
travelTime :1hours
travelPath : Metro
}

We are given such a graph and known travelPaths

 {air, Metro,Rail, Bus ,Auto,Rickshaw  }

A set of edges say unUsedEdges which are not part of the fixed graph are provided to us . They also hold the above properties just that they do not belong to the fixed graph . Now an edge from unUsedEdges is added in this fixed graph . We have to tell is there a cycle of only Metro and Rail types which includes this newly introcduced edge. Then the newly introduced edge is removed and we check with another edge from unUsedEdges . If there is a cycle we need the cycle edges . we need all the cycles from all the unUsedEdges edges.

The fixed graph is big. The unUsedEdges set is big too . We can use DFS to detect cycle in an undirected graph in O(V+E) time . Repeatedly doining this for all unUsedEdges is taking time .

Is there a faster appraoch ?

Upvotes: 0

Views: 135

Answers (1)

kaya3
kaya3

Reputation: 51102

Since you want to detect cycles of only metro or only rail edges, we can simplify the problem by running the algorithm with just the metro edges first, then just the rail edges. So an algorithm which works without the different edge classes can be trivially adapted to the full problem.

The reduced problem can be solved using a variation of the disjoint-set data structure. We can insert the fixed edges into the data structure, then query (without inserting) each new edge. This tells us whether a cycle exists, but we need to augment the data structure if we want to recover the cycle.

Maintain two parent-pointer arrays in the data structure: one as normal for the disjoint-union data structure using path compression, and one without path-compression. The one without path-compression must maintain the invariant property that each (directed) edge in the parent-pointer tree is an (undirected) edge of the original graph; this means sometimes the directions of edges need to be flipped in order to re-root the tree for a union operation.

When testing a non-fixed edge, we use the path-compressed array to query whether there is a cycle, and if so, we recover it by following both vertices in the other array to their lowest common ancestor in the parent-pointer tree. This works because the edges in the uncompressed array are all edges from the original fixed graph, and a cycle including the unfixed edge can be formed from that edge, plus the two paths from each of its vertices to the common ancestor.

The overall running time is O(m α(v) + v² + nv) in the worst case, where v is the number of vertices, m is the number of fixed edges, n is the number of non-fixed edges, and α is the very-slowly-growing inverse Ackermann function.

  • The m α(v) term is the cost of O(m) "find" queries on the union-find data structure. There are another O(n) "find" queries performed, but the term for those is dominated by nv.

  • The v² term is the cost of re-rooting trees in the uncompressed array up to O(v) times, flipping up to O(v) edges each time in the worst case.

  • The nv term is the size of the output in the worst case; there could be up to n cycles, and each could have length up to v. If most unfixed-edges don't create cycles, and/or the cycles are usually short relative to v, then the running time will be significantly faster. The algorithm is output-sensitive in this sense.

Upvotes: 0

Related Questions