CODEWITHSUNDEEP
algorithmgraphcycle
Philip
Philip

Reputation: 63

Finding all cycles with weight > 0 in a special directed graph

I'm looking for an algorithm to find all cycles with a total weight of all its edges that is greater than 0. I heard that this problem is NP-complete, but since I want to solve this for a special graph that always looks more or less the same, I hope there is an easier method.

My graph looks like this:

It always is a square of n * n vertices and edges between all horizontally and vertically adjacent vertices. There are just two possible weights, for black edges -1 and for the green ones its +1.

For this example the cycles I'm looking for would be:

What would be an efficient algorithm for this task? It should be quite fast, because I also want to do this for graphs with n = 25 => 625 vertices.

Upvotes: 2

Views: 337

Answers (1)

haltode
haltode

Reputation: 618

Why not using a basic cycle detection with a DFS and some modifications to it :

  • When you encounter a node, if you're already visiting this same node, you know that you're in a cycle so you check if the weight is positive, if so just go through the cycle again to keep the path in memory.
  • If the node you're visiting has already been seen just stop here.
  • Then recursively visit the node's neighbour.

The pseudo-code might look like this :

dfs(node, weight):
     if state[node] is "in progress" AND weight > 0
         // This is a cycle we want
         Keep in memory the path (just go throught the cycle once more)
     if state[node] is "visited"
         Stop

     state[node] = "in progress"
     For each neighbour
         dfs(neighbour, weight + edge_weight)
     state[node] = "visited"

If you do that for each starting node, you should get a complexity in time of approximately O(N * M) with N the number of vertices and M the number of edges.

Hope this helps !

EDIT : forgot to update the state

Upvotes: 1

Related Questions