[Tutor] Help needed

Sat Apr 26 21:16:27 CEST 2014

Hi Danny,

Let me give you a high level brief of what I am doing:
I am working on doing "disaster aware routing" considering the 24-node US
network where I will be setting up connection between two any two nodes (I
will select the source and destination nodes randomly). Also I have some
links whose "probability of failure" is mentioned in the attached file.
Other links, which are not mentioned in the file - we suppose their
"probability of failure" is zero. So between the source-destination nodes,
there will be multiple paths and I will select the one which has "least
probability of failure".

Now to setup the connection between two nodes, I have to select a path
whose "probability of failure" is least. To do that first I will calculate
the risk of each path from the attached file and then select the path with
least risk value. Did you get this part? I know it can be a bit confusing.

Now I break the problem into parts:

1. I have to topology of the 24-node map
2. I have the link values of each link - where risk values are the
"probability of failure"
3. I calculate the total "probability of failure" of each path (a path may
have multiple links): Suppose my source node is "a" and destination node is
"b". I can setup a path between a to b via c or via d (a-c-b or a-d-c):
Here I will check the risk values of a-c and c-b; also risk values of a-d
and d-c. If the total risk valure of a-c-b is lower that risk value of
a-d-c, then I select the path a-c-d to setup the connection. (again risk
value = probability of failure)

Now, I will first calculate the "total probability of failure" of each link
(using the file.txt) and since some links are repeated their values will be
added. The probabilities get added if a link is mentioned twice or thrice.
For example:  link 3—5 is repeated 3 times: in line one, it has a
probability of failure as 0.03, in line two it is 0.11 and in line three it
is 0.04. So the probability of failure for link 3—5 is 0.03+0.11+0.04 = 0.18

The length of each array will be same. You see the code I wrote: here is
the output for it:

Links ->

[('10', '13'), ('14', '18'), ('7', '8'), ('15', '20'), ('5', '8'), ('5',
'4'), ('11', '9'), ('21', '22'), ('12', '13'), ('21', '20'), ('17', '13'),
('20', '21'), ('21', '16'), ('14', '10'), ('11', '12'), ('11', '19'),
('14', '13'), ('3', '5'), ('11', '6'), ('19', '20')]

Probability ->

[0.04, 0.06, 0.04, 0.24, 0.08, 0.15, 0.08, 0.27, 0.04, 0.29, 0.08, 0.27,
0.27, 0.04, 0.08, 0.08, 0.08, 0.18000000000000002, 0.08, 0.24]

It means that link [10,13] has a "probability of failure" as [0.04] and
since the link [3-5] is repeated thrice with probability of 0.03, 0.11 and
0.04, its "probability of failure" is [0.18] (third last element in the
Probability array). For some reason instead of 0.18 it is showing
0.180000000002, which I cannot figure to why.

Please see the attached code. If you see the file.txt and my output: the
output is not displayed in sequence and that is what I need help with. I
want this to display :

Links = { [3,5] [5,4] [5,8] [7,8] [14,10] [14,13] [17,13] [14,18] [10,13]
[14,13] [17,13] [12,13] [11,6] [11,9] [11,12] [11,19] [19,20] [15,20]
[21,20] [20,21] [21,16] [21,22] }

Prob = {[0.18] [0.15] [0.08] [0.04] [0.04] [0.04] [0.08] [0.04] [0.08]
[0.08] [0.08] [0.08] [0.24] [0.24] [0.34] [0.27] [0.27]}

If you can figure why the output is not generated in same sequence as in
the file.txt for me, it will be very helpful.

let me know if I explained correctly, and if you have any questions or
doubts?

On Sat, Apr 26, 2014 at 11:41 AM, Danny Yoo <dyoo at hashcollision.org> wrote:

> >>> I want to create two arrays using the above file (Links array and Prob
> >>> array) that should give following output:
> >>>
> >>> *Links *= { [3,5] [5,4] [5,8] [7,8] [14,10] [14,13] [17,13] [14,18]
> >>> [10,13] [14,13] [17,13] [12,13] [11,6] [11,9][11,12] [11,19] [19,20]
> >>> [15,20] [21,20] [20,21] [21,16] [21,22] }
> >>>
> >>> *Prob *= {[0.28] [0.15] [0.08] [0.04] [0.04] [0.04] [0.08] [0.04]
> [0.08]
> >>> [0.08] [0.08] [0.08] [0.24] [0.24] [0.34] [0.27] [0.27]}
> >>
> >>
> >> I don't understand how you develop this? The first list has 22 items the
> >> second 17. I would have expected them to be the same?
> >
> >
> > In the "Prob" array the elements are less because if you read the note
> > below: I said the links that are repeating for example [3,5] their
> > probabilities  get added and stored as a single value in the "Prob"
> array.
>
>
> But what will you plan to do with these values afterwards?  I think
> Alan's point here is that if there's no direct relationship between
> the elements in Links and the elements in Probs, those values aren't
> going to be very useful to solve the rest of the problem.
>
>
> One way to look at this problem is to simplify or normalize the input;
> the original structure in the file is slightly weird to process, since
> a single line of the input represents several link/failure pairs.
>
> One concrete example is:
>
>     4,10,13,14,13,17,13,12,13,0.04
>
> where all these numbers are uninterpreted.
>
> You can imagine something that takes the line above, and breaks it
> down into a series of LinkFailure items.
>
> ######
> class LinkFailure(object):
>     """Represents a link and the probability of failure."""
>     def __init__(self, start, end, failure):
>         self.start = start
>         self.end = end
>         self.failure = failure
> ######
>
> which represent a link and failure structure.  If we have a structure
> like this, then it explicitly represents a relationship between a link
> and its failure, and the string line:
>
>     4,10,13,14,13,17,13,12,13,0.04
>
> can be distilled and represented as a collection of LinkFailure instances:
>
>     [LinkFailure(10, 13, 0.04), LinkFailure(14, 13, 0.04),
> LinkFailure(17, 13, 0.04), LinkFailure(12, 13, 0.04)]
>
> Then the relationship is explicit.
>
>
> >> Also why do you want these two lists? What do you plan on doing with
> them?
> >> I would have thought a mapping of link to probability would be much more
> >> useful? (mapping => dictionary)
> >
> >
> > I want these two lists because using the links and probs array, I will
> check
> > which link has the lowest probability. Here lowest probability means the
> > risk of failure for that link. So based on which link has least
> probability
> > of failure, I will use it to setup a connection (I have a source and
> > destination and the links mentioned above are the paths between them) I
> want
> > to select the path which has least failure probability.
> >
> > Did it make sense?
>
>
> Unfortunately, I'm still confused.  If you just have the Links and the
> Probs lists of unequal length, unless there's some additional
> information that you're represented, then I don't see the necessary
> connection between the two lists that lets you go any further in the
> problem.  There's no one-to-one-ness: given a link in Links, which
> Probs do you want to look at?  If you don't represent that linkage in
> some way, I don't understand yet where you go next.
>
>
> >>> So the first element in Links array is [3,5] and its probability of
> >>> failure is the first element in Prob array i.e. 0.28
>
> But if the two lists are different lengths, what probability of
> failure is associates with the last element in the Prob array?
>
>
> The representation of data is important: if you choose an awkward
> representation, it makes solving this problem more difficult than it
> needs be.  That is, if you're already compressing multiple elements in
> Prob that correspond to the same link, you also need some way to
> figure out what link that a compressed probability refer to.
> Otherwise, you don't have enough information to solve the problem
> anymore.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20140426/5c884582/attachment-0001.html>
-------------- next part --------------
1,3,5,0.03
2,3,5,5,4,0.11
3,3,5,5,4,5,8,0.04
2,5,8,7,8,0.04
3,14,10,14,13,17,13,0.04
1,14,18,0.06
4,10,13,14,13,17,13,12,13,0.04
4,11,6,11,9,11,12,11,19,0.08
3,19,20,15,20,21,20,0.24
1,21,20,0.05
3,20,21,21,16,21,22,0.27
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Code.py
Type: text/x-python-script
Size: 1957 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/tutor/attachments/20140426/5c884582/attachment-0001.bin>