Graph to Loops Decomposition

Representing electronic circuit as a graph - marking nodes

You need not know much about electricity or electronics for solving this problem - just it is a practical problem from this field, hence this intro. One of the methods of analyzing (calculating, modelling) of electric circuits uses the "Method of Current Loops".

• we represent circuit (graph) as a collection of simple loops (e.g. with no repeating vertices)
• loops could be picked arbitrarily, but we want every edge to be included in some loop (many edges could be shared between several loops)
• then we write equations with current in every loop being an unknown value (but same for every edge in this loop) and sum of voltages on all edges being zero

Such approach allows to reduce a number of unknown values (and equations) - to the number of chosen loops. English wikipedia seemingly calls it Mesh Analysis but this seems to be a special case of planar graph.

Method works with non-planar graphs either - just picking the loops becomes somewhat more tedious. That is the goal of this problem.

For example, the picture above represents symmetric multivibrator with amplifying cascade on the right. you see that every wire connecting several components represents a node (marked with red numbers). Components with more than 2 terminals (transistors here) couldn't be represented as edges and we need to put them as additional nodes. This circuit is used in the example below.

Problem statement

Given a graph description, produce a set of loops, suitable for the method described above. If something is wrong the checker will give you a hint.

Input data have the first line with the numbers of nodes V and edges E. Then some more lines follow with E pairs of numbers describing edges (edges are not directional).

Answer should give a space-separated list of loops, each as a sequnce of nodes. Start and end of a loop should be on the same node.

Example

input:
12 19
0:1 0:5 0:6 0:7 0:11 0:4 1:5 1:2 2:4 2:6 5:3 6:7 3:7 3:4 7:8 8:9 9:4 9:10 10:11

answer:
0-7-6-0 1-0-4-2-1 4-0-7-8-9-4 3-5-0-4-3 9-4-0-11-10-9 2-1-0-6-2 3-5-0-7-3 1-0-5-1

P.S. the graph generated for this problem is subject to some intuitive limitations:

• it is connected (otherwise disjoint circuits could be analysed separately)
• no dangling edges (these are rarely encountered in electric/electronic circuits and in these cases are not really dangling anyway)
• moreover any two nodes are guaranteed to be "covered" by some loop - or in other words there should be at least 2 completely distinct routes between any pair of nodes (it is an extension of the previous rule - and follows from 1st Kirchoff law)
• there are no duplicate edges - these could happen in practice, e.g. parallel resistor and capacitor - but such cases may be resolved in a number of ways and do not add anything interesting to the problem