A ring topology is a network configuration where the devices are connected to each other in a circular shape. Optical rings are widely used in mobile networks to transport the traffic from a base station to the backbone, through the mobile backhaul.

Definition of a ring

For the sake of simplicity, in this task, we define a ring as a connex graph which vertexes:

1. - have a degree 2 , which means they have 2 incident edges.
2. - are connected to two distinct vertexes

Shortest path asymmetric routing

Multiple traffic flows will be routed on the ring.
Each flow is routed on the shortest path from the ingress node (starting point of the traffic) to the egress node (exit point of the traffic).
If there are two shortest paths, the path which order fits the ring definition is kept .
Let's consider the following situation:

The path from A to B (and from B to A ) will be "A - G - B" , because it uses only two links, while the path going the other way around ("A - E - F - C - B") uses five links.
However, there are two paths of equal length to route a traffic from A to C : "A - E - F - C" and "A - G - B - C" . The first one, "A - E - F - C" , is kept: it is the same order as in the ring definition ( "AEFCBG" ).
The traffic from C to A will use the path "C - B - G - A" : the routing is asymmetric in that case.

Flow aggregation

A traffic flow is represented as a couple (s, dr) where:

1. - s is a string of length 2, containing the ingress node and the egress node .
2. - dr is the data rate in Gbps (gigabit per second).

Ethernet links dimensioning

There are five main types of Ethernet links used in mobile networks:

1. - Fast Ethernet (FE): 100 Mbps (or 0.1 Gbps)
2. - Gigabit Ethernet (GE): 1 Gbps.
3. - 10 Gigabit Ethernet (10GE): 10 Gbps
4. - 40 Gigabit Ethernet (40GE): 40 Gbps.
5. - 100 Gigabit Ethernet (100GE): 100 Gbps.

Given a ring and a list of traffic flows, you should return the number of Ethernet links of each type that are required to carry the resulting bandwidth:

In this example, we have 10 Gbps from E to C , 5 Gbps from A to C and 60 Gbps from A to B .
These traffic flows induce the following bandwidth: 15 Gbps from E to C , 5 Gbps from A to E and 60 Gbps from A to B .
The link dimensioning results in 2 100GE, 2 40GE and 1 10GE Ethernet links.

The result is given as a list containing the number of links for each category, from 100GE to FE. In our example, the result is [2, 2, 1, 0, 0]

Input: A variable number of arguments. The first one is a ring, represented as a string where each character is a node. The remaining arguments are traffic flows, represented as couples (s, dr) where s is a 2-characters string (ingress node, egress node) and dr is a positive value (traffic in Gbps).

Output: A list with 5 integers, one per type of link, in decreasing order of bandwidth capacity .

checkio("AEFCBG", ("AC", 5), ("EC", 10), ("AB", 60)) == [2, 2, 1, 0, 0]
checkio("ABCDEFGH", ("AD", 4)) == [0, 0, 3, 0, 0]
checkio("ABCDEFGH", ("AD", 4), ("EA", 41)) == [4, 0, 3, 0, 0]

How it is used: Links dimensioning is used for network planning and design. For real networks, various softwares are used to dimension the network based on the expected traffic load (for pre-sales engineers, when the network does not yet exist), or traffic measurements (for post-sales engineers to compute how much traffic the network can handle, and plan the network evolution).
However, real-life network dimensioning is much more complex than what is described in this task, as it deals with traffic differentiation and protection against equipment failure.

Preconditions:
The ring is a valid ring (connex, 2-degree nodes).
The traffic is a positive value (integer or float).