Graphs
4 problems from Rosalind — Bioinformatics Textbook Track. Press Run on any block to execute it in your browser.
BA3F — Find an Eulerian Cycle in a Graph
solved Problem statement
Hierholzer's algorithm, linear in the edges. Asserted on the property — every edge used exactly once, every step a real edge — rather than on the published string, which is one rotation among many.
BA3G — Find an Eulerian Path in a Graph
solved Problem statement
Add the edge between the two unbalanced nodes, find a cycle, then cut the added edge out again. Which node the walk starts and ends at is forced by the degrees, so those are asserted exactly.
BA5N — Find a Topological Ordering of a DAG
solved Problem statement
Kahn's algorithm with a FIFO queue. This is what BA5B and BA5D stand on: a longest path can be found in one sweep only if each node is reached after everything leading into it. Several orderings are valid, so the assertion checks every edge points forwards.
BA3M — Generate All Maximal Non-Branching Paths in a Graph
solved Problem statement
A run of 1-in-1-out nodes carries no choice, so collapsing it loses nothing; everywhere else is a real branch. The isolated cycle has no non-branching start and is only found by a second pass — without it, it would be silently dropped. Reported from 6 rather than 7, since a cycle has no first node.