Padskiiz Padskiiz - 1 year ago 65
Python Question

Layer Counting Algorithm

I have an algorithm that sorts nodes into layers based on how many paths it takes to get to the output node.

So for example if there were:

  • Two input nodes

  • One hidden node

  • One output

they would be displayed in that order (inputs in layer 0, hidden in layer 1, output in layer 2).

for node in self.nodes:
if node.nodeType != 'INPUT':
inNodeIDs = [con.inNode for con in self.connections if con.outNode == node.ID]
node.layer = max([node.layer for node in self.nodes if node.ID in inNodeIDs])+1

A Node contains: ID(ID), layerNumber(layer) and nodeType ('HIDDEN'/'INPUT'/'OUTPUT')

A Connection contains: inNode(which refers to a node by ID) and outNode(which refers to a node by ID)

My algorithm gains a list of connections that are incoming to that node and then finds the node that is connected to it with the highest layerNumber and then sets the current nodes layer number to 1 higher because it is 1 layer further down than that node

The problem with my algorithm is that the nodes are ordered by there IDs but a node can be added that is in a layer before a node with a higher ID so when the algorithm goes through it doesn't calculate it correctly because it calculates the nodes in the wrong order.

e.g. the output node is created at initialization so if there is 2 ins and 1 out it is node 2 (ID's start at 0 for obvious reasons)
so the IDs of the nodes respective to their layers could look like this:

  • layer0 (node0, node1) inputs

  • layer1 (node5) hidden

  • layer2 (node4) hidden

  • layer3 (node3) hidden

  • layer4 (node2) output
(green = input, grey = hidden, blue = output)

as you can see node 8 and 6 where placed in the same layer when one is clearly connected to another

Nodes are added by disabling a connection and adding a node and two connections in between the two nodes the original connection connected

(1) (1)_
| | |
| = (3) |
| | |
(2) (2)_|

And the way the new nodes layerNum is calculated is by the old connections out nodes layer + 1 (the outnodes layerNum is also increased) but when a node is created before 2 existing node it does not increase its layerNum i.e. in the example above node 5 was added but node 3's layerNum would not have been updated

Can anyone think of a way to solve this problem is there a logical way to propagate this layerNum change through the network, the only thing I could think of was running it multiple times to make sure everything propagates through the network.

P.S I hope this all makes sense and thanks for peoples help in advance

Answer Source

Try calling your algorithm every time you add a new node, this should make it divy up the network nodes evenly. This should work if it doesn't there is probably an error else where in the code

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download