#If anyone is knowledgeable on graphs, pls take a look at this problem

27 messages · Page 1 of 1 (latest)

runic niche
#

I am trying to solve this problem, I have already constructed my answer, just dont know if it is correct.

Suppose you are in a rock climbing competition, where the goal is to find a route on the climbing wall that uses as many different holds as possible, using only transitions that have been explicitly allowed by the route-setter. Say the climbing wall has n holds. You are given a list of m pairs (x, y) of holds, each indicating that moving directly from hold x to hold y is allowed; however, moving directly from y to x is not allowed unless the list also includes the pair (y, x). You need to figure out a sequence of allowed transitions that uses as many holds as possible, since each new hold increases your score by one point. The rules allow you to choose the first and last hold in your climbing route. The rules also allow you to use each hold as many times as you like; however, only the first use of each hold increases your score. So for example, if the legal transitions are (1, 2), (2, 1), and (3, 1), then (3, 1, 2, 1, 2, 1) would
be a valid sequence of holds getting a score of 3.

Problem: Describe and analyze an algorithm to solve the climbing problem with no restrictions on the input graph. (Hint: use the linear-time algorithm for finding all SCCs.)```
Answer:

  1. Find all SCCs in the input graph using Kosaraju's algorithm.

  2. Construct a sequence of holds for each SCC by applying something like topological sorting to each SCC separately.

  3. Combine the sequences of holds obtained for each SCC to form a single sequence that visits all holds in the graph.```

bright fern
#

your idea is nearly correct though

#

Why not draw out a simple graph and test it out? Make a few SCCs and then connect them up

runic niche
bright fern
#

I'm not sure what you mean; the question asks for

figure out a sequence of allowed transitions that uses as many holds as possible
and some holds are mutually exclusive

#

am I misunderstanding?

runic niche
#

wait if the goal is to maximize the number of holds visited, isn't the first answer I sent correct? to answer the previous concern of "you can't necessarily visit every hold in the graph", cant I just skip over these?

#

if a hole has no outgoing edges I don't include it in the sequence

bright fern
#

more precicely, you can't necessarily visit every SCC

#

yeah, the idea is right, just make sure to clarify how you handle that case

#

and justify the order and manner in which you traverse the SCCs

runic niche
#

as for the order, i thought saying topologically sorting it was justifying how I traverse the SCCs

bright fern
#

you can't visit every SCC (e.g. if you visit the bottom-middle one you can't visit the upper-right one, and vice versa), so you have to specify which SCCs you're going to visit and how you're going to get from one SCC to the next

runic niche
#

Unless I’m thinking of this incorrectly

bright fern
#

(there's nothing saying you can move from one node directly to the next in a topologically sorted graph)

bright fern
#

try your algorithm out on this graph

Graph_Condensation.png
#

(the graph is the blue nodes, the yellow nodes are the SCCs)

runic niche
bright fern
#

well, what happens when you try your algorithm on that graph?

runic niche
#

so I can find all the SCCs, but I think I need to store the path between 1 vertex of 1 SCC to another vertex of a different SCC

#

i think thats what i need to incorporate