4 Replies - 545 Views - Last Post: 04 September 2017 - 12:08 AM

#1 Patras  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 01-September 17

Solving a graph problem

Posted 02 September 2017 - 12:10 AM

Hi everybody! I'm in trouble solving this problem:

Given an undirected graph G=(N,A), where every vertex is colored with red or blue, and two red vertexes from N are: r and s.

1) We want to verify the existence of a path from r to s containing only red vertexes. Write the pseudo code for an optimal time algorithm.

2) We want to verify in general the existence of a cycle in that graph that contains only red edges. Write the pseudo code for an optimal time algorithm.


My solution:
I'm not looking for the code but just for any idea for the algorithm. I found a very rough way to verify these conditions so would like to hear your opinion.

1) Start from r and keep on visiting only the red nodes (using some edge lists or whatever) through the connected edges, everytime writing something like "VISITED" switching from the previous state "UNEXPLORED". If there aren't unexplored red nodes anymore and s still hasn't been visited, there doesn't exist such a path.

2) Visit the whole graph through BFS until you get to a CROSS edge. If both of its nodes are red, choose one, save the state "START" and keep on visiting all the red nodes connected until you get to the "START", If at the end start node wasn't found, then change it to UNEXPLORED and start everything again from a different cross edge.

Would these ideas work? I'm not sure about the second but I think the solution for the first one isn't that bad.

Is This A Good Question/Topic? 0
  • +

Replies To: Solving a graph problem

#2 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Solving a graph problem

Posted 02 September 2017 - 05:15 PM

Moved to Computer Science.

Your problem statements are ambiguous. You state:

Quote

We want to verify...


In the context of algorithm analysis, a verification algorithm is used to check that a "good" object satisfies the desired property, not whether an arbitrary object satisfies the desired property. We feed the algorithm as input an object satisfying the property, as well as a certificate which serves as evidence that the object indeed satisfies said property. Roughly speaking, a verification algorithm serves the purpose of "here is the problem statement and my work- can you check that it is correct?"

So for Part 1, a verification algorithm should accept as input the following:
  • A graph G(N, A)
  • A two coloring of the vertices, f : N -> { R, B }, in which at least two vertices are colored red
  • Two red vertices r and s
  • An r-s path P in G, using only red vertices


Then the verification algorithm actually checks that P is a path and only visits red vertices.

Your solution for Part 1 is correct, but it solves the following decision problem:
INSTANCE: A graph G(N, A), a two coloring of the vertices f : N -> {R, B} in which at least two vertices are colored red, and two red vertices r and s.

DECISION: Does G contain an r-s path visiting only red vertices?



Part 2) Again- do you want a verification algorithm to check that a graph G(N, A) with two-coloring f : N -> {R, B} and a red-cycle actually has a red cycle? Or do you want to determine if graph G(N, A) with a two-coloring f : N -> {R, B} has a red cycle?

If you are interested in the latter, I would suggest considering the induced subgraph of G, restricted to the red vertices. Then your problem comes down to checking for a cycle in a graph.

As for your answer, I do not know what a CROSS edge is. This is not standard graph theory terminology.
Was This Post Helpful? 0
  • +
  • -

#3 Patras  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 01-September 17

Re: Solving a graph problem

Posted 03 September 2017 - 01:01 AM

Thanks for the reply! By verify I mean finding out if there's such a cycle. I don't know from the beginning whether it exists or not and I don't need any reference to the nodes the cycle is made of. (Result: only TRUE or FALSE)
I hope to be clear and sorry about that I'm not from an anglo saxon country.

View Postmacosxnerd101, on 02 September 2017 - 05:15 PM, said:

As for your answer, I do not know what a CROSS edge is. This is not standard graph theory terminology.


We used to call CROSS the edges that during a BFS bring you from the node you're visiting to a node that has already been visited. It's due to the fact that these edges weren't still visited but their opposit nodes were. If you try to watch a graph in this condition you see that these are the edges that shouldn't be in a tree, because they would connect two sibilings (or children) forming a cycle. I've just read my post and I didn't explain it well enough:
This would help me to find a cycle but I should visit all the red nodes related to find out if there's a "red cycle". If there isn't: visit the next cross edge the same way after marking the cross edge I've already visited by something like "NO WAY" so this would help for the next steps, until there aren't cross edges left.
I could detect every cross and denominate them like this during a first traversal of the whole graph.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Solving a graph problem

Posted 03 September 2017 - 08:32 AM

Quote

Thanks for the reply! By verify I mean finding out if there's such a cycle. I don't know from the beginning whether it exists or not and I don't need any reference to the nodes the cycle is made of. (Result: only TRUE or FALSE)

Got it. :)


Quote

This would help me to find a cycle but I should visit all the red nodes related to find out if there's a "red cycle". If there isn't: visit the next cross edge the same way after marking the cross edge I've already visited by something like "NO WAY" so this would help for the next steps, until there aren't cross edges left.
I could detect every cross and denominate them like this during a first traversal of the whole graph.

This still sounds expensive, and also a little vague. I think you're getting too mired down in the implementation details far too early. Look at my suggestion for Part 2. Notice how I describe a very high level procedure that highlights precisely the steps that need to be accomplished. By the same token, I don't describe in implementation-level detail how to accomplish those steps. When you formulate algorithms, start at the same level of abstraction I did. If you need to add more details after that, do so later.
Was This Post Helpful? 0
  • +
  • -

#5 Patras  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 01-September 17

Re: Solving a graph problem

Posted 04 September 2017 - 12:08 AM

Thanks for the reply. Well yes my procedure was in an unconvenient order. I could first create a "red graph" like you said, and then find a cross edge. This would be enough. :^:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1