Tuesday, January 29, 2013

Loop identification - XIV

Time for some testing.

Circuit 1 - Single phase diode rectifier



Result:

>>>
Number of nodes 6
Number of branches 9
Number of loops 5
**************************************************
1K 2K 3K 4K 5K 6K 7K 8K 9K 10K 11K 11L 11M 10M 9M 8M 7M 6M 5M 4M 3M 2M 1M 1L 1K
1K 1J 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 11I 11J 11K 10K 9K 8K 7K 6K 5K 4K 3K 2K 1K
1K 1J 1I 1H 1G 1F 1E 2E 3E 4E 5E 6E 7E 8E 9E 10E 11E 11F 11G 11H 11I 11J 11K 10K 9K 8K 7K 6K 5K 4K 3K 2K 1K
1K 1J 1I 2I 3I 4I 5I 6I 6H 7B 7A 6A 5A 5B 5C 5D 5E 6E 7E 8E 9E 10E 11E 11F 11G 11H 11I 11J 11K 11L 11M 10M 9M 8M 7M 6M 5M 4M 3M 2M 1M 1L 1K
1K 1J 1I 1H 1G 1F 1E 2E 3E 4E 5E 5D 5C 5B 5A 6A 7A 7B 6H 6I 7I 8I 9I 10I 11I 11J 11K 11L 11M 10M 9M 8M 7M 6M 5M 4M 3M 2M 1M 1L 1K


One additional loop generated but result is OK.


Circuit 2 - Three phase diode rectifier

Result:

>>>
Number of nodes 10
Number of branches 15
Number of loops 9
**************************************************
1M 1L 1K 1J 1I 2I 3I 4I 5I 6I 6H 7B 7A 8A 9A 9B 6L 6M 5M 4M 3M 2M 1M
1M 1L 1K 1J 1I 1H 1G 1F 1E 2E 3E 4E 5E 5D 5C 5B 5A 6A 7A 8A 9A 9B 6L 6M 5M 4M 3M 2M 1M
11O 11P 11Q 10Q 9Q 8Q 7Q 6Q 5Q 4Q 3Q 2Q 1Q 1P 1O 2O 3O 4O 5O 6O 7O 8O 9O 10O 11O
1M 1L 1K 1J 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 11I 11J 11K 11L 11M 10M 9M 8M 7M 6M 5M 4M 3M 2M 1M
1M 1L 1K 1J 1I 1H 1G 1F 1E 2E 3E 4E 5E 6E 7E 8E 9E 10E 11E 11F 11G 11H 11I 11J 11K 11L 11M 10M 9M 8M 7M 6M 5M 4M 3M 2M 1M
1M 1L 1K 1J 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 11I 11J 11K 11L 11M 11N 11O 11P 11Q 10Q 9Q 8Q 7Q 6Q 5Q 4Q 3Q 2Q 1Q 1P 1O 1N 1M
1M 1L 1K 1J 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 11I 11H 11G 11F 11E 10E 9E 8E 7E 6E 5E 5D 5C 5B 5A 6A 7A 8A 9A 9B 6L 6M 5M 4M 3M 2M 1M
1M 1L 1K 1J 1I 1H 1G 1F 1E 2E 3E 4E 5E 6E 7E 8E 9E 10E 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 11O 11P 11Q 10Q 9Q 8Q 7Q 6Q 5Q 4Q 3Q 2Q 1Q 1P 1O 1N 1M
1M 1L 1K 1J 1I 1H 1G 1F 1E 2E 3E 4E 5E 6E 7E 8E 9E 10E 11E 11F 11G 11H 11I 10I 9I 8I 7I 6I 6H 7B 7A 8A 9A 9B 6L 6M 5M 4M 3M 2M 1M


Additional 3 loops generated but result is OK.



Circuit 3 - Dc-dc boost converter

Result:

>>>
Number of nodes 4
Number of branches 6
Number of loops 3
**************************************************
1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11C 11B 11A 10A 9A 8A 7A 6A 5A 4A 3A 2A 1A 1B 1C 1D
11F 11G 11H 10H 9H 8H 7H 6H 5H 4H 3H 2H 1H 1G 1F 2F 3F 4F 5F 6F 7F 8F 9F 10F 11F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 10H 9H 8H 7H 6H 5H 4H 3H 2H 1H 1G 1F


The exact number of loops! This happens quite rarely though.


Circuit 4 - Dc-dc boost converter feeding a single-phase converter without FWDs

Result:
>>>
Number of nodes 14
Number of branches 21
Number of loops 12
**************************************************
1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11C 11B 11A 10A 9A 8A 7A 6A 5A 4A 3A 2A 1A 1B 1C 1D
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 10H 9H 8H 7H 6H 5H 4H 3H 2H 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 10J 9J 8J 7J 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 10N 9N 8N 7N 6N 5N 4N 3N 2N 1N 1M 1L 1K 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 11O 11P 11Q 11R 10R 9R 8R 7R 6R 5R 4R 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 10N 9N 8N 7N 6N 6O 7U 7V 8V 9V 9U 6K 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 11O 11P 11Q 11R 10R 9R 8R 7R 6R 5R 5S 5T 5U 5V 6V 7V 8V 9V 9U 6K 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 10J 9J 8J 7J 6J 6K 9U 9V 8V 7V 7U 6O 6N 5N 4N 3N 2N 1N 1M 1L 1K 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 10J 9J 8J 7J 6J 6K 9U 9V 8V 7V 6V 5V 5U 5T 5S 5R 4R 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 10N 9N 8N 7N 6N 6O 7U 7V 6V 5V 5U 5T 5S 5R 4R 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F
1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 11E 11F 11G 11H 11I 11J 11K 11L 11M 11N 11O 11P 11Q 11R 10R 9R 8R 7R 6R 5R 5S 5T 5U 5V 6V 7V 7U 6O 6N 5N 4N 3N 2N 1N 1M 1L 1K 1J 1I 1H 1G 1F


Three additional loops generated but result is OK.



Circuit 5 - Dc-dc boost converter feeding a three phase three level diode clamped inverter connected to grid

Result (I am not going to check this!):


>>>

Number of nodes 48

Number of branches 72

Number of loops 70

**************************************************

1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25C 25B 25A 24A 23A 22A 21A 20A 19A 18A 17A 16A 15A 14A 13A 12A 11A 10A 9A 8A 7A 6A 5A 4A 3A 2A 1A 1B 1C 1D

23J 23K 23L 22L 21L 21K 21J 22J 23J

21R 22R 23R 23S 23T 22T 21T 21S 21R

21Z 22Z 23Z 23AA 23AB 22AB 21AB 21AA 21Z

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

5J 5K 5L 4L 3L 3K 3J 4J 5J

9J 10J 11J 11K 11L 10L 9L 9K 9J

17J 17K 17L 16L 15L 15K 15J 16J 17J

3R 4R 5R 5S 5T 4T 3T 3S 3R

11R 11S 11T 10T 9T 9S 9R 10R 11R

15R 16R 17R 17S 17T 16T 15T 15S 15R

5Z 5AA 5AB 4AB 3AB 3AA 3Z 4Z 5Z

9Z 10Z 11Z 11AA 11AB 10AB 9AB 9AA 9Z

17Z 17AA 17AB 16AB 15AB 15AA 15Z 16Z 17Z

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 5K 5L 4L 3L 3K 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 22Z 21Z 20Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 19K 19L 19M 19N 18N 17N 16N 15N 14N 13N 13O 15G 15F 14F 13F 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 6R 5R 4R 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F



1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 19K 19L 19M 19N 18N 17N 16N 15N 14N 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 11F 10F 9F 9G 11AE 11AD 10AD 9AD 8AD 7AD 7AC 7AB 7AA 7Z 6Z 5Z 5AA 5AB 4AB 3AB 3AA 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 22Z 21Z 20Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 10AD 9AD 8AD 7AD 7AC 7AB 7AA 7Z 6Z 5Z 5AA 5AB 4AB 3AB 3AA 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 6R 5R 5S 5T 4T 3T 3S 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 20J 21J 22J 23J 24J 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 23AA 23AB 22AB 21AB 21AA 21Z 20Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 12J 11J 10J 9J 8J 7J 6J 5J 5K 5L 4L 3L 3K 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 5K 5L 4L 3L 3K 3J 2J 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 2Z 3Z 4Z 5Z 6Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 14V 15V 16V 17V 18V 19V 19U 19T 19S 19R 20R 21R 21S 21T 22T 23T 23S 23R 24R 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 23AA 23AB 22AB 21AB 21AA 21Z 20Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 6R 5R 4R 3R 2R 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 2Z 3Z 4Z 5Z 6Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 22Z 21Z 20Z 19Z 18Z 17Z 17AA 17AB 16AB 15AB 15AA 15Z 14Z 13Z 12Z 11Z 10Z 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 13F 14F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 18J 17J 16J 15J 14J 13J 12J 11J 11K 11L 10L 9L 9K 9J 8J 7J 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 19K 19L 19M 19N 18N 17N 16N 15N 14N 13N 13O 15G 15F 14F 13F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 6R 5R 5S 5T 4T 3T 3S 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 20J 21J 22J 23J 24J 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 23S 23T 22T 21T 21S 21R 20R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 14Z 15Z 15AA 15AB 16AB 17AB 17AA 17Z 18Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 10Z 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 8J 9J 10J 11J 12J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 14Z 15Z 15AA 15AB 16AB 17AB 17AA 17Z 18Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 8J 9J 10J 11J 12J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 10Z 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 5K 5L 4L 3L 3K 3J 2J 1J 1K 1L 1M 1N 1O 1P 1Q 1R 2R 3R 4R 5R 6R 7R 7S 7T 7U 7V 8V 9V 10V 11V 12V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 22Z 21Z 20Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 10F 11F 12F 13F 14F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 5K 5L 4L 3L 3K 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 22Z 21Z 20Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 10F 11F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 6R 5R 4R 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 18R 17R 17S 17T 16T 15T 15S 15R 14R 13R 12R 11R 10R 9R 8R 7R 7S 7T 7U 7V 8V 9V 10V 11V 12V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 11F 10F 9F 9G 11AE 11AD 10AD 9AD 8AD 7AD 7AC 7AB 7AA 7Z 6Z 5Z 4Z 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 18J 17J 16J 15J 14J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 14Z 15Z 16Z 17Z 18Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 18J 17J 16J 15J 14J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 11AA 11AB 10AB 9AB 9AA 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 18J 17J 16J 15J 14J 13J 12J 11J 11K 11L 10L 9L 9K 9J 8J 7J 7K 7L 7M 7N 8N 9N 10N 11N 12N 13N 13O 15G 15F 14F 13F 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 19K 19L 19M 19N 18N 17N 16N 15N 14N 13N 13O 15G 15F 14F 13F 12F 11F 10F 9F 9G 11AE 11AD 10AD 9AD 8AD 7AD 7AC 7AB 7AA 7Z 6Z 5Z 4Z 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 14R 15R 15S 15T 16T 17T 17S 17R 18R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 12R 11R 10R 9R 8R 7R 7S 7T 7U 7V 8V 9V 10V 11V 12V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 8J 9J 10J 11J 12J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 14R 15R 15S 15T 16T 17T 17S 17R 18R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 8J 9J 10J 11J 12J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 12R 11R 10R 9R 8R 7R 7S 7T 7U 7V 8V 9V 10V 11V 12V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 14V 15V 16V 17V 18V 19V 19U 19T 19S 19R 18R 17R 16R 15R 14R 13R 13S 15AH 15AI 14AI 13AI 13AH 13AA 13Z 14Z 15Z 16Z 17Z 18Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 14V 15V 16V 17V 18V 19V 19U 19T 19S 19R 18R 17R 16R 15R 14R 13R 13S 15AH 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 11AA 11AB 10AB 9AB 9AA 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 14V 15V 16V 17V 18V 19V 19U 19T 19S 19R 18R 17R 16R 15R 14R 13R 12R 11R 11S 11T 10T 9T 9S 9R 8R 7R 6R 5R 4R 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 8R 9R 9S 9T 10T 11T 11S 11R 12R 13R 13S 15AH 15AI 14AI 13AI 13AH 13AA 13Z 14Z 15Z 16Z 17Z 18Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 8R 9R 9S 9T 10T 11T 11S 11R 12R 13R 13S 15AH 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 11AA 11AB 10AB 9AB 9AA 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 25S 25T 25U 25V 25W 25X 25Y 25Z 24Z 23Z 22Z 21Z 20Z 19Z 18Z 17Z 17AA 17AB 16AB 15AB 15AA 15Z 14Z 13Z 12Z 11Z 10Z 9Z 8Z 7Z 6Z 5Z 5AA 5AB 4AB 3AB 3AA 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 18R 17R 17S 17T 16T 15T 15S 15R 14R 13R 13S 15AH 15AI 14AI 13AI 13AH 13AA 13Z 14Z 15Z 15AA 15AB 16AB 17AB 17AA 17Z 18Z 19Z 19AA 19AB 19AC 19AD 18AD 17AD 16AD 15AD 14AD 13AD 12AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 18R 17R 17S 17T 16T 15T 15S 15R 14R 13R 13S 15AH 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 10Z 9Z 8Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 18R 17R 17S 17T 16T 15T 15S 15R 14R 13R 12R 11R 10R 9R 8R 7R 6R 5R 5S 5T 4T 3T 3S 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 25K 25L 25M 25N 25O 25P 25Q 25R 24R 23R 22R 21R 20R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 6R 5R 5S 5T 4T 3T 3S 3R 2R 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 2Z 3Z 3AA 3AB 4AB 5AB 5AA 5Z 6Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 18J 17J 16J 15J 14J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 14R 15R 16R 17R 18R 19R 19S 19T 19U 19V 18V 17V 16V 15V 14V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 18J 17J 16J 15J 14J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 12R 11R 11S 11T 10T 9T 9S 9R 8R 7R 7S 7T 7U 7V 8V 9V 10V 11V 12V 13V 13W 12G 12F 11F 10F 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 25G 25H 25I 25J 24J 23J 23K 23L 22L 21L 21K 21J 20J 19J 19K 19L 19M 19N 18N 17N 16N 15N 14N 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 6J 5J 4J 3J 2J 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 2Z 3Z 3AA 3AB 4AB 5AB 5AA 5Z 6Z 7Z 7AA 7AB 7AC 7AD 8AD 9AD 10AD 11AD 11AE 9G 9F 8F 7F 6F 5F 4F 3F 2F 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 10Z 9Z 8Z 7Z 6Z 5Z 5AA 5AB 4AB 3AB 3AA 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 14N 15N 16N 17N 18N 19N 19M 19L 19K 19J 18J 17J 17K 17L 16L 15L 15K 15J 14J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 12R 11R 10R 9R 8R 7R 6R 5R 5S 5T 4T 3T 3S 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 8J 9J 10J 11J 12J 13J 13K 17AH 17AI 16AI 15AI 14AI 13AI 13AH 13AA 13Z 12Z 11Z 10Z 9Z 8Z 7Z 6Z 5Z 5AA 5AB 4AB 3AB 3AA 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 15G 13O 13N 12N 11N 10N 9N 8N 7N 7M 7L 7K 7J 8J 9J 10J 11J 12J 13J 13K 17AH 17AI 16AI 15AI 15AH 13S 13R 12R 11R 10R 9R 8R 7R 6R 5R 5S 5T 4T 3T 3S 3R 2R 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 14V 15V 16V 17V 18V 19V 19U 19T 19S 19R 18R 17R 16R 15R 14R 13R 13S 15AH 15AI 16AI 17AI 17AH 13K 13J 12J 11J 11K 11L 10L 9L 9K 9J 8J 7J 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 12G 13W 13V 12V 11V 10V 9V 8V 7V 7U 7T 7S 7R 8R 9R 9S 9T 10T 11T 11S 11R 12R 13R 13S 15AH 15AI 16AI 17AI 17AH 13K 13J 12J 11J 11K 11L 10L 9L 9K 9J 8J 7J 6J 5J 4J 3J 2J 1J 1I 1H 1G 1F

1F 1E 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 14D 15D 16D 17D 18D 19D 20D 21D 22D 23D 24D 25D 25E 25F 24F 23F 22F 21F 20F 19F 18F 17F 16F 15F 14F 13F 12F 11F 10F 9F 9G 11AE 11AD 12AD 13AD 14AD 15AD 16AD 17AD 18AD 19AD 19AC 19AB 19AA 19Z 18Z 17Z 17AA 17AB 16AB 15AB 15AA 15Z 14Z 13Z 12Z 11Z 10Z 9Z 8Z 7Z 6Z 5Z 5AA 5AB 4AB 3AB 3AA 3Z 2Z 1Z 1Y 1X 1W 1V 1U 1T 1S 1R 1Q 1P 1O 1N 1M 1L 1K 1J 1I 1H 1G 1F


Loop identification - XIII

The concept involved in determining loops.

1. branch_map is the array that contains every branch as a list of elements between nodes. The diagonal elements are null because it is assumed that self-loops do not exist. The non-diagonal elements are branched between nodes. So branch_map[i][j] is the branch between node i and node j.

2. branch_map can have multiple lists because there can be parallel branches between two nodes.

3. Every row must have at least three elements because that is how a node is defined - a node is an element from which three or four branches connect it to another node.

4. The number of independent loops = Branches - Nodes +1.

So this is how I find the loops:

1. Pick the first non-null element in the first row.
2. The first loop in progress will be this element.
3. The direction of searching will be horizontal or "horiz". This means we search in the same row for other branches. All searches will be from the first column to last column of a row.
4. For every element in the row, check for parallel branches and add them to loop_list.
5. If not a parallel branch, check if that element or the inverse of it (i.e if [i, j] is the element, [j, i] will also be the same) has been encountered before. If so, then loop is not valid and stop updating that particular list. If not a repeat, append that element to the list.
6. For every element found, create a new list and add it to the elements already in the list. This means, the lists will keep growing in number and size.
7. Check is the loop has ended. This means, are one of the end nodes of the latest branch the same as the end node of the first branch in the loop.
8. If so, take this list and check if the nodes in the branches of the list have been encountered before. That is make a copy of node_list (loop_nodes) and keep deleting the nodes which are found. So it a node in the list exists in loop_nodes, this means the node has not been encountered. A loop which passes through a new nodes is definitely an independent loop, so add this loop to the main loop_list.
9. If the loop does not pass through a new node, it could still be an independent loop. So check if the loop is the same as the loops already found and in loop_list.
10. If so, this means the loop is different from the loops in loop_list. So this may or may not be an independent loop. Add it to loop_list anyway.
11. This completed once cycle. Change the direction of search to vertical or "vert".
12. Check if loop_nodes is null or if number of loops found is less than B-N+1. If either or both are true, continue checking.
13. Take the last element of every loop in progress and look in the columns of those elements starting from first row to last row. Repeat 4-10. Change direction of search again.


The problem is that this method often throws up a number of loops greater than B-N+1 which means some of them will be redundant. This is particularly the case when tightly interconnected circuits are examined. The examples in the next post will make things clear.

Loop identification - XII

Another change in code. Since, this is one of the most critical aspects of the simulator, I need to make sure I get this right. Still not very happy with the result, but need to take a couple of steps forward. The explanation for why I did what I did will come soon in the next post.

Here is the loop finder part (click on "view raw" below the code box to see it in a new window):

def loop_copy(loop_inp):
""" Will return a copy of a loop list
Used when a change needs to be made."""
loop_op=[]
for c1 in range(len(loop_inp)):
row_vector=[]
for c2 in range(len(loop_inp[c1])):
row_vector.append(loop_inp[c1][c2])
loop_op.append(row_vector)
return loop_op
def check_loop_repeat(lp_iter, lp_list):
""" Will return 1 if the loop already
exists if the loop_list found so far."""
# Make a copy of the entire loop list
# found so far. Just in case.
list_cmp=loop_copy(lp_list)
# As a default, loop is not repeated
# A single instance of repitition will
# set it to 1.
lp_repeat=0
# Go through every loop found
# so far
for c1 in range(len(list_cmp)):
# Make a copy of the loop being checked
iter_cmp=loop_copy(lp_iter)
# Move in the reverse direction of the loop
# This is because elements are deleted
# as they are found.
for c2 in range(len(iter_cmp)-1, -1, -1):
# Check if the element is found or if the
# symmetrical element is found in any of
# the loops found so far.
# Because they are the same.
if ([iter_cmp[c2][0], iter_cmp[c2][1]] in list_cmp[c1]) or \
([iter_cmp[c2][1], iter_cmp[c2][0]] in list_cmp[c1]):
# If so, remove the element
iter_cmp.remove(iter_cmp[c2])
# If all element have been deleted
# it means the loop exists
if not iter_cmp:
lp_repeat=1
return lp_repeat
def loop_addition(br_map, nd_list, lp_list, curr_lp_iter, lp_update, curr_elem, all_loops, main_loops):
""" Take a new element of br_map in any direction.
Check for a parallel branch at that element.
Add that element if not already there in the temporary loop."""
row=curr_elem[0]
col=curr_elem[1]
# Check if there is an element
if br_map[row][col]:
# Check for parallel branches
if len(br_map[row][col])>1:
if (br_map[row][col][0][0] in nd_list) or \
(br_map[row][col][0][-1] in nd_list):
del nd_list[nd_list.index(br_map[row][col][0][-1])]
del nd_list[nd_list.index(br_map[row][col][0][0])]
# Check if the parallel branch exists already
# in lp_list
if not check_loop_repeat([[row, col], [row, col]], lp_list):
lp_list.append([[row, col], [row, col]])
# Update the all_loops counter
all_loops+=len(br_map[row][col])-1
# Temp list to make copies
# of loops found
row_vec=[]
for item in curr_lp_iter:
row_vec.append(item)
# Check if an element has been
# encountered before
# not going back and forth that is
if not (([row, col] in row_vec) or [col, row] in row_vec):
# Add the element found
lp_update.append(row_vec)
lp_update[main_loops].append([row, col])
# Update the main loops counter
main_loops+=1
# If an element has not been found
# or is a duplicate, lp_update
# won't contain it.
return [all_loops, main_loops]
def loop_closing(br_map, lp_list, nd_list, lp_update, c1, lp_count):
""" After a loop has been indentified. That is
the first node and the last node are the same.
It is checked whether the loop passes through
nodes that have not been passed through. If not,
loop is directly added. If it does, another
additional check is is the loop has the same elements
as any other loops already found in lp_list. """
# Default is that all nodes have been "found"
# or passed through. A single exception will
# produce a new loop.
nd_exist="found"
for c5 in range(len(lp_update[c1])):
# Go through every branch in the loop
# Take the first and last node of every branch
st_node=br_map[lp_update[c1][c5][0]][lp_update[c1][c5][1]][0][0]
end_node=br_map[lp_update[c1][c5][0]][lp_update[c1][c5][1]][0][-1]
# Check if either are there in nd_list
# Nodes are deleted from nd_list as they are
# found. So if the node is in nd_list
# it means it has not been passed through
if (st_node in nd_list):
nd_exist="not_found"
nd_idx=nd_list.index(st_node)
del nd_list[nd_idx]
if (end_node in nd_list):
nd_exist="not_found"
nd_idx=nd_list.index(end_node)
del nd_list[nd_idx]
if nd_exist=="not_found":
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
else:
# Check if the loop is new even
# if all nodes have been passed through.
lp_exist="found"
if not check_loop_repeat(lp_update[c1], lp_list):
lp_exist="not_found"
if lp_exist=="not_found":
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
return lp_count
def loop_horiz(br_map, nd_list, lp_list, lp_iter, elem, lp_count):
""" Moves horizontally in a loop find.
Looks for every element in a particular column of br_map.
Each element is added onto the exiting loops. """
# lp_list is the loops found.
# lp_iter is the list of loops as they are being identified.
# Those that are loops will be added to lp_list.
no_nodes=len(br_map)
start_row=elem[0]
start_col=elem[1]
# Temp list to make copies
# of exisiting lists
# if elements exist on that row
lp_update=[]
# Counter for number
# of elements found in the row
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element in next column
# to end of matrix
#for c3 in range(loop_column+1, no_nodes):
for c3 in range(0, no_nodes):
curr_elem=[loop_row, c3]
lp_count,c2=loop_addition(br_map, nd_list, lp_list, \
lp_iter[c1], lp_update, curr_elem, lp_count, c2)
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
lp_count=loop_closing(br_map, lp_list, nd_list, lp_update, c1, lp_count)
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
#print lp_update, "Check"
#print lp_iter, "End"
return [lp_count, lp_iter]
def loop_vert(br_map, nd_list, lp_list, lp_iter, elem, lp_count):
""" Moves vertically in a loop find.
Looks for every element in a particular column of br_map.
Each element is added onto the exiting loops. """
# lp_list is the loops found.
# lp_iter is the list of loops as they are being identified.
# Those that are loops will be added to lp_list.
no_nodes=len(br_map)
start_row=elem[0]
start_col=elem[1]
# Temp list to make copies
# of exisiting lists
# if elements exist on that column
lp_update=[]
# Counter for number
# of elements found in the column
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element from first row
# to end of column
for c3 in range(0, no_nodes):
curr_elem=[c3, loop_column]
lp_count,c2=loop_addition(br_map, nd_list, lp_list, \
lp_iter[c1], lp_update, curr_elem, lp_count, c2)
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
lp_count=loop_closing(br_map, lp_list, nd_list, lp_update, c1, lp_count)
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
return [lp_count, lp_iter]
def find_loop(br_map, nd_list, lp_list, lp_iter, elem, lp_count, lp_limit):
"""Find the loops from info on branches and
nodes. The starting point is the first branch in br_map.
The loops found need not be independent loops."""
no_nodes=len(br_map)
# First branch
start_row=elem[0]
start_col=elem[1]
# Move right from that element
# This is the first element
# In a general sense, the direction is horiz
loop_dir="horiz"
# The termination condition is
# that there should not be any element
# in the nd_list. The nodes are deleted
# as a completed loop contains them.
# This is to ensure that all the nodes
# are included in the loops found.
# To ensure that parallel loops between
# a few pair of nodes, do not cause
# loops to be left out, additionally,
# it is checked whether
# Loops < Branches - Nodes + 1
while (nd_list or lp_count<lp_limit):
# Will be executed if we are moving horizontally
if (loop_dir == "horiz"):
lp_count, lp_iter=loop_horiz(br_map, nd_list, lp_list, lp_iter, elem, lp_count)
# Change direction to vertical
loop_dir="vert"
# Will be executed if we are moving vertically
if (loop_dir == "vert"):
lp_count, lp_iter=loop_vert(br_map, nd_list, lp_list, lp_iter, elem, lp_count)
# Change direction to horizontal
loop_dir="horiz"
return lp_count
# Determining the loops
loop_list=[]
loop_count=0
loop_nodes=[]
# Making a copy of node_list
# for finding the loops
for c1 in range(len(node_list)):
loop_nodes.append(node_list[c1])
# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
for c2 in range(c1+1, number_of_nodes):
#check if it exists
if branch_map[c1][c2]:
# Starting branch found
if len(branch_map[c1][c2])>1:
if not check_loop_repeat([[c1, c2], [c1, c2]], loop_list):
loop_list.append([[c1, c2], [c1, c2]])
# Check for parallel branches again.
if (branch_map[c1][c2][0][0] in loop_nodes):
del loop_nodes[loop_nodes.index(branch_map[c1][c2][0][0])]
if (branch_map[c1][c2][0][-1] in loop_nodes):
del loop_nodes[loop_nodes.index(branch_map[c1][c2][0][-1])]
# Check is there are parallel branches between the nodes
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=len(branch_map[c1][c2])-1
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([[c1, c2]])
loop_count=find_loop(branch_map, loop_nodes, loop_list, loop_iter, \
[c1, c2], loop_count, number_of_branches-number_of_nodes+1)
# Remove any repitions in loop_list
for c1 in range(len(loop_list)-1):
for c2 in range(len(loop_list)-1, c1, -1):
if loop_list[c1]==loop_list[c2]:
del loop_list[c2]
# The actual elements from the branches
# to be entered into the loops
loop_branches=[]
# Go through every element in loop_list
for c1 in range(len(loop_list)):
# If the loop has two elements
# it means it is a group of
# parallel branches between nodes
if len(loop_list[c1])==2:
curr_br=loop_list[c1][0]
# Get every permutation of branch pairs possible
for c2 in range(len(branch_map[curr_br[0]][curr_br[1]])-1):
for c3 in range(c2+1, len(branch_map[curr_br[0]][curr_br[1]])):
loop_updt=[]
# Iterate in the forward direction
for c4 in range(len(branch_map[curr_br[0]][curr_br[1]][c2])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][c2][c4])
# Iterate in the reverse direction
for c4 in range(len(branch_map[curr_br[0]][curr_br[1]][c3])-2, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][c3][c4])
loop_branches.append(loop_updt)
else:
loop_updt=[]
# Go through all elements in the loop
for c2 in range(0, len(loop_list[c1])-1):
# Mark two elements in the loop
# The current and the next element
curr_br=loop_list[c1][c2]
curr_br_beg=branch_map[curr_br[0]][curr_br[1]][0][0]
curr_br_end=branch_map[curr_br[0]][curr_br[1]][0][-1]
next_br=loop_list[c1][c2+1]
next_br_beg=branch_map[next_br[0]][next_br[1]][0][0]
next_br_end=branch_map[next_br[0]][next_br[1]][0][-1]
curr_dir="forward"
# Start stringing the branches together
# So if it is the first branch
# Check if the beginning element of the branch
# is the same as the beginning or ending element
# if the next branch
# In that case, the first/current branch
# is to be reversed
if not loop_updt:
if curr_br_beg==next_br_beg or curr_br_beg==next_br_end:
curr_dir="reverse"
# If the loop update is in progress
# check how the current element is linked to
# the last element on the updated loop
else:
if curr_br_end==loop_updt[-1]:
curr_dir="reverse"
# Depending on the direction in which
# an element is to be added to
# the loop.
if curr_dir=="forward":
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
else:
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
# Repeat for the last element
next_dir="forward"
if next_br_end==loop_updt[-1]:
next_dir="reverse"
if next_dir=="forward":
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
else:
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
# Remove any repitions in the elements
# in consecutive elements only
for c3 in range(len(loop_updt)-1, 0, -1):
if loop_updt[c3]==loop_updt[c3-1]:
del loop_updt[c3]
loop_branches.append(loop_updt)
#loop_count=len(loop_branches)
print "Number of nodes",
print number_of_nodes
print "Number of branches",
print number_of_branches
print "Number of loops",
print loop_count
print "*"*50
excel_col="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
excel_dict={}
excel_col_list=excel_col.split(" ")
for c1 in range(26):
excel_dict[c1]=excel_col_list[c1]
for item in loop_branches:
for c1 in range(len(item)):
print str(item[c1][0]+1) + excel_dict[item[c1][1]],
print
view raw loop_finder.py hosted with ❤ by GitHub

And here is the entire code (click on "view raw" below the code box to see it in a new window):

#! /usr/bin/env python
import sys, math, matrix
new_file = open("powerckt3.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire"
# where a zero impedance direct connection exists.
# Where no connection nor device
#(resitor, inductor etc) exists, a '' will be found.
# The devices will be strings.
# Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# Remove any leading or trailing quotes
# and also carriage returns (\n) that
# may have been added while generating the csv file.
def scrub_elements(x, row, col):
if x[row][col]:
if "\n" in x[row][col]:
x[row][col]=x[row][col][:-1]
if x[row][col]:
while (x[row][col][0]=='"' or x[row][col][0]=="'"):
x[row][col]=x[row][col][1:]
while (x[row][col][-1]=='"' or x[row][col][-1]=="'"):
x[row][col]=x[row][col][:-1]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
scrub_elements(conn_matrix, c1, c2)
# List of jumps labels
jump_list=[]
# Structure of jump_list
# row, column, jump_label, direction
# Check is it a jump, an element
# or simply no connection
def jump_sanity(x, x_jump, row, column):
x_elem = x[row][column]
if (x_elem ==''):
del x_jump["exist"]
del x_jump["jump"]
elif (len(x_elem)>3):
if (x_elem.lower()[0:4] == "jump"):
del x_jump["exist"]
else:
del x_jump["jump"]
else:
del x_jump["jump"]
# Check for jump label sanity and
# add a list of elements where jumps exist.
# Basically examines whether element (c1, c2)
# is a jump and what are the elements
# around it.
def jump_checking(x_matrix, x_jump, row, col, no_rows, no_cols):
# Current element
curr_element = {"exist":0, "jump":1}
# Determine if it is a jump label
jump_sanity(x_matrix, curr_element, row, col)
if ("jump" in curr_element):
# If so, what is the element in the same column
# and next row
if (row<no_rows-1):
next_row_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, next_row_element, row+1, col)
else:
next_row_element = {}
# If so, what is the element in the same column
# and previous row
if (row>0):
prev_row_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, prev_row_element, row-1, col)
else:
prev_row_element = {}
# If so, what is the element in the same row
# and next column
if (col<no_cols-1):
next_col_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, next_col_element, row, col+1)
else:
next_col_element = {}
# If so, what is the element in the same row
# and previous column
if (col>0):
prev_col_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, prev_col_element, row, col-1)
else:
prev_col_element = {}
# Check if two jumps are next to each other
if ("jump" in next_row_element or "jump" in next_col_element or \
"jump" in prev_row_element or "jump" in prev_col_element):
print "Two jumps can't be adjacent to each other."
print "Check jump at row %d, column %d" %(row, col)
# Jump must have only one element adjacent to it.
if ("exist" in next_row_element):
if ("exist" in next_col_element or "exist" in prev_row_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "down"])
elif ("exist" in next_col_element):
if ("exist" in next_row_element or "exist" in prev_row_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "right"])
elif ("exist" in prev_row_element):
if ("exist" in next_row_element or "exist" in next_col_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "up"])
elif ("exist" in prev_col_element):
if ("exist" in next_row_element or "exist" in next_col_element or \
"exist" in prev_row_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "left"])
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
jump_checking(conn_matrix, jump_list, c1, c2, conn_rows, conn_columns)
# Create a dictionary of jumps -
# for each jump label - there is a list with two elements.
jump_matrix={}
# Structure of jump_matrix
# label: [[[row, col], "dir"], [[row, col], "dir"]]
for c1 in range(len(jump_list)):
jump_count=1
for c2 in range(len(jump_list)):
if not c1==c2:
if jump_list[c1][2]==jump_list[c2][2]:
frst_jmp = jump_list[c1]
scd_jmp = jump_list[c2]
jump_matrix[frst_jmp[2]]=[[[frst_jmp[0], frst_jmp[1]], frst_jmp[3]],\
[[scd_jmp[0], scd_jmp[1]], scd_jmp[3]]]
jump_count=jump_count+1
if (jump_count<2):
print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
elif (jump_count>2):
print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
del jump_matrix[jump_list[c1][2]]
# A node is defined as a junction of 3 or more branches.
def node_checking(x_mat, x_list, row, col, x_row, x_col):
if ((row==0 and col==0) or (row==x_row-1 and col==x_col-1) or \
(row==0 and col==x_col-1) or (row==x_row-1 and col==0)):
# If its a corner point it can't be a node.
# This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (row==0):
# If it is the first row,
# check if the element in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
# Then check if the element in next row and
# same column is connected. Look for a T junction.
if not (x_mat[row+1][col]==''):
x_list.append([row, col])
if (row==x_row-1):
# If it is the last row,
# check if the elements in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
if not (x_mat[row-1][col]==''):
# Then check if element in the previous row and
# same column is connected. Look for a T junction.
x_list.append([row, col])
if (col==0):
# If it is the first column,
# check if the element in the next column and
# same row is connected.
if not (x_mat[row][col+1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (col==x_col-1):
# If it is the last column,
# check if the element in the previous column and
# same row is connected.
if not (x_mat[row][col-1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (row>0 and row<x_row-1 and col>0 and col<x_col-1):
# If the element is not on the outer boundary
if (x_mat[row][col+1]!='' and x_mat[row][col-1]!=''):
# Check if the elements in next and
# previous columns and same row are connected
if (x_mat[row+1][col]!='' or x_mat[row-1][col]!=''):
# Then check if elements in either the next and
# previous row and same column are connected
x_list.append([row, col])
elif (x_mat[row+1][col]!='' and x_mat[row-1][col]!=''):
# Check if the elements in next and
# previous rows and same column are connected
if (x_mat[row][col+1]!='' or x_mat[row][col-1]!=''):
# Then check if elements in either the next and
# previous column and same row are connected
x_list.append([row, col])
node_list=[]
# Structure of node_list
# [row, column]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
jump_sanity(conn_matrix, curr_element, c1, c2)
if ("exist" in curr_element):
node_checking(conn_matrix, node_list, c1, c2, conn_rows, conn_columns)
else:
pass
# This list contains all the nodes that are T or + junctions.
#print "*"*60
#print node_list
#print "*"*60
# Map of branches between nodes in node_list
branch_map=[]
# Creating an square of the dimension of node_list.
# Each element will be a list of the
# series connection of branches between the nodes.
for c1 in range(len(node_list)):
branch_rows=[]
for c2 in range(len(node_list)):
branch_rows.append([])
branch_map.append(branch_rows)
# Generate a search rule for each node.
# The concept is to start at a node and
# search until another node is reached.
node_iter_rule=[]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
iter_rule={"left":0, "down":1, "right":2, "up":3}
# For nodes in the outer edges,
# the rules going outwards will be removed.
if (node_row==0):
del(iter_rule["up"])
if (node_row==conn_rows-1):
del(iter_rule["down"])
if (node_column==0):
del(iter_rule["left"])
if (node_column==conn_columns-1):
del(iter_rule["right"])
# Depending on the non-existence of elements
# in a direction, those rules will be removed.
if (node_row>0) and (node_row<conn_rows-1) and \
(node_column>0) and (node_column<conn_columns-1):
if (conn_matrix[node_row-1][node_column]==''):
del(iter_rule["up"])
if (conn_matrix[node_row+1][node_column]==''):
del(iter_rule["down"])
if (conn_matrix[node_row][node_column+1]==''):
del(iter_rule["right"])
if (conn_matrix[node_row][node_column-1]==''):
del(iter_rule["left"])
node_iter_rule.append(iter_rule)
def jump_node_check(x_mat, x_list, jdir, row):
n_row=x_list[c1][0]
n_col=x_list[c1][1]
if (jdir=="up"):
if (len(x_mat[n_row-1][n_col])>3):
if (x_mat[n_row-1][n_col].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row-1, n_col)
if (jdir=="down"):
if (len(x_mat[n_row+1][n_col])>3):
if (x_mat[n_row+1][n_col].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row+1, n_col)
if (jdir=="left"):
if (len(x_mat[n_row][n_col-1])>3):
if (x_mat[n_row][n_col-1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row, n_col-1)
if (jdir=="right"):
if (len(x_mat[n_row][n_col+1])>3):
if (x_mat[n_row][n_col+1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row, n_col+1)
# Check if a jump is not next to a node.
for c1 in range(len(node_list)):
for jump_check_dir in node_iter_rule[c1].keys():
jump_node_check(conn_matrix, node_list, jump_check_dir, c1)
# For each node in node_list perform the search operation.
# Each node has a list of possible search rules.
# Perform a search for each rule.
# From the starting node, advance in the direction of the rule.
# After advancing, check if the next element is a node.
# If it is a node, stop.
# If it is not a node, there can be only two directions of movement.
# Move in a direction and check is an element exists.
# If it exists, check if it is not already an element encountered -
# shouldn't be moving backwards.
# If a new element is encountered,
# update the element is branch iter and continue.
def jump_move(x_mat, x_jump, x_element, pos):
jump_trace=x_mat[x_element[0]][x_element[1]]
if (x_jump[jump_trace][pos][1] == "left"):
nxt_row=x_jump[jump_trace][pos][0][0]
nxt_col=x_jump[jump_trace][pos][0][1] - 1
jmp_exec="left"
elif (x_jump[jump_trace][pos][1] == "right"):
nxt_row=x_jump[jump_trace][pos][0][0]
nxt_col=x_jump[jump_trace][pos][0][1] + 1
jmp_exec="right"
elif (x_jump[jump_trace][pos][1] == "up"):
nxt_row=x_jump[jump_trace][pos][0][0] - 1
nxt_col=x_jump[jump_trace][pos][0][1]
jmp_exec="up"
elif (x_jump[jump_trace][pos][1] == "down"):
nxt_row=x_jump[jump_trace][pos][0][0] + 1
nxt_col=x_jump[jump_trace][pos][0][1]
jmp_exec="down"
return [jmp_exec, nxt_row, nxt_col]
def branch_jump(x_mat, x_jump, x_element):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and
# the sense of movement.
# Depending on the sense of movement, update
# the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement
# has taken place
# To ensure that we don't go back
# from the next element after the jump.
nxt_row=x_element[0]
nxt_col=x_element[1]
jump_exec=""
if (len(x_mat[nxt_row][nxt_col])>3):
if (x_mat[nxt_row][nxt_col].lower()[0:4] == "jump"):
jump_trace=x_mat[nxt_row][nxt_col]
if (x_jump[jump_trace][0][0] == [nxt_row, nxt_col]):
jump_exec, nxt_row, nxt_col = \
jump_move(x_mat, x_jump, x_element, 1)
elif (x_jump[jump_trace][1][0] == [nxt_row, nxt_col]):
jump_exec, nxt_row, nxt_col = \
jump_move(x_mat, x_jump, x_element, 0)
return [jump_exec, nxt_row, nxt_col]
# Advancing one element in a branch
# Checking for jump direction
# to make sure we don't go back
def branch_advance(x_mat, x_iter, nxt_elem, jmp_exec, x_rows, x_cols):
nxt_row=nxt_elem[0]
nxt_col=nxt_elem[1]
# This temporary variable is to ensure,
# two advancements don't take place in one loop.
branch_proceed=0
if ((nxt_col>0) and branch_proceed==0):
# We are trying to go left, so check if we didn't jump right.
if (x_mat[nxt_row][nxt_col-1] != '' and jmp_exec!="right"):
# Next check is if we are going backwards.
if not ([nxt_row, nxt_col-1] in x_iter):
nxt_col=nxt_col-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_row>0) and branch_proceed==0):
# We are trying to go up, so check if we didn't jump down.
if (x_mat[nxt_row-1][nxt_col] != '' and jmp_exec!="down"):
if not ([nxt_row-1, nxt_col] in x_iter):
nxt_row=nxt_row-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_col<x_cols-1) and branch_proceed==0):
# We are trying to go right, so check if we didn't jump left.
if (x_mat[nxt_row][nxt_col+1] != '' and jmp_exec!="left"):
if not ([nxt_row, nxt_col+1] in x_iter):
nxt_col=nxt_col+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_row<x_rows-1) and branch_proceed==0):
# We are trying to go down, so check if we didn't jump up.
if (x_mat[nxt_row+1][nxt_col] != '' and jmp_exec!="up"):
if not ([nxt_row+1, nxt_col] in x_iter):
nxt_row=nxt_row+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
return [jmp_exec, nxt_row, nxt_col]
for c1 in range(len(node_list)):
# Iterate through every node found
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
# Move in every direction possible
# for every node
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
# This variable is used when jumps are encountered.
jump_executed=""
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and
# the sense of movement.
# Depending on the sense of movement, update
# the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement
# has taken place
# To ensure that we don't go back
# from the next element after the jump.
next_element = [next_node_row, next_node_column]
jump_executed, next_node_row, next_node_column = \
branch_jump(conn_matrix, jump_matrix, next_element)
branch_iter.append([next_node_row, next_node_column])
next_element = [next_node_row, next_node_column]
jump_executed, next_node_row, next_node_column = \
branch_advance(conn_matrix, branch_iter, next_element, \
jump_executed, conn_rows, conn_columns)
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches. \
Check at row %d column %d" %(next_node_row, next_node_column)
break
else:
branch_iter.append([next_node_row, next_node_column])
next_elem_index=node_list.index([next_node_row, next_node_column])
branch_map[c1][next_elem_index].append(branch_iter)
nw_look=open("nw_check.csv","w")
for c1 in range(len(node_list)):
for c2 in range(len(node_list)-1):
if (branch_map[c1][c2]):
for c3 in range(len(branch_map[c1][c2])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2][c3])):
nw_look.write("[%d %d] ;" \
%(branch_map[c1][c2][c3][c4][0], branch_map[c1][c2][c3][c4][1]))
nw_look.write(")")
nw_look.write(", ")
else:
nw_look.write("[], ")
if (branch_map[c1][c2+1]):
for c3 in range(len(branch_map[c1][c2+1])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2+1][c3])):
nw_look.write("[%d %d] ;" \
%(branch_map[c1][c2+1][c3][c4][0], branch_map[c1][c2+1][c3][c4][1]))
nw_look.write(")")
nw_look.write("\n")
else:
nw_look.write("[] \n")
##for c1 in range(len(node_list)):
## for c2 in range(len(node_list)-1):
## nw_look.write("%s ;" %(branch_map[c1][c2]))
## nw_look.write("%s \n" %(branch_map[c1][c2+1]))
nw_look.close()
number_of_nodes=len(node_list)
number_of_branches=0
# Counting the number of branches
for c1 in range(len(node_list)):
for c2 in range(c1+1, len(node_list)):
for parallel_branches in branch_map[c1][c2]:
number_of_branches+=1
def loop_copy(loop_inp):
""" Will return a copy of a loop list
Used when a change needs to be made."""
loop_op=[]
for c1 in range(len(loop_inp)):
row_vector=[]
for c2 in range(len(loop_inp[c1])):
row_vector.append(loop_inp[c1][c2])
loop_op.append(row_vector)
return loop_op
def check_loop_repeat(lp_iter, lp_list):
""" Will return 1 if the loop already
exists if the loop_list found so far."""
# Make a copy of the entire loop list
# found so far. Just in case.
list_cmp=loop_copy(lp_list)
# As a default, loop is not repeated
# A single instance of repitition will
# set it to 1.
lp_repeat=0
# Go through every loop found
# so far
for c1 in range(len(list_cmp)):
# Make a copy of the loop being checked
iter_cmp=loop_copy(lp_iter)
# Move in the reverse direction of the loop
# This is because elements are deleted
# as they are found.
for c2 in range(len(iter_cmp)-1, -1, -1):
# Check if the element is found or if the
# symmetrical element is found in any of
# the loops found so far.
# Because they are the same.
if ([iter_cmp[c2][0], iter_cmp[c2][1]] in list_cmp[c1]) or \
([iter_cmp[c2][1], iter_cmp[c2][0]] in list_cmp[c1]):
# If so, remove the element
iter_cmp.remove(iter_cmp[c2])
# If all element have been deleted
# it means the loop exists
if not iter_cmp:
lp_repeat=1
return lp_repeat
def loop_addition(br_map, nd_list, lp_list, curr_lp_iter, lp_update, curr_elem, all_loops, main_loops):
""" Take a new element of br_map in any direction.
Check for a parallel branch at that element.
Add that element if not already there in the temporary loop."""
row=curr_elem[0]
col=curr_elem[1]
# Check if there is an element
if br_map[row][col]:
# Check for parallel branches
if len(br_map[row][col])>1:
if (br_map[row][col][0][0] in nd_list) or \
(br_map[row][col][0][-1] in nd_list):
del nd_list[nd_list.index(br_map[row][col][0][-1])]
del nd_list[nd_list.index(br_map[row][col][0][0])]
# Check if the parallel branch exists already
# in lp_list
if not check_loop_repeat([[row, col], [row, col]], lp_list):
lp_list.append([[row, col], [row, col]])
# Update the all_loops counter
all_loops+=len(br_map[row][col])-1
# Temp list to make copies
# of loops found
row_vec=[]
for item in curr_lp_iter:
row_vec.append(item)
# Check if an element has been
# encountered before
# not going back and forth that is
if not (([row, col] in row_vec) or [col, row] in row_vec):
# Add the element found
lp_update.append(row_vec)
lp_update[main_loops].append([row, col])
# Update the main loops counter
main_loops+=1
# If an element has not been found
# or is a duplicate, lp_update
# won't contain it.
return [all_loops, main_loops]
def loop_closing(br_map, lp_list, nd_list, lp_update, c1, lp_count):
""" After a loop has been indentified. That is
the first node and the last node are the same.
It is checked whether the loop passes through
nodes that have not been passed through. If not,
loop is directly added. If it does, another
additional check is is the loop has the same elements
as any other loops already found in lp_list. """
# Default is that all nodes have been "found"
# or passed through. A single exception will
# produce a new loop.
nd_exist="found"
for c5 in range(len(lp_update[c1])):
# Go through every branch in the loop
# Take the first and last node of every branch
st_node=br_map[lp_update[c1][c5][0]][lp_update[c1][c5][1]][0][0]
end_node=br_map[lp_update[c1][c5][0]][lp_update[c1][c5][1]][0][-1]
# Check if either are there in nd_list
# Nodes are deleted from nd_list as they are
# found. So if the node is in nd_list
# it means it has not been passed through
if (st_node in nd_list):
nd_exist="not_found"
nd_idx=nd_list.index(st_node)
del nd_list[nd_idx]
if (end_node in nd_list):
nd_exist="not_found"
nd_idx=nd_list.index(end_node)
del nd_list[nd_idx]
if nd_exist=="not_found":
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
else:
# Check if the loop is new even
# if all nodes have been passed through.
lp_exist="found"
if not check_loop_repeat(lp_update[c1], lp_list):
lp_exist="not_found"
if lp_exist=="not_found":
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
return lp_count
def loop_horiz(br_map, nd_list, lp_list, lp_iter, elem, lp_count):
""" Moves horizontally in a loop find.
Looks for every element in a particular column of br_map.
Each element is added onto the exiting loops. """
# lp_list is the loops found.
# lp_iter is the list of loops as they are being identified.
# Those that are loops will be added to lp_list.
no_nodes=len(br_map)
start_row=elem[0]
start_col=elem[1]
# Temp list to make copies
# of exisiting lists
# if elements exist on that row
lp_update=[]
# Counter for number
# of elements found in the row
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element in next column
# to end of matrix
#for c3 in range(loop_column+1, no_nodes):
for c3 in range(0, no_nodes):
curr_elem=[loop_row, c3]
lp_count,c2=loop_addition(br_map, nd_list, lp_list, \
lp_iter[c1], lp_update, curr_elem, lp_count, c2)
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
lp_count=loop_closing(br_map, lp_list, nd_list, lp_update, c1, lp_count)
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
#print lp_update, "Check"
#print lp_iter, "End"
return [lp_count, lp_iter]
def loop_vert(br_map, nd_list, lp_list, lp_iter, elem, lp_count):
""" Moves vertically in a loop find.
Looks for every element in a particular column of br_map.
Each element is added onto the exiting loops. """
# lp_list is the loops found.
# lp_iter is the list of loops as they are being identified.
# Those that are loops will be added to lp_list.
no_nodes=len(br_map)
start_row=elem[0]
start_col=elem[1]
# Temp list to make copies
# of exisiting lists
# if elements exist on that column
lp_update=[]
# Counter for number
# of elements found in the column
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element from first row
# to end of column
for c3 in range(0, no_nodes):
curr_elem=[c3, loop_column]
lp_count,c2=loop_addition(br_map, nd_list, lp_list, \
lp_iter[c1], lp_update, curr_elem, lp_count, c2)
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
lp_count=loop_closing(br_map, lp_list, nd_list, lp_update, c1, lp_count)
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
return [lp_count, lp_iter]
def find_loop(br_map, nd_list, lp_list, lp_iter, elem, lp_count, lp_limit):
"""Find the loops from info on branches and
nodes. The starting point is the first branch in br_map.
The loops found need not be independent loops."""
no_nodes=len(br_map)
# First branch
start_row=elem[0]
start_col=elem[1]
# Move right from that element
# This is the first element
# In a general sense, the direction is horiz
loop_dir="horiz"
# The termination condition is
# that there should not be any element
# in the nd_list. The nodes are deleted
# as a completed loop contains them.
# This is to ensure that all the nodes
# are included in the loops found.
# To ensure that parallel loops between
# a few pair of nodes, do not cause
# loops to be left out, additionally,
# it is checked whether
# Loops < Branches - Nodes + 1
while (nd_list or lp_count<lp_limit):
# Will be executed if we are moving horizontally
if (loop_dir == "horiz"):
lp_count, lp_iter=loop_horiz(br_map, nd_list, lp_list, lp_iter, elem, lp_count)
# Change direction to vertical
loop_dir="vert"
# Will be executed if we are moving vertically
if (loop_dir == "vert"):
lp_count, lp_iter=loop_vert(br_map, nd_list, lp_list, lp_iter, elem, lp_count)
# Change direction to horizontal
loop_dir="horiz"
return lp_count
# Determining the loops
loop_list=[]
loop_count=0
loop_nodes=[]
# Making a copy of node_list
# for finding the loops
for c1 in range(len(node_list)):
loop_nodes.append(node_list[c1])
# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
for c2 in range(c1+1, number_of_nodes):
#check if it exists
if branch_map[c1][c2]:
# Starting branch found
if len(branch_map[c1][c2])>1:
if not check_loop_repeat([[c1, c2], [c1, c2]], loop_list):
loop_list.append([[c1, c2], [c1, c2]])
# Check for parallel branches again.
if (branch_map[c1][c2][0][0] in loop_nodes):
del loop_nodes[loop_nodes.index(branch_map[c1][c2][0][0])]
if (branch_map[c1][c2][0][-1] in loop_nodes):
del loop_nodes[loop_nodes.index(branch_map[c1][c2][0][-1])]
# Check is there are parallel branches between the nodes
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=len(branch_map[c1][c2])-1
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([[c1, c2]])
loop_count=find_loop(branch_map, loop_nodes, loop_list, loop_iter, \
[c1, c2], loop_count, number_of_branches-number_of_nodes+1)
# Remove any repitions in loop_list
for c1 in range(len(loop_list)-1):
for c2 in range(len(loop_list)-1, c1, -1):
if loop_list[c1]==loop_list[c2]:
del loop_list[c2]
# The actual elements from the branches
# to be entered into the loops
loop_branches=[]
# Go through every element in loop_list
for c1 in range(len(loop_list)):
# If the loop has two elements
# it means it is a group of
# parallel branches between nodes
if len(loop_list[c1])==2:
curr_br=loop_list[c1][0]
# Get every permutation of branch pairs possible
for c2 in range(len(branch_map[curr_br[0]][curr_br[1]])-1):
for c3 in range(c2+1, len(branch_map[curr_br[0]][curr_br[1]])):
loop_updt=[]
# Iterate in the forward direction
for c4 in range(len(branch_map[curr_br[0]][curr_br[1]][c2])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][c2][c4])
# Iterate in the reverse direction
for c4 in range(len(branch_map[curr_br[0]][curr_br[1]][c3])-2, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][c3][c4])
loop_branches.append(loop_updt)
else:
loop_updt=[]
# Go through all elements in the loop
for c2 in range(0, len(loop_list[c1])-1):
# Mark two elements in the loop
# The current and the next element
curr_br=loop_list[c1][c2]
curr_br_beg=branch_map[curr_br[0]][curr_br[1]][0][0]
curr_br_end=branch_map[curr_br[0]][curr_br[1]][0][-1]
next_br=loop_list[c1][c2+1]
next_br_beg=branch_map[next_br[0]][next_br[1]][0][0]
next_br_end=branch_map[next_br[0]][next_br[1]][0][-1]
curr_dir="forward"
# Start stringing the branches together
# So if it is the first branch
# Check if the beginning element of the branch
# is the same as the beginning or ending element
# if the next branch
# In that case, the first/current branch
# is to be reversed
if not loop_updt:
if curr_br_beg==next_br_beg or curr_br_beg==next_br_end:
curr_dir="reverse"
# If the loop update is in progress
# check how the current element is linked to
# the last element on the updated loop
else:
if curr_br_end==loop_updt[-1]:
curr_dir="reverse"
# Depending on the direction in which
# an element is to be added to
# the loop.
if curr_dir=="forward":
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
else:
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
# Repeat for the last element
next_dir="forward"
if next_br_end==loop_updt[-1]:
next_dir="reverse"
if next_dir=="forward":
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
else:
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
# Remove any repitions in the elements
# in consecutive elements only
for c3 in range(len(loop_updt)-1, 0, -1):
if loop_updt[c3]==loop_updt[c3-1]:
del loop_updt[c3]
loop_branches.append(loop_updt)
#loop_count=len(loop_branches)
print "Number of nodes",
print number_of_nodes
print "Number of branches",
print number_of_branches
print "Number of loops",
print loop_count
print "*"*50
excel_col="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
excel_dict={}
excel_col_list=excel_col.split(" ")
for c1 in range(26):
excel_dict[c1]=excel_col_list[c1]
for item in loop_branches:
for c1 in range(len(item)):
print str(item[c1][0]+1) + excel_dict[item[c1][1]],
print
view raw enitre_new.py hosted with ❤ by GitHub

Thursday, January 24, 2013

Loop identification - XI

This task never seems to end. Another change in the loop find code.

I was trying out a method where I try to turn at every node in branch_map. However, one major flaw was that the starting point of a loop is the first non-null element in a row in branch_map. Even this will have to be changed to every non-null element in every row in branch_map. So the old code was:

# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
c2=c1+1
#check if it exists
while not branch_map[c1][c2]:
# If not move to next column
c2=c2+1
# Check if the column is within dimensions
if (c2>=number_of_nodes):
# If not, break out and move to next row
break
else:
# Starting branch found
# Check is there are parallel branches between the nodes
for c3 in range(len(branch_map[c1][c2])-1):
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=1
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([[c1, c2]])
loop_count=find_loop(branch_map, loop_list, loop_iter, \
[c1, c2], loop_count)
view raw loop_findold.py hosted with ❤ by GitHub

The new code is:

# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
for c2 in range(c1+1, number_of_nodes):
#check if it exists
if branch_map[c1][c2]:
# Starting branch found
# Check is there are parallel branches between the nodes
for c3 in range(len(branch_map[c1][c2])-1):
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=1
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([[c1, c2]])
loop_count=find_loop(branch_map, loop_list, loop_iter, \
[c1, c2], loop_count)
view raw loop_findnew.py hosted with ❤ by GitHub

So essentially a for loop has been placed that iterates through the entire starting row.

Wednesday, January 23, 2013

Loop identification - X

Back to the circuit:


Result:
>>> ================================ RESTART ===========================
>>>
Number of nodes 4
Number of branches 7
Number of loops 6
**************************************************
4D 3D 2D 1D 1E 1F 1G 1H 2H 3H 4H 5H 6H 7H 8H 9H 9G 9F 9E 9D 8D 7D 6D 5D 4D
4D 3D 2D 1D 1E 1F 2F 3F 4F 4E 4D
4D 3D 2D 1D 1E 1F 1G 1H 2H 3H 4H 5H 6H 7H 8H 9H 9G 9F 9E 9D 8D 7D 7E 7F 6F 5F 4F 4E 4D
4D 3D 2D 1D 1E 1F 2F 3F 4F 5F 6F 7F 7E 7D 6D 5D 4D
4D 5D 6D 7D 7C 7B 7A 6A 5A 4A 4B 4C 4D
4F 4E 4D 5D 6D 7D 7E 7F 6F 5F 4F
>>> node_list
[[0, 5], [3, 3], [3, 5], [6, 3]]



Circuit 4:

Created two more nodes by putting an element at 6G
Result:
>>> ================================ RESTART ====================
>>>
Number of nodes 6
Number of branches 10
Number of loops 8
**************************************************
4D 3D 2D 1D 1E 1F 2F 3F 4F 4E 4D
4D 3D 2D 1D 1E 1F 1G 1H 2H 3H 4H 5H 6H 7H 8H 9H 9G 9F 9E 9D 8D 7D 6D 5D 4D
4D 3D 2D 1D 1E 1F 1G 1H 2H 3H 4H 5H 6H 6G 6F 5F 4F 4E 4D
4D 3D 2D 1D 1E 1F 1G 1H 2H 3H 4H 5H 6H 7H 8H 9H 9G 9F 9E 9D 8D 7D 7E 7F 6F 5F 4F 4E 4D
4D 5D 6D 7D 7C 7B 7A 6A 5A 4A 4B 4C 4D
4F 4E 4D 5D 6D 7D 7E 7F 6F 5F 4F
4F 4E 4D 5D 6D 7D 8D 9D 9E 9F 9G 9H 8H 7H 6H 6G 6F 5F 4F
6H 6G 6F 7F 7E 7D 8D 9D 9E 9F 9G 9H 8H 7H 6H



Circuit 5:


Added a jump statement.
Result:
>>> ================================ RESTART =========================
>>>
Number of nodes 8
Number of branches 13
Number of loops 12
**************************************************
1F 1E 1D 1C 10D 9D 9E 9F 9G 9H 8H 7H 6H 5H 4H 3H 2H 1H 1G 1F
1F 1E 1D 2D 3D 4D 4E 4F 3F 2F 1F
7D 6D 5D 4D 4C 4B 4A 5A 6A 7A 7B 7C 7D
1F 1E 1D 1C 10D 9D 8D 7D 6D 5D 4D 4E 4F 3F 2F 1F
1F 1E 1D 1C 10D 9D 8D 7D 7E 7F 6F 5F 4F 3F 2F 1F
1F 1E 1D 1C 10D 9D 8D 7D 7E 7F 6F 6G 6H 5H 4H 3H 2H 1H 1G 1F
1F 1E 1D 1C 10D 9D 9E 9F 9G 9H 8H 7H 6H 6G 6F 5F 4F 3F 2F 1F
4F 3F 2F 1F 1G 1H 2H 3H 4H 5H 6H 6G 6F 5F 4F
4D 5D 6D 7D 7C 7B 7A 6A 5A 4A 4B 4C 4D
4F 4E 4D 5D 6D 7D 7E 7F 6F 5F 4F
4F 4E 4D 5D 6D 7D 8D 9D 9E 9F 9G 9H 8H 7H 6H 6G 6F 5F 4F
6H 6G 6F 7F 7E 7D 8D 9D 9E 9F 9G 9H 8H 7H 6H



OK. So much for basic circuits. I'll plot some power electronics layout tomrrow and check again.

Loop identification -IX

The last circuit was short of one node because of an error in the node_checking function.

Here is the function:

# A node is defined as a junction of 3 or more branches.
def node_checking(x_mat, x_list, row, col, x_row, x_col):
if ((row==0 and col==0) or (row==x_row-1 and col==x_col-1) or \
(row==0 and col==x_col-1) or (row==x_row-1 and col==0)):
# If its a corner point it can't be a node.
# This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (row==0):
# If it is the first row,
# check if the element in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
# Then check if the element in next row and
# same column is connected. Look for a T junction.
if not (x_mat[row+1][col]==''):
x_list.append([row, col])
if (row==x_row-1):
# If it is the last row,
# check if the elements in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
if not (x_mat[row-1][col]==''):
# Then check if element in the previous row and
# same column is connected. Look for a T junction.
x_list.append([row, col])
if (col==0):
# If it is the first column,
# check if the element in the next column and
# same row is connected.
if not (x_mat[row][col+1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (col==x_col-1):
# If it is the last column,
# check if the element in the previous column and
# same row is connected.
if not (x_mat[row][col-1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (row>0 and row<x_row-1 and col>0 and col<x_col-1):
# If the element is not on the outer boundary
if (x_mat[row][col+1]!='' and x_mat[row][col-1]!=''):
# Check if the elements in next and
# previous columns and same row are connected
if (x_mat[row+1][col]!='' or x_mat[row-1][col]!=''):
# Then check if elements in either the next and
# previous row and same column are connected
x_list.append([row, col])
elif (x_mat[row+1][col]!='' and x_mat[row-1][col]!=''):
# Check if the elements in next and
# previous rows and same column are connected
if (x_mat[row][col+1]!='' or x_mat[row][col-1]!=''):
# Then check if elements in either the next and
# previous column and same row are connected
x_list.append([row, col])
view raw node_def.py hosted with ❤ by GitHub

The difference is caused by the last block:

if (row>0 and row<x_row-1 and col>0 and col<x_col-1):
    # If the element is not on the outer boundary
    if (x_mat[row][col+1]!='' and x_mat[row][col-1]!=''):
        # Check if the elements in next and
        # previous columns and same row are connected
        if (x_mat[row+1][col]!='' or x_mat[row-1][col]!=''):
            # Then check if elements in either the next and
            # previous row and same column are connected
            x_list.append([row, col])
    elif (x_mat[row+1][col]!='' and x_mat[row-1][col]!=''):
        # Check if the elements in next and
        # previous rows and same column are connected
        if (x_mat[row][col+1]!='' or x_mat[row][col-1]!=''):
            # Then check if elements in either the next and
            # previous column and same row are connected
            x_list.append([row, col])
The second elif statement had an extra indent!

Loop identification - VIII

Time for some testing.

Circuit 1:

I deliberately started the circuit from row 3 just to see if it still works.

Result:
>>> ================================ RESTART ===================
>>>
Number of nodes 2
Number of branches 3
Number of loops 3
**************************************************
1D 2D 3D 4D 4E 4F 3F 2F 1F 1E 1D
1D 2D 3D 4D 4C 4B 4A 3A 2A 1A 1B 1C 1D
1D 1E 1F 2F 3F 4F 4E 4D 4C 4B 4A 3A 2A 1A 1B 1C 1D
>>>


Circuit 2:

Three parallel branches between 2 nodes.

Result:
>>> ================================ RESTART =====================
>>>
Number of nodes 2
Number of branches 4
Number of loops 6
**************************************************
3D 4D 5D 6D 6E 6F 5F 4F 3F 3E 3D
3D 4D 5D 6D 7D 8D 8E 8F 8G 8H 7H 6H 5H 4H 3H 2H 1H 1G 1F 1E 1D 2D 3D
3D 4D 5D 6D 6C 6B 6A 5A 4A 3A 3B 3C 3D
3D 3E 3F 4F 5F 6F 6E 6D 7D 8D 8E 8F 8G 8H 7H 6H 5H 4H 3H 2H 1H 1G 1F 1E 1D 2D 3D
3D 3E 3F 4F 5F 6F 6E 6D 6C 6B 6A 5A 4A 3A 3B 3C 3D
3D 2D 1D 1E 1F 1G 1H 2H 3H 4H 5H 6H 7H 8H 8G 8F 8E 8D 7D 6D 6C 6B 6A 5A 4A 3A 3B 3C 3D



Circuit 3:

Result:
>>> ================================ RESTART ======================
>>>
Number of nodes 3
Number of branches 5
Number of loops 3
**************************************************
1F 2F 3F 4F 4E 4D 3D 2D 1D 1E 1F
4D 4E 4F 3F 2F 1F 1G 1H 2H 3H 4H 5H 6H 7H 8H 9H 9G 9F 9E 9D 8D 7D 6D 5D 4D
4D 5D 6D 7D 7C 7B 7A 6A 5A 4A 4B 4C 4D


WRONG!!!!!! Number of nodes is 4.
>>> node_list
[[0, 5], [3, 3], [6, 3]]

So it hasn't picked up [3,5] as a node. Time to check the code!

Loop identification - VII

Another couple of changes. Put in another check for repetitions of loops in loop_list. Also, took care of more than two parallel branches possible between two nodes.

Another major comment. If the number of nodes (including the reference or ground node) is N and the number of branches is B, the number of independent loops will be B-N+1. However, while trying to generate just that many number of independent loops, the code was beginning to fail. So the code posted will show all the possible "distinct" loops out of which many of them will simply be linear combinations of the others. I hope this will get sorted out while solving the equations, since the upper triangularization of the matrices will result in a number of rows to be zero. Anyway, this comes later.

As before, click on "view raw" to see the code that goes out of the box.


# Remove any repitions in loop_list
for c1 in range(len(loop_list)-1):
for c2 in range(len(loop_list)-1, c1, -1):
if loop_list[c1]==loop_list[c2]:
del loop_list[c2]
# The actual elements from the branches
# to be entered into the loops
loop_branches=[]
# Go through every element in loop_list
for c1 in range(len(loop_list)):
# If the loop has two elements
# it means it is a group of
# parallel branches between nodes
if len(loop_list[c1])==2:
curr_br=loop_list[c1][0]
# Get every permutation of branch pairs possible
for c2 in range(len(branch_map[curr_br[0]][curr_br[1]])-1):
for c3 in range(c2+1, len(branch_map[curr_br[0]][curr_br[1]])):
loop_updt=[]
# Iterate in the forward direction
for c4 in range(len(branch_map[curr_br[0]][curr_br[1]][c2])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][c2][c4])
# Iterate in the reverse direction
for c4 in range(len(branch_map[curr_br[0]][curr_br[1]][c3])-2, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][c3][c4])
loop_branches.append(loop_updt)
else:
loop_updt=[]
# Go through all elements in the loop
for c2 in range(0, len(loop_list[c1])-1):
# Mark two elements in the loop
# The current and the next element
curr_br=loop_list[c1][c2]
curr_br_beg=branch_map[curr_br[0]][curr_br[1]][0][0]
curr_br_end=branch_map[curr_br[0]][curr_br[1]][0][-1]
next_br=loop_list[c1][c2+1]
next_br_beg=branch_map[next_br[0]][next_br[1]][0][0]
next_br_end=branch_map[next_br[0]][next_br[1]][0][-1]
curr_dir="forward"
# Start stringing the branches together
# So if it is the first branch
# Check if the beginning element of the branch
# is the same as the beginning or ending element
# if the next branch
# In that case, the first/current branch
# is to be reversed
if not loop_updt:
if curr_br_beg==next_br_beg or curr_br_beg==next_br_end:
curr_dir="reverse"
# If the loop update is in progress
# check how the current element is linked to
# the last element on the updated loop
else:
if curr_br_end==loop_updt[-1]:
curr_dir="reverse"
# Depending on the direction in which
# an element is to be added to
# the loop.
if curr_dir=="forward":
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
else:
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
# Repeat for the last element
next_dir="forward"
if next_br_end==loop_updt[-1]:
next_dir="reverse"
if next_dir=="forward":
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
else:
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
# Remove any repitions in the elements
# in consecutive elements only
for c3 in range(len(loop_updt)-1, 0, -1):
if loop_updt[c3]==loop_updt[c3-1]:
del loop_updt[c3]
loop_branches.append(loop_updt)
loop_count=len(loop_branches)
print "Number of nodes",
print number_of_nodes
print "Number of branches",
print number_of_branches
print "Number of loops",
print loop_count
print "*"*50
excel_col="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
excel_dict={}
excel_col_list=excel_col.split(" ")
for c1 in range(26):
excel_dict[c1]=excel_col_list[c1]
for item in loop_branches:
for c1 in range(len(item)):
print str(item[c1][0]+1) + excel_dict[item[c1][1]],
print
view raw loop.br.py hosted with ❤ by GitHub

Tuesday, January 22, 2013

Loop identification - VI

Before I start checking whether the results of the loop identification code is correct, a small addition to generate the sequence of elements in a loop and also to generate them in a manner that they can read off directly from the spread sheet describing the circuit.

Here is the added code. The final code I'll put up again after verification.

Click on "View Raw" at the bottom of the box to see the entire code that goes out view.

loop_branches=[]
for c1 in range(len(loop_list)):
if len(loop_list[c1])==2:
loop_updt=[]
#for c2 in range(2):
curr_br=loop_list[c1][0]
for c2 in range(len(branch_map[curr_br[0]][curr_br[1]][0])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c2])
for c2 in range(len(branch_map[curr_br[0]][curr_br[1]][1])-2, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][1][c2])
else:
loop_updt=[]
for c2 in range(0, len(loop_list[c1])-1):
curr_br=loop_list[c1][c2]
curr_br_beg=branch_map[curr_br[0]][curr_br[1]][0][0]
curr_br_end=branch_map[curr_br[0]][curr_br[1]][0][-1]
next_br=loop_list[c1][c2+1]
next_br_beg=branch_map[next_br[0]][next_br[1]][0][0]
next_br_end=branch_map[next_br[0]][next_br[1]][0][-1]
curr_dir="forward"
if not loop_updt:
if curr_br_beg==next_br_beg or curr_br_beg==next_br_end:
curr_dir="reverse"
else:
if curr_br_end==loop_updt[-1]:
curr_dir="reverse"
if curr_dir=="forward":
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
else:
for c3 in range(len(branch_map[curr_br[0]][curr_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[curr_br[0]][curr_br[1]][0][c3])
next_dir="forward"
if next_br_end==loop_updt[-1]:
next_dir="reverse"
if next_dir=="forward":
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
else:
for c3 in range(len(branch_map[next_br[0]][next_br[1]][0])-1, -1, -1):
loop_updt.append(branch_map[next_br[0]][next_br[1]][0][c3])
for c3 in range(len(loop_updt)-1, 0, -1):
if loop_updt[c3]==loop_updt[c3-1]:
del loop_updt[c3]
loop_branches.append(loop_updt)
excel_col="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
excel_dict={}
excel_col_list=excel_col.split(" ")
for c1 in range(26):
excel_dict[c1]=excel_col_list[c1]
for item in loop_branches:
for c1 in range(len(item)):
print str(item[c1][0]+1) + excel_dict[item[c1][1]],
print

Thursday, January 17, 2013

Loop identification - V

Code is ready but roughly written. Seems to work with 3 different types of circuits. But still need to test it out.

Here is the code. Click on "View Raw" at the bottom of the box to see the entire code that goes out of the page.

#! /usr/bin/env python
import sys, math, matrix
new_file = open("testckt.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire"
# where a zero impedance direct connection exists.
# Where no connection nor device
#(resitor, inductor etc) exists, a '' will be found.
# The devices will be strings.
# Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# Remove any leading or trailing quotes
# and also carriage returns (\n) that
# may have been added while generating the csv file.
def scrub_elements(x, row, col):
if x[row][col]:
if "\n" in x[row][col]:
x[row][col]=x[row][col][:-1]
if x[row][col]:
while (x[row][col][0]=='"' or x[row][col][0]=="'"):
x[row][col]=x[row][col][1:]
while (x[row][col][-1]=='"' or x[row][col][-1]=="'"):
x[row][col]=x[row][col][:-1]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
scrub_elements(conn_matrix, c1, c2)
# List of jumps labels
jump_list=[]
# Structure of jump_list
# row, column, jump_label, direction
# Check is it a jump, an element
# or simply no connection
def jump_sanity(x, x_jump, row, column):
x_elem = x[row][column]
if (x_elem ==''):
del x_jump["exist"]
del x_jump["jump"]
elif (len(x_elem)>3):
if (x_elem.lower()[0:4] == "jump"):
del x_jump["exist"]
else:
del x_jump["jump"]
else:
del x_jump["jump"]
# Check for jump label sanity and
# add a list of elements where jumps exist.
# Basically examines whether element (c1, c2)
# is a jump and what are the elements
# around it.
def jump_checking(x_matrix, x_jump, row, col, no_rows, no_cols):
# Current element
curr_element = {"exist":0, "jump":1}
# Determine if it is a jump label
jump_sanity(x_matrix, curr_element, row, col)
if ("jump" in curr_element):
# If so, what is the element in the same column
# and next row
if (row<no_rows-1):
next_row_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, next_row_element, row+1, col)
else:
next_row_element = {}
# If so, what is the element in the same column
# and previous row
if (row>0):
prev_row_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, prev_row_element, row-1, col)
else:
prev_row_element = {}
# If so, what is the element in the same row
# and next column
if (col<no_cols-1):
next_col_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, next_col_element, row, col+1)
else:
next_col_element = {}
# If so, what is the element in the same row
# and previous column
if (col>0):
prev_col_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, prev_col_element, row, col-1)
else:
prev_col_element = {}
# Check if two jumps are next to each other
if ("jump" in next_row_element or "jump" in next_col_element or \
"jump" in prev_row_element or "jump" in prev_col_element):
print "Two jumps can't be adjacent to each other."
print "Check jump at row %d, column %d" %(row, col)
# Jump must have only one element adjacent to it.
if ("exist" in next_row_element):
if ("exist" in next_col_element or "exist" in prev_row_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "down"])
elif ("exist" in next_col_element):
if ("exist" in next_row_element or "exist" in prev_row_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "right"])
elif ("exist" in prev_row_element):
if ("exist" in next_row_element or "exist" in next_col_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "up"])
elif ("exist" in prev_col_element):
if ("exist" in next_row_element or "exist" in next_col_element or \
"exist" in prev_row_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "left"])
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
jump_checking(conn_matrix, jump_list, c1, c2, conn_rows, conn_columns)
# Create a dictionary of jumps -
# for each jump label - there is a list with two elements.
jump_matrix={}
# Structure of jump_matrix
# label: [[[row, col], "dir"], [[row, col], "dir"]]
for c1 in range(len(jump_list)):
jump_count=1
for c2 in range(len(jump_list)):
if not c1==c2:
if jump_list[c1][2]==jump_list[c2][2]:
frst_jmp = jump_list[c1]
scd_jmp = jump_list[c2]
jump_matrix[frst_jmp[2]]=[[[frst_jmp[0], frst_jmp[1]], frst_jmp[3]],\
[[scd_jmp[0], scd_jmp[1]], scd_jmp[3]]]
jump_count=jump_count+1
if (jump_count<2):
print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
elif (jump_count>2):
print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
del jump_matrix[jump_list[c1][2]]
# A node is defined as a junction of 3 or more branches.
def node_checking(x_mat, x_list, row, col, x_row, x_col):
if ((row==0 and col==0) or (row==x_row-1 and col==x_col-1) or \
(row==0 and col==x_col-1) or (row==x_row-1 and col==0)):
# If its a corner point it can't be a node.
# This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (row==0):
# If it is the first row,
# check if the element in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
# Then check if the element in next row and
# same column is connected. Look for a T junction.
if not (x_mat[row+1][col]==''):
x_list.append([row, col])
if (row==x_row-1):
# If it is the last row,
# check if the elements in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
if not (x_mat[row-1][col]==''):
# Then check if element in the previous row and
# same column is connected. Look for a T junction.
x_list.append([row, col])
if (col==0):
# If it is the first column,
# check if the element in the next column and
# same row is connected.
if not (x_mat[row][col+1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (col==x_col-1):
# If it is the last column,
# check if the element in the previous column and
# same row is connected.
if not (x_mat[row][col-1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (row>0 and row<x_row-1 and col>0 and col<x_col-1):
# If the element is not on the outer boundary
if (x_mat[row][col+1]!='' and x_mat[row][col-1]!=''):
# Check if the elements in next and
# previous columns and same row are connected
if (x_mat[row+1][col]!='' or x_mat[row-1][col]!=''):
# Then check if elements in either the next and
# previous row and same column are connected
x_list.append([row, col])
elif (x_mat[row+1][col]!='' and x_mat[row-1][col]!=''):
if (x_mat[row][col+1]!='' or x_mat[row][col-1]!=''):
x_list.append([row, col])
node_list=[]
# Structure of node_list
# [row, column]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
jump_sanity(conn_matrix, curr_element, c1, c2)
if ("exist" in curr_element):
node_checking(conn_matrix, node_list, c1, c2, conn_rows, conn_columns)
else:
pass
# This list contains all the nodes that are T or + junctions.
#print "*"*60
#print node_list
#print "*"*60
# Map of branches between nodes in node_list
branch_map=[]
# Creating an square of the dimension of node_list.
# Each element will be a list of the
# series connection of branches between the nodes.
for c1 in range(len(node_list)):
branch_rows=[]
for c2 in range(len(node_list)):
branch_rows.append([])
branch_map.append(branch_rows)
# Generate a search rule for each node.
# The concept is to start at a node and
# search until another node is reached.
node_iter_rule=[]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
iter_rule={"left":0, "down":1, "right":2, "up":3}
# For nodes in the outer edges,
# the rules going outwards will be removed.
if (node_row==0):
del(iter_rule["up"])
if (node_row==conn_rows-1):
del(iter_rule["down"])
if (node_column==0):
del(iter_rule["left"])
if (node_column==conn_columns-1):
del(iter_rule["right"])
# Depending on the non-existence of elements
# in a direction, those rules will be removed.
if (node_row>0) and (node_row<conn_rows-1) and \
(node_column>0) and (node_column<conn_columns-1):
if (conn_matrix[node_row-1][node_column]==''):
del(iter_rule["up"])
if (conn_matrix[node_row+1][node_column]==''):
del(iter_rule["down"])
if (conn_matrix[node_row][node_column+1]==''):
del(iter_rule["right"])
if (conn_matrix[node_row][node_column-1]==''):
del(iter_rule["left"])
node_iter_rule.append(iter_rule)
def jump_node_check(x_mat, x_list, jdir, row):
n_row=x_list[c1][0]
n_col=x_list[c1][1]
if (jdir=="up"):
if (len(x_mat[n_row-1][n_col])>3):
if (x_mat[n_row-1][n_col].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row-1, n_col)
if (jdir=="down"):
if (len(x_mat[n_row+1][n_col])>3):
if (x_mat[n_row+1][n_col].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row+1, n_col)
if (jdir=="left"):
if (len(x_mat[n_row][n_col-1])>3):
if (x_mat[n_row][n_col-1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row, n_col-1)
if (jdir=="right"):
if (len(x_mat[n_row][n_col+1])>3):
if (x_mat[n_row][n_col+1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row, n_col+1)
# Check if a jump is not next to a node.
for c1 in range(len(node_list)):
for jump_check_dir in node_iter_rule[c1].keys():
jump_node_check(conn_matrix, node_list, jump_check_dir, c1)
# For each node in node_list perform the search operation.
# Each node has a list of possible search rules.
# Perform a search for each rule.
# From the starting node, advance in the direction of the rule.
# After advancing, check if the next element is a node.
# If it is a node, stop.
# If it is not a node, there can be only two directions of movement.
# Move in a direction and check is an element exists.
# If it exists, check if it is not already an element encountered -
# shouldn't be moving backwards.
# If a new element is encountered,
# update the element is branch iter and continue.
def jump_move(x_mat, x_jump, x_element, pos):
jump_trace=x_mat[x_element[0]][x_element[1]]
if (x_jump[jump_trace][pos][1] == "left"):
nxt_row=x_jump[jump_trace][pos][0][0]
nxt_col=x_jump[jump_trace][pos][0][1] - 1
jmp_exec="left"
elif (x_jump[jump_trace][pos][1] == "right"):
nxt_row=x_jump[jump_trace][pos][0][0]
nxt_col=x_jump[jump_trace][pos][0][1] + 1
jmp_exec="right"
elif (x_jump[jump_trace][pos][1] == "up"):
nxt_row=x_jump[jump_trace][pos][0][0] - 1
nxt_col=x_jump[jump_trace][pos][0][1]
jmp_exec="up"
elif (x_jump[jump_trace][pos][1] == "down"):
nxt_row=x_jump[jump_trace][pos][0][0] + 1
nxt_col=x_jump[jump_trace][pos][0][1]
jmp_exec="down"
return [jmp_exec, nxt_row, nxt_col]
def branch_jump(x_mat, x_jump, x_element):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and
# the sense of movement.
# Depending on the sense of movement, update
# the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement
# has taken place
# To ensure that we don't go back
# from the next element after the jump.
nxt_row=x_element[0]
nxt_col=x_element[1]
jump_exec=""
if (len(x_mat[nxt_row][nxt_col])>3):
if (x_mat[nxt_row][nxt_col].lower()[0:4] == "jump"):
jump_trace=x_mat[nxt_row][nxt_col]
if (x_jump[jump_trace][0][0] == [nxt_row, nxt_col]):
jump_exec, nxt_row, nxt_col = \
jump_move(x_mat, x_jump, x_element, 1)
elif (x_jump[jump_trace][1][0] == [nxt_row, nxt_col]):
jump_exec, nxt_row, nxt_col = \
jump_move(x_mat, x_jump, x_element, 0)
return [jump_exec, nxt_row, nxt_col]
# Advancing one element in a branch
# Checking for jump direction
# to make sure we don't go back
def branch_advance(x_mat, x_iter, nxt_elem, jmp_exec, x_rows, x_cols):
nxt_row=nxt_elem[0]
nxt_col=nxt_elem[1]
# This temporary variable is to ensure,
# two advancements don't take place in one loop.
branch_proceed=0
if ((nxt_col>0) and branch_proceed==0):
# We are trying to go left, so check if we didn't jump right.
if (x_mat[nxt_row][nxt_col-1] != '' and jmp_exec!="right"):
# Next check is if we are going backwards.
if not ([nxt_row, nxt_col-1] in x_iter):
nxt_col=nxt_col-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_row>0) and branch_proceed==0):
# We are trying to go up, so check if we didn't jump down.
if (x_mat[nxt_row-1][nxt_col] != '' and jmp_exec!="down"):
if not ([nxt_row-1, nxt_col] in x_iter):
nxt_row=nxt_row-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_col<x_cols-1) and branch_proceed==0):
# We are trying to go right, so check if we didn't jump left.
if (x_mat[nxt_row][nxt_col+1] != '' and jmp_exec!="left"):
if not ([nxt_row, nxt_col+1] in x_iter):
nxt_col=nxt_col+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_row<x_rows-1) and branch_proceed==0):
# We are trying to go down, so check if we didn't jump up.
if (x_mat[nxt_row+1][nxt_col] != '' and jmp_exec!="up"):
if not ([nxt_row+1, nxt_col] in x_iter):
nxt_row=nxt_row+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
return [jmp_exec, nxt_row, nxt_col]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
# This variable is used when jumps are encountered.
jump_executed=""
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and
# the sense of movement.
# Depending on the sense of movement, update
# the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement
# has taken place
# To ensure that we don't go back
# from the next element after the jump.
next_element = [next_node_row, next_node_column]
jump_executed, next_node_row, next_node_column = \
branch_jump(conn_matrix, jump_matrix, next_element)
branch_iter.append([next_node_row, next_node_column])
next_element = [next_node_row, next_node_column]
jump_executed, next_node_row, next_node_column = \
branch_advance(conn_matrix, branch_iter, next_element, \
jump_executed, conn_rows, conn_columns)
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches. \
Check at row %d column %d" %(next_node_row, next_node_column)
break
else:
branch_iter.append([next_node_row, next_node_column])
next_elem_index=node_list.index([next_node_row, next_node_column])
branch_map[c1][next_elem_index].append(branch_iter)
nw_look=open("nw_check.csv","w")
for c1 in range(len(node_list)):
for c2 in range(len(node_list)-1):
if (branch_map[c1][c2]):
for c3 in range(len(branch_map[c1][c2])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2][c3])):
nw_look.write("[%d %d] ;" \
%(branch_map[c1][c2][c3][c4][0], branch_map[c1][c2][c3][c4][1]))
nw_look.write(")")
nw_look.write(", ")
else:
nw_look.write("[], ")
if (branch_map[c1][c2+1]):
for c3 in range(len(branch_map[c1][c2+1])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2+1][c3])):
nw_look.write("[%d %d] ;" \
%(branch_map[c1][c2+1][c3][c4][0], branch_map[c1][c2+1][c3][c4][1]))
nw_look.write(")")
nw_look.write("\n")
else:
nw_look.write("[] \n")
##for c1 in range(len(node_list)):
## for c2 in range(len(node_list)-1):
## nw_look.write("%s ;" %(branch_map[c1][c2]))
## nw_look.write("%s \n" %(branch_map[c1][c2+1]))
nw_look.close()
number_of_nodes=len(node_list)
number_of_branches=0
for c1 in range(len(node_list)):
for c2 in range(c1+1, len(node_list)):
for parallel_branches in branch_map[c1][c2]:
number_of_branches+=1
# Determining the loops
loop_list=[]
loop_count = 0
def find_loop(br_map, lp_list, lp_iter, elem, lp_count):
no_nodes=len(br_map)
# Move right from that element
# This is the first element
loop_dir="right"
start_row=elem[0]
start_col=elem[1]
# The termination condition is
# that there should not be any element
# in the lp_iter list
# So no further elements to consider
while (lp_iter):
# Will be executed if we are moving right
if (loop_dir == "right"):
# Temp list to make copies
# of exisiting lists
# if elements exist on that row
lp_update=[]
# Counter for number
# of elements found in the row
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element in next column
# to end of matrix
for c3 in range(loop_column+1, no_nodes):
# If element exists
if br_map[loop_row][c3]:
# Check for parallel branches again.
for c4 in range(len(br_map[loop_row][loop_column])-1):
lp_list.append([[loop_row, loop_column], [loop_row, loop_column]])
lp_count+=1
# Temp list to make copies
# of loops found
row_vec=[]
for item in lp_iter[c1]:
row_vec.append(item)
# Check if an element has been
# encountered before
# not going back and forth that is
if not (([loop_row, c3] in row_vec) or [c3, loop_row] in row_vec):
# Add the element found
lp_update.append(row_vec)
lp_update[c2].append([loop_row, c3])
c2+=1
# If an element has not been found
# or is a duplicate, lp_update
# won't contain it.
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
# Move down
loop_dir="down"
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
print lp_iter
print lp_update
print loop_dir
# Will be executed if we are moving down
if (loop_dir == "down"):
# Temp list to make copies
# of exisiting lists
# if elements exist on that column
lp_update=[]
# Counter for number
# of elements found in the column
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element in next row
# to end of matrix
for c3 in range(loop_row+1, no_nodes):
# Check if an element exists there
if br_map[c3][loop_column]:
# Check for parallel branches again.
for c4 in range(len(br_map[loop_row][loop_column])-1):
lp_list.append([[loop_row, loop_column], [loop_row, loop_column]])
lp_count+=1
# Temp list to make copies
# of loops found
row_vec=[]
for item in lp_iter[c1]:
row_vec.append(item)
# Check if an element has been
# encountered before
# not going back and forth that is
if not (([c3, loop_column] in row_vec) or [loop_column, c3] in row_vec):
# Add the element found
lp_update.append(row_vec)
lp_update[c2].append([c3, loop_column])
c2+=1
# If an element has not been found
# or is a duplicate, lp_update
# won't contain it.
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
# Move left
loop_dir="left"
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
print lp_iter
print lp_update
print loop_dir
# Will be executed if we are moving left
if (loop_dir == "left"):
# Temp list to make copies
# of exisiting lists
# if elements exist on that row
lp_update=[]
# Counter for number
# of elements found in the row
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element in previous column
# to the column of the starting element
for c3 in range(loop_column-1, lp_iter[c1][0][1]-1, -1):
# Check if an element exists there
if br_map[loop_row][c3]:
# Check for parallel branches again.
for c4 in range(len(br_map[loop_row][loop_column])-1):
lp_list.append([[loop_row, loop_column], [loop_row, loop_column]])
lp_count+=1
# Temp list to make copies
# of loops found
row_vec=[]
for item in lp_iter[c1]:
row_vec.append(item)
# Check if an element has been
# encountered before
# not going back and forth that is
if not (([loop_row, c3] in row_vec) or [c3, loop_row] in row_vec):
# Add the element found
lp_update.append(row_vec)
lp_update[c2].append([loop_row, c3])
c2+=1
# If an element has not been found
# or is a duplicate, lp_update
# won't contain it.
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
# Add that loop to loop list
lp_list.append(lp_update[c1])
# Remove the loop from the temp
# variable.
del lp_update[c1]
lp_count+=1
# Move up
loop_dir="up"
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
print lp_iter
print lp_update
print loop_dir
# Will be executed if we are moving up
if (loop_dir == "up"):
# Temp list to make copies
# of exisiting lists
# if elements exist on that column
lp_update=[]
# Counter for number
# of elements found in the column
c2=0
for c1 in range(len(lp_iter)):
# Set loop row and counter
# to the latest element
# in lp_iter
loop_row=lp_iter[c1][-1][0]
loop_column=lp_iter[c1][-1][1]
# Start from element in previous row
# to row after the starting element
for c3 in range(loop_row-1, lp_iter[c1][0][0], -1):
# Check if an element exists there
if br_map[c3][loop_column]:
# Check for parallel branches again.
for c4 in range(len(br_map[loop_row][loop_column])-1):
lp_list.append([[loop_row, loop_column], [loop_row, loop_column]])
lp_count+=1
# Temp list to make copies
# of loops found
row_vec=[]
for item in lp_iter[c1]:
row_vec.append(item)
# Check if an element has been
# encountered before
# not going back and forth that is
if not (([c3, loop_column] in row_vec) or [loop_column, c3] in row_vec):
# Add the element found
lp_update.append(row_vec)
lp_update[c2].append([c3, loop_column])
c2+=1
# If an element has not been found
# or is a duplicate, lp_update
# won't contain it.
for c1 in range(len(lp_update)-1, -1, -1):
# End condition
# Latest element has ending or starting node
# Same as last element of first branch
last_elem_frst=br_map[start_row][start_col][0][-1]
frst_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][0]
last_elem_curr=br_map[lp_update[c1][-1][0]][lp_update[c1][-1][1]][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
lp_list.append(lp_update[c1])
del lp_update[c1]
lp_count+=1
# Move left
loop_dir="left"
# lp_iter will be the same as lp_update
lp_iter=[]
for c1 in range(len(lp_update)):
lp_iter.append(lp_update[c1])
# lp_iter contains ongoing loops
# Closed loops are moved to lp_list
# Broken loops are dropped
print lp_iter
print lp_update
print loop_dir
return lp_count
# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
c2=c1+1
#check if it exists
while not branch_map[c1][c2]:
# If not move to next column
c2=c2+1
# Check if the column is within dimensions
if (c2>=number_of_nodes):
# If not, break out and move to next row
break
else:
# Starting branch found
# Check is there are parallel branches between the nodes
for c3 in range(len(branch_map[c1][c2])-1):
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=1
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([[c1, c2]])
loop_count=find_loop(branch_map, loop_list, loop_iter, \
[c1, c2], loop_count)
print loop_count
print loop_list
for item in loop_list:
print item
view raw loop.py hosted with ❤ by GitHub

Wednesday, January 16, 2013

Loop identification - IV

An error in the previous code. The code fails with certain types of circuits. This is why:

I don't move right except after the first element after the diagonal. This is OK as long as I cover all elements with each movement. That is when I am moving down, all existing elements must be covered. When left, and up also. But I am only touching the nearest element. Which will only work when the loops connect the closest nodes together.

So, the code will have to be rewritten and significantly. The logic will be:

1. Start from the first element after the diagonal. Check how many elements exist in that row and create that many lists with these two elements.

2. For each of these lists, look "down" and see how many elements exist in that column. Create those many copies of the original list with three elements now and so on.

3. The termination condition will be is a loop is found or if no other element is found.

This will need repeated copies of lists.

Monday, January 14, 2013

Loop identification - III

No update as such. Just cleaned up the code a bit. Broke up the code into functions to reduce the level of indents. The idea is try to fit the code in the visible window but I see from the preview that its still going beyond it. I guess I can't rewrite the code again.

Here is the code. Click on "View Raw" if you need to see the entire code.

#! /usr/bin/env python
import sys, math, matrix
new_file = open("testckt2.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire"
# where a zero impedance direct connection exists.
# Where no connection nor device
#(resitor, inductor etc) exists, a '' will be found.
# The devices will be strings.
# Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# Remove any leading or trailing quotes
# and also carriage returns (\n) that
# may have been added while generating the csv file.
def scrub_elements(x, row, col):
if x[row][col]:
if "\n" in x[row][col]:
x[row][col]=x[row][col][:-1]
if x[row][col]:
while (x[row][col][0]=='"' or x[row][col][0]=="'"):
x[row][col]=x[row][col][1:]
while (x[row][col][-1]=='"' or x[row][col][-1]=="'"):
x[row][col]=x[row][col][:-1]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
scrub_elements(conn_matrix, c1, c2)
# List of jumps labels
jump_list=[]
# Structure of jump_list
# row, column, jump_label, direction
# Check is it a jump, an element
# or simply no connection
def jump_sanity(x, x_jump, row, column):
x_elem = x[row][column]
if (x_elem ==''):
del x_jump["exist"]
del x_jump["jump"]
elif (len(x_elem)>3):
if (x_elem.lower()[0:4] == "jump"):
del x_jump["exist"]
else:
del x_jump["jump"]
else:
del x_jump["jump"]
# Check for jump label sanity and
# add a list of elements where jumps exist.
# Basically examines whether element (c1, c2)
# is a jump and what are the elements
# around it.
def jump_checking(x_matrix, x_jump, row, col, no_rows, no_cols):
# Current element
curr_element = {"exist":0, "jump":1}
# Determine if it is a jump label
jump_sanity(x_matrix, curr_element, row, col)
if ("jump" in curr_element):
# If so, what is the element in the same column
# and next row
if (row<no_rows-1):
next_row_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, next_row_element, row+1, col)
else:
next_row_element = {}
# If so, what is the element in the same column
# and previous row
if (row>0):
prev_row_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, prev_row_element, row-1, col)
else:
prev_row_element = {}
# If so, what is the element in the same row
# and next column
if (col<no_cols-1):
next_col_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, next_col_element, row, col+1)
else:
next_col_element = {}
# If so, what is the element in the same row
# and previous column
if (col>0):
prev_col_element = {"exist":0, "jump":1}
jump_sanity(x_matrix, prev_col_element, row, col-1)
else:
prev_col_element = {}
21# Check if two jumps are next to each other
if ("jump" in next_row_element or "jump" in next_col_element or \
"jump" in prev_row_element or "jump" in prev_col_element):
print "Two jumps can't be adjacent to each other."
print "Check jump at row %d, column %d" %(row, col)
# Jump must have only one element adjacent to it.
if ("exist" in next_row_element):
if ("exist" in next_col_element or "exist" in prev_row_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "down"])
elif ("exist" in next_col_element):
if ("exist" in next_row_element or "exist" in prev_row_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "right"])
elif ("exist" in prev_row_element):
if ("exist" in next_row_element or "exist" in next_col_element or \
"exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "up"])
elif ("exist" in prev_col_element):
if ("exist" in next_row_element or "exist" in next_col_element or \
"exist" in prev_row_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(row, col)
else:
x_jump.append([row, col, x_matrix[row][col], "left"])
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
jump_checking(conn_matrix, jump_list, c1, c2, conn_rows, conn_columns)
# Create a dictionary of jumps -
# for each jump label - there is a list with two elements.
jump_matrix={}
# Structure of jump_matrix
# label: [[[row, col], "dir"], [[row, col], "dir"]]
for c1 in range(len(jump_list)):
jump_count=1
for c2 in range(len(jump_list)):
if not c1==c2:
if jump_list[c1][2]==jump_list[c2][2]:
frst_jmp = jump_list[c1]
scd_jmp = jump_list[c2]
jump_matrix[frst_jmp[2]]=[[[frst_jmp[0], frst_jmp[1]], frst_jmp[3]],\
[[scd_jmp[0], scd_jmp[1]], scd_jmp[3]]]
jump_count=jump_count+1
if (jump_count<2):
print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
elif (jump_count>2):
print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
del jump_matrix[jump_list[c1][2]]
# A node is defined as a junction of 3 or more branches.
def node_checking(x_mat, x_list, row, col, x_row, x_col):
if ((row==0 and col==0) or (row==x_row-1 and col==x_col-1) or \
(row==0 and col==x_col-1) or (row==x_row-1 and col==0)):
# If its a corner point it can't be a node.
# This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (row==0):
# If it is the first row,
# check if the element in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
# Then check if the element in next row and
# same column is connected. Look for a T junction.
if not (x_mat[row+1][col]==''):
x_list.append([row, col])
if (row==x_row-1):
# If it is the last row,
# check if the elements in the next and
# previous columns and same row are connected.
if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''):
if not (x_mat[row-1][col]==''):
# Then check if element in the previous row and
# same column is connected. Look for a T junction.
x_list.append([row, col])
if (col==0):
# If it is the first column,
# check if the element in the next column and
# same row is connected.
if not (x_mat[row][col+1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (col==x_col-1):
# If it is the last column,
# check if the element in the previous column and
# same row is connected.
if not (x_mat[row][col-1]==''):
# Then check if the elements in next and
# previous row and same column are connected.
# Look for a T junction.
if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''):
x_list.append([row, col])
if (row>0 and row<x_row-1 and col>0 and col<x_col-1):
# If the element is not on the outer boundary
if (x_mat[row][col+1]!='' and x_mat[row][col-1]!=''):
# Check if the elements in next and
# previous columns and same row are connected
if (x_mat[row+1][col]!='' or x_mat[row-1][col]!=''):
# Then check if elements in either the next and
# previous row and same column are connected
x_list.append([row, col])
elif (x_mat[row+1][col]!='' and x_mat[row-1][col]!=''):
if (x_mat[row][col+1]!='' or x_mat[row][col-1]!=''):
x_list.append([row, col])
node_list=[]
# Structure of node_list
# [row, column]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
jump_sanity(conn_matrix, curr_element, c1, c2)
if ("exist" in curr_element):
node_checking(conn_matrix, node_list, c1, c2, conn_rows, conn_columns)
else:
pass
# This list contains all the nodes that are T or + junctions.
#print "*"*60
#print node_list
#print "*"*60
# Map of branches between nodes in node_list
branch_map=[]
# Creating an square of the dimension of node_list.
# Each element will be a list of the
# series connection of branches between the nodes.
for c1 in range(len(node_list)):
branch_rows=[]
for c2 in range(len(node_list)):
branch_rows.append([])
branch_map.append(branch_rows)
# Generate a search rule for each node.
# The concept is to start at a node and
# search until another node is reached.
node_iter_rule=[]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
iter_rule={"left":0, "down":1, "right":2, "up":3}
# For nodes in the outer edges,
# the rules going outwards will be removed.
if (node_row==0):
del(iter_rule["up"])
if (node_row==conn_rows-1):
del(iter_rule["down"])
if (node_column==0):
del(iter_rule["left"])
if (node_column==conn_columns-1):
del(iter_rule["right"])
# Depending on the non-existence of elements
# in a direction, those rules will be removed.
if (node_row>0) and (node_row<conn_rows-1) and \
(node_column>0) and (node_column<conn_columns-1):
if (conn_matrix[node_row-1][node_column]==''):
del(iter_rule["up"])
if (conn_matrix[node_row+1][node_column]==''):
del(iter_rule["down"])
if (conn_matrix[node_row][node_column+1]==''):
del(iter_rule["right"])
if (conn_matrix[node_row][node_column-1]==''):
del(iter_rule["left"])
node_iter_rule.append(iter_rule)
def jump_node_check(x_mat, x_list, jdir, row):
n_row=x_list[c1][0]
n_col=x_list[c1][1]
if (jdir=="up"):
if (len(x_mat[n_row-1][n_col])>3):
if (x_mat[n_row-1][n_col].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row-1, n_col)
if (jdir=="down"):
if (len(x_mat[n_row+1][n_col])>3):
if (x_mat[n_row+1][n_col].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row+1, n_col)
if (jdir=="left"):
if (len(x_mat[n_row][n_col-1])>3):
if (x_mat[n_row][n_col-1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row, n_col-1)
if (jdir=="right"):
if (len(x_mat[n_row][n_col+1])>3):
if (x_mat[n_row][n_col+1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. \
Check jump at row %d column %d." %(n_row, n_col+1)
# Check if a jump is not next to a node.
for c1 in range(len(node_list)):
for jump_check_dir in node_iter_rule[c1].keys():
jump_node_check(conn_matrix, node_list, jump_check_dir, c1)
# For each node in node_list perform the search operation.
# Each node has a list of possible search rules.
# Perform a search for each rule.
# From the starting node, advance in the direction of the rule.
# After advancing, check if the next element is a node.
# If it is a node, stop.
# If it is not a node, there can be only two directions of movement.
# Move in a direction and check is an element exists.
# If it exists, check if it is not already an element encountered -
# shouldn't be moving backwards.
# If a new element is encountered,
# update the element is branch iter and continue.
def jump_move(x_mat, x_jump, x_element, pos):
jump_trace=x_mat[x_element[0]][x_element[1]]
if (x_jump[jump_trace][pos][1] == "left"):
nxt_row=x_jump[jump_trace][pos][0][0]
nxt_col=x_jump[jump_trace][pos][0][1] - 1
jmp_exec="left"
elif (x_jump[jump_trace][pos][1] == "right"):
nxt_row=x_jump[jump_trace][pos][0][0]
nxt_col=x_jump[jump_trace][pos][0][1] + 1
jmp_exec="right"
elif (x_jump[jump_trace][pos][1] == "up"):
nxt_row=x_jump[jump_trace][pos][0][0] - 1
nxt_col=x_jump[jump_trace][pos][0][1]
jmp_exec="up"
elif (x_jump[jump_trace][pos][1] == "down"):
nxt_row=x_jump[jump_trace][pos][0][0] + 1
nxt_col=x_jump[jump_trace][pos][0][1]
jmp_exec="down"
return [jmp_exec, nxt_row, nxt_col]
def branch_jump(x_mat, x_jump, x_element):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and
# the sense of movement.
# Depending on the sense of movement, update
# the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement
# has taken place
# To ensure that we don't go back
# from the next element after the jump.
nxt_row=x_element[0]
nxt_col=x_element[1]
jump_exec=""
if (len(x_mat[nxt_row][nxt_col])>3):
if (x_mat[nxt_row][nxt_col].lower()[0:4] == "jump"):
jump_trace=x_mat[nxt_row][nxt_col]
if (x_jump[jump_trace][0][0] == [nxt_row, nxt_col]):
jump_exec, nxt_row, nxt_col = \
jump_move(x_mat, x_jump, x_element, 1)
elif (x_jump[jump_trace][1][0] == [nxt_row, nxt_col]):
jump_exec, nxt_row, nxt_col = \
jump_move(x_mat, x_jump, x_element, 0)
return [jump_exec, nxt_row, nxt_col]
# Advancing one element in a branch
# Checking for jump direction
# to make sure we don't go back
def branch_advance(x_mat, x_iter, nxt_elem, jmp_exec, x_rows, x_cols):
nxt_row=nxt_elem[0]
nxt_col=nxt_elem[1]
# This temporary variable is to ensure,
# two advancements don't take place in one loop.
branch_proceed=0
if ((nxt_col>0) and branch_proceed==0):
# We are trying to go left, so check if we didn't jump right.
if (x_mat[nxt_row][nxt_col-1] != '' and jmp_exec!="right"):
# Next check is if we are going backwards.
if not ([nxt_row, nxt_col-1] in x_iter):
nxt_col=nxt_col-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_row>0) and branch_proceed==0):
# We are trying to go up, so check if we didn't jump down.
if (x_mat[nxt_row-1][nxt_col] != '' and jmp_exec!="down"):
if not ([nxt_row-1, nxt_col] in x_iter):
nxt_row=nxt_row-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_col<x_cols-1) and branch_proceed==0):
# We are trying to go right, so check if we didn't jump left.
if (x_mat[nxt_row][nxt_col+1] != '' and jmp_exec!="left"):
if not ([nxt_row, nxt_col+1] in x_iter):
nxt_col=nxt_col+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
if ((nxt_row<x_rows-1) and branch_proceed==0):
# We are trying to go down, so check if we didn't jump up.
if (x_mat[nxt_row+1][nxt_col] != '' and jmp_exec!="up"):
if not ([nxt_row+1, nxt_col] in x_iter):
nxt_row=nxt_row+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jmp_exec=""
return [jmp_exec, nxt_row, nxt_col]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
# This variable is used when jumps are encountered.
jump_executed=""
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and
# the sense of movement.
# Depending on the sense of movement, update
# the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement
# has taken place
# To ensure that we don't go back
# from the next element after the jump.
next_element = [next_node_row, next_node_column]
jump_executed, next_node_row, next_node_column = \
branch_jump(conn_matrix, jump_matrix, next_element)
branch_iter.append([next_node_row, next_node_column])
next_element = [next_node_row, next_node_column]
jump_executed, next_node_row, next_node_column = \
branch_advance(conn_matrix, branch_iter, next_element, \
jump_executed, conn_rows, conn_columns)
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches. \
Check at row %d column %d" %(next_node_row, next_node_column)
break
else:
branch_iter.append([next_node_row, next_node_column])
next_elem_index=node_list.index([next_node_row, next_node_column])
branch_map[c1][next_elem_index].append(branch_iter)
nw_look=open("nw_check.csv","w")
for c1 in range(len(node_list)):
for c2 in range(len(node_list)-1):
if (branch_map[c1][c2]):
for c3 in range(len(branch_map[c1][c2])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2][c3])):
nw_look.write("[%d %d] ;" \
%(branch_map[c1][c2][c3][c4][0], branch_map[c1][c2][c3][c4][1]))
nw_look.write(")")
nw_look.write(", ")
else:
nw_look.write("[], ")
if (branch_map[c1][c2+1]):
for c3 in range(len(branch_map[c1][c2+1])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2+1][c3])):
nw_look.write("[%d %d] ;" \
%(branch_map[c1][c2+1][c3][c4][0], branch_map[c1][c2+1][c3][c4][1]))
nw_look.write(")")
nw_look.write("\n")
else:
nw_look.write("[] \n")
##for c1 in range(len(node_list)):
## for c2 in range(len(node_list)-1):
## nw_look.write("%s ;" %(branch_map[c1][c2]))
## nw_look.write("%s \n" %(branch_map[c1][c2+1]))
nw_look.close()
number_of_nodes=len(node_list)
number_of_branches=0
for c1 in range(len(node_list)):
for c2 in range(c1+1, len(node_list)):
for parallel_branches in branch_map[c1][c2]:
number_of_branches+=1
# Determining the loops
loop_list=[]
loop_count = 0
# Number of non-null elements (branches) on
# every row and column of branch_map
branch_map_rows=[]
branch_map_columns=[]
for c1 in range(len(node_list)):
branch_rows_count=0
branch_columns_count=0
for c2 in range(len(node_list)):
if branch_map[c1][c2]:
branch_rows_count+=1
if branch_map[c2][c1]:
branch_columns_count+=1
branch_map_rows.append(branch_rows_count)
branch_map_columns.append(branch_columns_count)
def find_loop(br_map, lp_list, lp_iter, br_map_rows, br_map_cols, elem, lp_count):
# If an element exists, add it to loop iterator
# Decrease the number of times that row can be visited.
row=elem[0]
col=elem[1]
lp_iter.append([row, col])
br_map_rows[row]-=1
# Move down from that element
loop_dir="down"
# Update the loop row and column counter to that element
loop_row=row
loop_column=col
print lp_iter
print row, col
print br_map_rows
print br_map_cols
print loop_dir
# The termination condition is that the loop should have "ended"
while (loop_dir != "end"):
# Check for parallel branches again.
for c3 in range(len(br_map[row][col])-1):
lp_list.append([[row, col], [row, col]])
lp_count+=1
# Not using this block but I'll keep it anyway
if (loop_dir == "right" and br_map_rows[loop_row]>0):
c3=loop_column+1
while (c3<number_of_nodes):
if br_map[loop_row][c3]:
lp_iter.append([loop_row, c3])
last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1]
frst_elem_curr=br_map[loop_row][c3][0][0]
last_elem_curr=br_map[loop_row][c3][0][-1]
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
loop_dir="end"
br_map_rows[loop_row]-=1
else:
loop_column=c3
loop_dir="down"
br_map_rows[loop_row]-=1
break
else:
c3=c3+1
else:
loop_dir="end"
lp_iter=[]
br_map_rows[loop_row]-=1
print lp_iter
print loop_dir
print br_map_rows
print br_map_cols
# Will be executed if we are moving down
# and there are elements in that column
if (loop_dir == "down" and br_map_cols[loop_column]>0):
# Start from the next row in that column
c3=loop_row+1
# check if it is within the dimensions
while (c3<number_of_nodes):
# Check if an element exists there
if br_map[c3][loop_column]:
# If so, add that element.
lp_iter.append([c3, loop_column])
last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1]
frst_elem_curr=br_map[c3][loop_column][0][0]
last_elem_curr=br_map[c3][loop_column][0][-1]
# Check if that is the last element
# Check if one of the extreme nodes in that branch
# is the same as the starting nodes in the loop iterator.
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
# If so, loop has ended
loop_dir="end"
# Decrement the column counter
# There is one element less in that column
br_map_cols[loop_column]-=1
else:
# If not, we move to the left
# Update the loop row counter
loop_row=c3
loop_dir="left"
# Decrement the column counter
br_map_cols[loop_column]-=1
break
else:
# If no element is as the spot,
# check the next row in the that column
c3=c3+1
else:
# If the end of the matrix has
# reached without finding an element
# this means that a loop can't be formed.
# End the loop and make the iterator null
loop_dir="end"
lp_iter=[]
# The column counter still decrements
# so that we don't come here again.
br_map_cols[loop_column]-=1
print lp_iter
print loop_dir
print br_map_rows
print br_map_cols
# Will be executed if we are moving left
# and there are elements in that row
if (loop_dir == "left" and br_map_rows[loop_row]>0):
# Start from the previous column in that row
c3=loop_column-1
# check if it is within the dimensions
while (c3>=0):
# Check if an element exists there
if br_map[loop_row][c3]:
# If so, add that element.
lp_iter.append([loop_row, c3])
last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1]
frst_elem_curr=br_map[loop_row][c3][0][0]
last_elem_curr=br_map[loop_row][c3][0][-1]
# Check if that is the last element
# Check if one of the extreme nodes in that branch
# is the same as the starting nodes in the loop iterator.
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
# If so, loop has ended
loop_dir="end"
# Decrement the row counter
# There is one element less in that row
br_map_rows[loop_row]-=1
else:
# If not, we move up
# Update the loop column counter
loop_column=c3
loop_dir="up"
# Decrement the column counter
br_map_rows[loop_row]-=1
break
else:
# If no element is as the spot,
# check the previous column in the that row
c3=c3-1
else:
# If the end of the matrix has
# reached without finding an element
# this means that a loop can't be formed.
# End the loop and make the iterator null
loop_dir="end"
lp_iter=[]
# The column counter still decrements
# so that we don't come here again.
br_map_rows[loop_row]-=1
print lp_iter
print loop_dir
print br_map_rows
print br_map_cols
# Will be executed if we are moving up
# and there are elements in that column
if (loop_dir == "up" and br_map_cols[loop_column]>0):
# Start from the previous row in that column
c3=loop_row-1
# check if it is within the dimensions
while (c3>=0):
# Check if an element exists there
if br_map[c3][loop_column]:
# If so, add that element.
lp_iter.append([c3, loop_column])
last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1]
frst_elem_curr=br_map[c3][loop_column][0][0]
last_elem_curr=br_map[c3][loop_column][0][-1]
# Check if that is the last element
# Check if one of the extreme nodes in that branch
# is the same as the starting nodes in the loop iterator.
if (frst_elem_curr==last_elem_frst or \
last_elem_curr==last_elem_frst):
# If so, loop has ended
loop_dir="end"
# Decrement the column counter
# There is one element less in that column
br_map_cols[loop_column]-=1
else:
# If not, we move to the left
# Update the loop row counter
loop_row=c3
loop_dir="left"
# Decrement the column counter
br_map_cols[loop_column]-=1
break
else:
# If no element is as the spot,
# check the previous row in the that column
c3=c3-1
else:
# If the end of the matrix has
# reached without finding an element
# this means that a loop can't be formed.
# End the loop and make the iterator null
loop_dir="end"
lp_iter=[]
# The column counter still decrements
# so that we don't come here again.
br_map_cols[loop_column]-=1
print lp_iter
print loop_dir
print br_map_rows
print br_map_cols
# End of while loop
# "end" encountered
if lp_iter:
lp_count+=1
lp_list.append(lp_iter)
lp_iter=[]
return lp_count
# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
c2=c1+1
#check if it exists
while not branch_map[c1][c2]:
# If not move to next column
c2=c2+1
# Check if the column is within dimensions
if (c2>=number_of_nodes):
# If not, break out and move to next row
break
else:
# Starting branch found
# Check is there are parallel branches between the nodes
for c3 in range(len(branch_map[c1][c2])-1):
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=1
# Reduce the number of elements in the rows from
# zero up to the current row
# checking for elements to the left of
# the starting element
# The idea is that you can't go right in the loop.
for row_count in range(c1, number_of_nodes):
for col_count in range(c2):
if branch_map[row_count][col_count]:
if (branch_map_rows[row_count]>1):
branch_map_rows[row_count]-=1
print "*"*70
print c1, c2
print branch_map_rows
print branch_map_columns
# Move right along the row of branch_map until the end.
for c4 in range(c2+1, number_of_nodes):
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([c1, c2])
# check if there is an element in that row
if branch_map[c1][c4]:
loop_count=find_loop(branch_map, loop_list, loop_iter, \
branch_map_rows, branch_map_columns, [c1, c4], loop_count)
print loop_count
print loop_list
view raw loop.py hosted with ❤ by GitHub

Thursday, January 10, 2013

Loop identification - II

This part actually turned out a whole lot trickier than I thought it would. I figured the best way to go about is by a two step process: first identify the route every loop must take and then actually build the loop.

So, this is the first part - identifying the loop.

To begin with, here is the entire code (including node and branch identification):

#! /usr/bin/env python
import sys, math, matrix
new_file = open("testckt2.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire" where a zero impedance direct connection exists.
# Where no connection nor device (resitor, inductor etc) exists, a '' will be found.
# The devices will be strings. Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# Remove any leading or trailing quotes and also carriage returns (\n) that may have been added while generating the csv file.
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
if conn_matrix[c1][c2]:
if "\n" in conn_matrix[c1][c2]:
conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
if conn_matrix[c1][c2]:
while (conn_matrix[c1][c2][0]=='"' or conn_matrix[c1][c2][0]=="'"):
conn_matrix[c1][c2]=conn_matrix[c1][c2][1:]
while (conn_matrix[c1][c2][-1]=='"' or conn_matrix[c1][c2][-1]=="'"):
conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
jump_list=[]
# Check for jump label sanity and add a list of elements where jumps exist.
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2]==''):
del curr_element["exist"]
del curr_element["jump"]
elif (len(conn_matrix[c1][c2])>3):
if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
del curr_element["exist"]
else:
del curr_element["jump"]
else:
del curr_element["jump"]
if ("jump" in curr_element):
if (c1<conn_rows-1):
next_row_element = {"exist":0, "jump":1}
if (conn_matrix[c1+1][c2]==''):
del next_row_element["exist"]
del next_row_element["jump"]
elif (len(conn_matrix[c1+1][c2])>3):
if (conn_matrix[c1+1][c2].lower()[0:4] == "jump"):
del next_row_element["exist"]
else:
del next_row_element["jump"]
else:
del next_row_element["jump"]
else:
next_row_element = {}
if (c1>0):
prev_row_element = {"exist":0, "jump":1}
if (conn_matrix[c1-1][c2]==''):
del prev_row_element["exist"]
del prev_row_element["jump"]
elif (len(conn_matrix[c1-1][c2])>3):
if (conn_matrix[c1-1][c2].lower()[0:4] == "jump"):
del prev_row_element["exist"]
else:
del prev_row_element["jump"]
else:
del prev_row_element["jump"]
else:
prev_row_element = {}
if (c2<conn_columns-1):
next_col_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2+1]==''):
del next_col_element["exist"]
del next_col_element["jump"]
elif (len(conn_matrix[c1][c2+1])>3):
if (conn_matrix[c1][c2+1].lower()[0:4] == "jump"):
del next_col_element["exist"]
else:
del next_col_element["jump"]
else:
del next_col_element["jump"]
else:
next_col_element = {}
if (c2>0):
prev_col_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2-1]==''):
del prev_col_element["exist"]
del prev_col_element["jump"]
elif (len(conn_matrix[c1][c2-1])>3):
if (conn_matrix[c1][c2-1].lower()[0:4] == "jump"):
del prev_col_element["exist"]
else:
del prev_col_element["jump"]
else:
del prev_col_element["jump"]
else:
prev_col_element = {}
if ("jump" in next_row_element or "jump" in next_col_element or "jump" in prev_row_element or "jump" in prev_col_element):
print "Two jumps can't be adjacent to each other."
print "Check jump at row %d, column %d" %(c1, c2)
if ("exist" in next_row_element):
if ("exist" in next_col_element or "exist" in prev_row_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "down"])
elif ("exist" in next_col_element):
if ("exist" in next_row_element or "exist" in prev_row_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "right"])
elif ("exist" in prev_row_element):
if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "up"])
elif ("exist" in prev_col_element):
if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_row_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "left"])
# Create a dictionary of jumps - for each jump label - there is a list with two elements.
jump_matrix={}
for c1 in range(len(jump_list)):
jump_count=1
for c2 in range(len(jump_list)):
if not c1==c2:
if jump_list[c1][2]==jump_list[c2][2]:
jump_matrix[jump_list[c1][2]]=[[[jump_list[c1][0], jump_list[c1][1]], jump_list[c1][3]], [[jump_list[c2][0], jump_list[c2][1]], jump_list[c2][3]]]
jump_count=jump_count+1
if (jump_count<2):
print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
elif (jump_count>2):
print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
del jump_matrix[jump_list[c1][2]]
# A node is defined as a junction of 3 or more branches.
node_list=[]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2]==''):
del curr_element["exist"]
del curr_element["jump"]
elif (len(conn_matrix[c1][c2])>3):
if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
del curr_element["exist"]
else:
del curr_element["jump"]
if ("exist" in curr_element):
if ((c1==0 and c2==0) or (c1==conn_rows-1 and c2==conn_columns-1) or (c1==0 and c2==conn_columns-1) or (c1==conn_rows-1 and c2==0)):
# If its a corner point it can't be a node. This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (c1==0):
# If it is the first row,
# check if the element in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
# Then check if the element in next row and same column is connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]==''):
node_list.append([c1, c2])
if (c1==conn_rows-1):
# If it is the last row,
# check if the elements in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
if not (conn_matrix[c1-1][c2]==''):
# Then check if element in the previous row and same column is connected. Look for a T junction.
node_list.append([c1, c2])
if (c2==0):
# If it is the first column,
# check if the element in the next column and same row is connected.
if not (conn_matrix[c1][c2+1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c2==conn_columns-1):
# If it is the last column,
# check if the element in the previous column and same row is connected.
if not (conn_matrix[c1][c2-1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c1>0 and c1<conn_rows-1 and c2>0 and c2<conn_columns-1):
# If the element is not on the outer boundary
if (conn_matrix[c1][c2+1]!='' and conn_matrix[c1][c2-1]!=''):
# Check if the elements in next and previous columns and same row are connected
if (conn_matrix[c1+1][c2]!='' or conn_matrix[c1-1][c2]!=''):
# Then check if elements in either the next and previous row and same column are connected
node_list.append([c1, c2])
elif (conn_matrix[c1+1][c2]!='' and conn_matrix[c1-1][c2]!=''):
if (conn_matrix[c1][c2+1]!='' or conn_matrix[c1][c2-1]!=''):
node_list.append([c1, c2])
else:
pass
# This list contains all the nodes that are T or + junctions.
#print "*"*60
#print node_list
#print "*"*60
# Map of branches between nodes in node_list
branch_map=[]
# Creating an square of the dimension of node_list.
# Each element will be a list of the series connection of branches between the nodes.
for c1 in range(len(node_list)):
branch_rows=[]
for c2 in range(len(node_list)):
branch_rows.append([])
branch_map.append(branch_rows)
# Generate a search rule for each node.
# The concept is to start at a node and search until another node is reached.
node_iter_rule=[]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
iter_rule={"left":0, "down":1, "right":2, "up":3}
# For nodes in the outer edges, the rules going outwards will be removed.
if (node_row==0):
del(iter_rule["up"])
if (node_row==conn_rows-1):
del(iter_rule["down"])
if (node_column==0):
del(iter_rule["left"])
if (node_column==conn_columns-1):
del(iter_rule["right"])
# Depending on the non-existence of elements in a direction, those rules will be removed.
if (node_row>0) and (node_row<conn_rows-1) and (node_column>0) and (node_column<conn_columns-1):
if (conn_matrix[node_row-1][node_column]==''):
del(iter_rule["up"])
if (conn_matrix[node_row+1][node_column]==''):
del(iter_rule["down"])
if (conn_matrix[node_row][node_column+1]==''):
del(iter_rule["right"])
if (conn_matrix[node_row][node_column-1]==''):
del(iter_rule["left"])
node_iter_rule.append(iter_rule)
# Check if a jump is not next to a node.
for c1 in range(len(node_list)):
for jump_check_dir in node_iter_rule[c1].keys():
if (jump_check_dir=="up"):
if (len(conn_matrix[node_list[c1][0]-1][node_list[c1][1]])>3):
if (conn_matrix[node_list[c1][0]-1][node_list[c1][1]].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0]-1, node_list[c1][1])
if (jump_check_dir=="down"):
if (len(conn_matrix[node_list[c1][0]+1][node_list[c1][1]])>3):
if (conn_matrix[node_list[c1][0]+1][node_list[c1][1]].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0]+1, node_list[c1][1])
if (jump_check_dir=="left"):
if (len(conn_matrix[node_list[c1][0]][node_list[c1][1]-1])>3):
if (conn_matrix[node_list[c1][0]][node_list[c1][1]-1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0], node_list[c1][1]-1)
if (jump_check_dir=="right"):
if (len(conn_matrix[node_list[c1][0]][node_list[c1][1]+1])>3):
if (conn_matrix[node_list[c1][0]][node_list[c1][1]+1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0], node_list[c1][1]+1)
# For each node in node_list perform the search operation.
# Each node has a list of possible search rules.
# Perform a search for each rule.
# From the starting node, advance in the direction of the rule.
# After advancing, check if the next element is a node.
# If it is a node, stop.
# If it is not a node, there can be only two directions of movement.
# Move in a direction and check is an element exists.
# If it exists, check if it is not already an element encountered - shouldn't be moving backwards.
# If a new element is encountered, update the element is branch iter and continue.
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
# This variable is used when jumps are encountered.
jump_executed=""
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and the sense of movement.
# Depending on the sense of movement, update the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement has taken place
# To ensure that we don't go back from the next element after the jump.
if (len(conn_matrix[next_node_row][next_node_column])>3):
if (conn_matrix[next_node_row][next_node_column].lower()[0:4] == "jump"):
jump_trace=conn_matrix[next_node_row][next_node_column]
if (jump_matrix[jump_trace][0][0] == [next_node_row, next_node_column]):
if (jump_matrix[jump_trace][1][1] == "left"):
next_node_row=jump_matrix[jump_trace][1][0][0]
next_node_column=jump_matrix[jump_trace][1][0][1] - 1
jump_executed="left"
elif (jump_matrix[jump_trace][1][1] == "right"):
next_node_row=jump_matrix[jump_trace][1][0][0]
next_node_column=jump_matrix[jump_trace][1][0][1] + 1
jump_executed="right"
elif (jump_matrix[jump_trace][1][1] == "up"):
next_node_row=jump_matrix[jump_trace][1][0][0] - 1
next_node_column=jump_matrix[jump_trace][1][0][1]
jump_executed="up"
elif (jump_matrix[jump_trace][1][1] == "down"):
next_node_row=jump_matrix[jump_trace][1][0][0] + 1
next_node_column=jump_matrix[jump_trace][1][0][1]
jump_executed="down"
elif (jump_matrix[jump_trace][1][0] == [next_node_row, next_node_column]):
if (jump_matrix[jump_trace][0][1] == "left"):
next_node_row=jump_matrix[jump_trace][0][0][0]
next_node_column=jump_matrix[jump_trace][0][0][1] - 1
jump_executed="left"
elif (jump_matrix[jump_trace][0][1] == "right"):
next_node_row=jump_matrix[jump_trace][0][0][0]
next_node_column=jump_matrix[jump_trace][0][0][1] + 1
jump_executed="right"
elif (jump_matrix[jump_trace][0][1] == "up"):
next_node_row=jump_matrix[jump_trace][0][0][0] - 1
next_node_column=jump_matrix[jump_trace][0][0][1]
jump_executed="up"
elif (jump_matrix[jump_trace][0][1] == "down"):
next_node_row=jump_matrix[jump_trace][0][0][0] + 1
next_node_column=jump_matrix[jump_trace][0][0][1]
jump_executed="down"
branch_iter.append([next_node_row, next_node_column])
# This temporary variable is to ensure, two advancements don't take place in one loop.
branch_proceed=0
if ((next_node_column>0) and branch_proceed==0):
# We are trying to go left, so check if we didn't jump right.
if (conn_matrix[next_node_row][next_node_column-1] != '' and jump_executed!="right"):
# Next check is if we are going backwards.
if not ([next_node_row, next_node_column-1] in branch_iter):
next_node_column=next_node_column-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_row>0) and branch_proceed==0):
# We are trying to go up, so check if we didn't jump down.
if (conn_matrix[next_node_row-1][next_node_column] != '' and jump_executed!="down"):
if not ([next_node_row-1, next_node_column] in branch_iter):
next_node_row=next_node_row-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_column<conn_columns-1) and branch_proceed==0):
# We are trying to go right, so check if we didn't jump left.
if (conn_matrix[next_node_row][next_node_column+1] != '' and jump_executed!="left"):
if not ([next_node_row, next_node_column+1] in branch_iter):
next_node_column=next_node_column+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_row<conn_rows-1) and branch_proceed==0):
# We are trying to go down, so check if we didn't jump up.
if (conn_matrix[next_node_row+1][next_node_column] != '' and jump_executed!="up"):
if not ([next_node_row+1, next_node_column] in branch_iter):
next_node_row=next_node_row+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches. Check at row %d column %d" %(next_node_row, next_node_column)
break
else:
branch_iter.append([next_node_row, next_node_column])
branch_map[c1][node_list.index([next_node_row, next_node_column])].append(branch_iter)
nw_look=open("nw_check.csv","w")
for c1 in range(len(node_list)):
for c2 in range(len(node_list)-1):
if (branch_map[c1][c2]):
for c3 in range(len(branch_map[c1][c2])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2][c3])):
nw_look.write("[%d %d] ;" %(branch_map[c1][c2][c3][c4][0], branch_map[c1][c2][c3][c4][1]))
nw_look.write(")")
nw_look.write(", ")
else:
nw_look.write("[], ")
if (branch_map[c1][c2+1]):
for c3 in range(len(branch_map[c1][c2+1])):
nw_look.write("(")
for c4 in range(len(branch_map[c1][c2+1][c3])):
nw_look.write("[%d %d] ;" %(branch_map[c1][c2+1][c3][c4][0], branch_map[c1][c2+1][c3][c4][1]))
nw_look.write(")")
nw_look.write("\n")
else:
nw_look.write("[] \n")
##for c1 in range(len(node_list)):
## for c2 in range(len(node_list)-1):
## nw_look.write("%s ;" %(branch_map[c1][c2]))
## nw_look.write("%s \n" %(branch_map[c1][c2+1]))
nw_look.close()
number_of_nodes=len(node_list)
number_of_branches=0
for c1 in range(len(node_list)):
for c2 in range(c1+1, len(node_list)):
for parallel_branches in branch_map[c1][c2]:
number_of_branches+=1
# Determining the loops
loop_list=[]
loop_count = 0
# Number of non-null elements (branches) on every row and column of branch_map
branch_map_rows=[]
branch_map_columns=[]
for c1 in range(len(node_list)):
branch_rows_count=0
branch_columns_count=0
for c2 in range(len(node_list)):
if branch_map[c1][c2]:
branch_rows_count+=1
if branch_map[c2][c1]:
branch_columns_count+=1
branch_map_rows.append(branch_rows_count)
branch_map_columns.append(branch_columns_count)
# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
c2=c1+1
#check if it exists
while not branch_map[c1][c2]:
# If not move to next column
c2=c2+1
# Check if the column is within dimensions
if (c2>=number_of_nodes):
# If not, break out and move to next row
break
else:
# Starting branch found
# Check is there are parallel branches between the nodes
for c3 in range(len(branch_map[c1][c2])-1):
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=1
# Reduce the number of elements in the rows from zero up to the current row
# checking for elements to the left of the starting element
# The idea is that you can't go right in the loop.
for row_count in range(c1, number_of_nodes):
for col_count in range(c2):
if branch_map[row_count][col_count]:
if (branch_map_rows[row_count]>1):
branch_map_rows[row_count]-=1
# Set the loop row and column count
loop_row=c1
loop_column=c2
print "*"*70
print c1, c2
print branch_map_rows
print branch_map_columns
# Move right along the row of branch_map until the end.
for c4 in range(c2+1, number_of_nodes):
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([c1, c2])
# check if there is an element in that row
if branch_map[c1][c4]:
# If an element exists, add it to loop iterator
# Decrease the number of times that row can be visited.
loop_iter.append([c1, c4])
branch_map_rows[loop_row]-=1
# Move down from that element
loop_dir="down"
# Update the loop row and column counter to that element
loop_row=c1
loop_column=c4
print loop_iter
print c1, c4
print branch_map_rows
print branch_map_columns
print loop_dir
# The termination condition is that the loop should have "ended"
while (loop_dir != "end"):
# Check for parallel branches again.
for c3 in range(len(branch_map[c1][c4])-1):
loop_list.append([[c1, c4], [c1, c4]])
loop_count+=1
# Not using this block but I'll keep it anyway
if (loop_dir == "right" and branch_map_rows[loop_row]>0):
c3=loop_column+1
while (c3<number_of_nodes):
if branch_map[loop_row][c3]:
loop_iter.append([loop_row, c3])
if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
loop_dir="end"
branch_map_rows[loop_row]-=1
else:
loop_column=c3
loop_dir="down"
branch_map_rows[loop_row]-=1
break
else:
c3=c3+1
else:
loop_dir="end"
loop_iter=[]
branch_map_rows[loop_row]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
# Will be executed if we are moving down
# and there are elements in that column
if (loop_dir == "down" and branch_map_columns[loop_column]>0):
# Start from the next row in that column
c3=loop_row+1
# check if it is within the dimensions
while (c3<number_of_nodes):
# Check if an element exists there
if branch_map[c3][loop_column]:
# If so, add that element.
loop_iter.append([c3, loop_column])
# Check if that is the last element
# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
# If so, loop has ended
loop_dir="end"
# Decrement the column counter
# There is one element less in that column
branch_map_columns[loop_column]-=1
else:
# If not, we move to the left
# Update the loop row counter
loop_row=c3
loop_dir="left"
# Decrement the column counter
branch_map_columns[loop_column]-=1
break
else:
# If no element is as the spot, check the next row in the that column
c3=c3+1
else:
# If the end of the matrix has reached without finding an element
# this means that a loop can't be formed
# End the loop and make the iterator null
loop_dir="end"
loop_iter=[]
# The column counter still decrements so that we don't come here again.
branch_map_columns[loop_column]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
# Will be executed if we are moving left
# and there are elements in that row
if (loop_dir == "left" and branch_map_rows[loop_row]>0):
# Start from the previous column in that row
c3=loop_column-1
# check if it is within the dimensions
while (c3>=0):
# Check if an element exists there
if branch_map[loop_row][c3]:
# If so, add that element.
loop_iter.append([loop_row, c3])
# Check if that is the last element
# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
# If so, loop has ended
loop_dir="end"
# Decrement the row counter
# There is one element less in that row
branch_map_rows[loop_row]-=1
else:
# If not, we move up
# Update the loop column counter
loop_column=c3
loop_dir="up"
# Decrement the column counter
branch_map_rows[loop_row]-=1
break
else:
# If no element is as the spot, check the previous column in the that row
c3=c3-1
else:
# If the end of the matrix has reached without finding an element
# this means that a loop can't be formed
# End the loop and make the iterator null
loop_dir="end"
loop_iter=[]
# The column counter still decrements so that we don't come here again.
branch_map_rows[loop_row]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
# Will be executed if we are moving up
# and there are elements in that column
if (loop_dir == "up" and branch_map_columns[loop_column]>0):
# Start from the previous row in that column
c3=loop_row-1
# check if it is within the dimensions
while (c3>=0):
# Check if an element exists there
if branch_map[c3][loop_column]:
# If so, add that element.
loop_iter.append([c3, loop_column])
# Check if that is the last element
# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
# If so, loop has ended
loop_dir="end"
# Decrement the column counter
# There is one element less in that column
branch_map_columns[loop_column]-=1
else:
# If not, we move to the left
# Update the loop row counter
loop_row=c3
loop_dir="left"
# Decrement the column counter
branch_map_columns[loop_column]-=1
break
else:
# If no element is as the spot, check the previous row in the that column
c3=c3-1
else:
# If the end of the matrix has reached without finding an element
# this means that a loop can't be formed
# End the loop and make the iterator null
loop_dir="end"
loop_iter=[]
# The column counter still decrements so that we don't come here again.
branch_map_columns[loop_column]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
if loop_iter:
loop_count+=1
loop_list.append(loop_iter)
loop_iter=[]
print loop_count
print loop_list
view raw node_br_loop.py hosted with ❤ by GitHub
The loop identification part is:

# Determining the loops
loop_list=[]
loop_count = 0
# Number of non-null elements (branches) on every row and column of branch_map
branch_map_rows=[]
branch_map_columns=[]
for c1 in range(len(node_list)):
branch_rows_count=0
branch_columns_count=0
for c2 in range(len(node_list)):
if branch_map[c1][c2]:
branch_rows_count+=1
if branch_map[c2][c1]:
branch_columns_count+=1
branch_map_rows.append(branch_rows_count)
branch_map_columns.append(branch_columns_count)
# Pick a row
for c1 in range(number_of_nodes-1):
# Diagonal elements are null
# So choose the column next to diagonal
c2=c1+1
#check if it exists
while not branch_map[c1][c2]:
# If not move to next column
c2=c2+1
# Check if the column is within dimensions
if (c2>=number_of_nodes):
# If not, break out and move to next row
break
else:
# Starting branch found
# Check is there are parallel branches between the nodes
for c3 in range(len(branch_map[c1][c2])-1):
loop_list.append([[c1, c2], [c1, c2]])
loop_count+=1
# Reduce the number of elements in the rows from zero up to the current row
# checking for elements to the left of the starting element
# The idea is that you can't go right in the loop.
for row_count in range(c1, number_of_nodes):
for col_count in range(c2):
if branch_map[row_count][col_count]:
if (branch_map_rows[row_count]>1):
branch_map_rows[row_count]-=1
# Set the loop row and column count
loop_row=c1
loop_column=c2
print "*"*70
print c1, c2
print branch_map_rows
print branch_map_columns
# Move right along the row of branch_map until the end.
for c4 in range(c2+1, number_of_nodes):
# Initialize the loop iterator list with the first element.
loop_iter=[]
loop_iter.append([c1, c2])
# check if there is an element in that row
if branch_map[c1][c4]:
# If an element exists, add it to loop iterator
# Decrease the number of times that row can be visited.
loop_iter.append([c1, c4])
branch_map_rows[loop_row]-=1
# Move down from that element
loop_dir="down"
# Update the loop row and column counter to that element
loop_row=c1
loop_column=c4
print loop_iter
print c1, c4
print branch_map_rows
print branch_map_columns
print loop_dir
# The termination condition is that the loop should have "ended"
while (loop_dir != "end"):
# Check for parallel branches again.
for c3 in range(len(branch_map[c1][c4])-1):
loop_list.append([[c1, c4], [c1, c4]])
loop_count+=1
# Not using this block but I'll keep it anyway
if (loop_dir == "right" and branch_map_rows[loop_row]>0):
c3=loop_column+1
while (c3<number_of_nodes):
if branch_map[loop_row][c3]:
loop_iter.append([loop_row, c3])
if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
loop_dir="end"
branch_map_rows[loop_row]-=1
else:
loop_column=c3
loop_dir="down"
branch_map_rows[loop_row]-=1
break
else:
c3=c3+1
else:
loop_dir="end"
loop_iter=[]
branch_map_rows[loop_row]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
# Will be executed if we are moving down
# and there are elements in that column
if (loop_dir == "down" and branch_map_columns[loop_column]>0):
# Start from the next row in that column
c3=loop_row+1
# check if it is within the dimensions
while (c3<number_of_nodes):
# Check if an element exists there
if branch_map[c3][loop_column]:
# If so, add that element.
loop_iter.append([c3, loop_column])
# Check if that is the last element
# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
# If so, loop has ended
loop_dir="end"
# Decrement the column counter
# There is one element less in that column
branch_map_columns[loop_column]-=1
else:
# If not, we move to the left
# Update the loop row counter
loop_row=c3
loop_dir="left"
# Decrement the column counter
branch_map_columns[loop_column]-=1
break
else:
# If no element is as the spot, check the next row in the that column
c3=c3+1
else:
# If the end of the matrix has reached without finding an element
# this means that a loop can't be formed
# End the loop and make the iterator null
loop_dir="end"
loop_iter=[]
# The column counter still decrements so that we don't come here again.
branch_map_columns[loop_column]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
# Will be executed if we are moving left
# and there are elements in that row
if (loop_dir == "left" and branch_map_rows[loop_row]>0):
# Start from the previous column in that row
c3=loop_column-1
# check if it is within the dimensions
while (c3>=0):
# Check if an element exists there
if branch_map[loop_row][c3]:
# If so, add that element.
loop_iter.append([loop_row, c3])
# Check if that is the last element
# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
# If so, loop has ended
loop_dir="end"
# Decrement the row counter
# There is one element less in that row
branch_map_rows[loop_row]-=1
else:
# If not, we move up
# Update the loop column counter
loop_column=c3
loop_dir="up"
# Decrement the column counter
branch_map_rows[loop_row]-=1
break
else:
# If no element is as the spot, check the previous column in the that row
c3=c3-1
else:
# If the end of the matrix has reached without finding an element
# this means that a loop can't be formed
# End the loop and make the iterator null
loop_dir="end"
loop_iter=[]
# The column counter still decrements so that we don't come here again.
branch_map_rows[loop_row]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
# Will be executed if we are moving up
# and there are elements in that column
if (loop_dir == "up" and branch_map_columns[loop_column]>0):
# Start from the previous row in that column
c3=loop_row-1
# check if it is within the dimensions
while (c3>=0):
# Check if an element exists there
if branch_map[c3][loop_column]:
# If so, add that element.
loop_iter.append([c3, loop_column])
# Check if that is the last element
# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
# If so, loop has ended
loop_dir="end"
# Decrement the column counter
# There is one element less in that column
branch_map_columns[loop_column]-=1
else:
# If not, we move to the left
# Update the loop row counter
loop_row=c3
loop_dir="left"
# Decrement the column counter
branch_map_columns[loop_column]-=1
break
else:
# If no element is as the spot, check the previous row in the that column
c3=c3-1
else:
# If the end of the matrix has reached without finding an element
# this means that a loop can't be formed
# End the loop and make the iterator null
loop_dir="end"
loop_iter=[]
# The column counter still decrements so that we don't come here again.
branch_map_columns[loop_column]-=1
print loop_iter
print loop_dir
print branch_map_rows
print branch_map_columns
if loop_iter:
loop_count+=1
loop_list.append(loop_iter)
loop_iter=[]
print loop_count
print loop_list
view raw loop.py hosted with ❤ by GitHub
This works for a couple of circuits. But I'll have to test it for all kinds of circuits (or layouts rather) before moving to the next step.

Some things that I assumed:

1. The branch_map matrix is symmetrical (at least in branch information if not exactly). So this means branches will be picked up sooner or later if a reasonably detailed search method is used.

2. To elaborate on what a "reseaonably detailed" search method is.

3. I start from an element in the row which is the first after the null diagonal element. So this is the first branch. I touch EVERY element in this first row. This means, I take a turn (turning down) at all the other nodes (columns) that this node (row) is connected.

4. I then move left from the first element in the column where I turned. The other nodes in that column are not touched. Will this affect later? Will have to think about it.

5. Similarly, the other searches will also turn a the first node they find.


This is the output from the latest circuit that I pasted. It works for a few simple other ones, but will have to test specifically if the code will break at those assumptions.

**********************************************************************
0 1
[3, 2, 2, 3, 3, 3, 3, 3, 2, 3]
[3, 3, 3, 3, 3, 4, 3, 3, 2, 3]
[[0, 1], [0, 2]]
0 2
[2, 2, 2, 3, 3, 3, 3, 3, 2, 3]
[3, 3, 3, 3, 3, 4, 3, 3, 2, 3]
down
[[0, 1], [0, 2], [1, 2]]
end
[2, 2, 2, 3, 3, 3, 3, 3, 2, 3]
[3, 3, 2, 3, 3, 4, 3, 3, 2, 3]
[[0, 1], [0, 5]]
0 5
[1, 2, 2, 3, 3, 3, 3, 3, 2, 3]
[3, 3, 2, 3, 3, 4, 3, 3, 2, 3]
down
[[0, 1], [0, 5], [4, 5]]
left
[1, 2, 2, 3, 3, 3, 3, 3, 2, 3]
[3, 3, 2, 3, 3, 3, 3, 3, 2, 3]
[[0, 1], [0, 5], [4, 5], [4, 3]]
up
[1, 2, 2, 3, 2, 3, 3, 3, 2, 3]
[3, 3, 2, 3, 3, 3, 3, 3, 2, 3]
[[0, 1], [0, 5], [4, 5], [4, 3], [2, 3]]
left
[1, 2, 2, 3, 2, 3, 3, 3, 2, 3]
[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
[[0, 1], [0, 5], [4, 5], [4, 3], [2, 3], [2, 1]]
end
[1, 2, 1, 3, 2, 3, 3, 3, 2, 3]
[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
**********************************************************************
1 2
[1, 1, 1, 3, 2, 2, 3, 2, 2, 3]
[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
[[1, 2], [1, 7]]
1 7
[1, 0, 1, 3, 2, 2, 3, 2, 2, 3]
[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
down
[[1, 2], [1, 7], [6, 7]]
left
[1, 0, 1, 3, 2, 2, 3, 2, 2, 3]
[3, 3, 2, 2, 3, 3, 3, 2, 2, 3]
[[1, 2], [1, 7], [6, 7], [6, 5]]
up
[1, 0, 1, 3, 2, 2, 2, 2, 2, 3]
[3, 3, 2, 2, 3, 3, 3, 2, 2, 3]
[[1, 2], [1, 7], [6, 7], [6, 5], [4, 5]]
left
[1, 0, 1, 3, 2, 2, 2, 2, 2, 3]
[3, 3, 2, 2, 3, 2, 3, 2, 2, 3]
[[1, 2], [1, 7], [6, 7], [6, 5], [4, 5], [4, 3]]
up
[1, 0, 1, 3, 1, 2, 2, 2, 2, 3]
[3, 3, 2, 2, 3, 2, 3, 2, 2, 3]
[[1, 2], [1, 7], [6, 7], [6, 5], [4, 5], [4, 3], [2, 3]]
end
[1, 0, 1, 3, 1, 2, 2, 2, 2, 3]
[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
**********************************************************************
2 3
[1, 0, 1, 2, 1, 1, 2, 1, 2, 3]
[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
**********************************************************************
3 4
[1, 0, 1, 1, 1, 1, 2, 1, 2, 2]
[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
[[3, 4], [3, 9]]
3 9
[1, 0, 1, 0, 1, 1, 2, 1, 2, 2]
[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
down
[[3, 4], [3, 9], [5, 9]]
left
[1, 0, 1, 0, 1, 1, 2, 1, 2, 2]
[3, 3, 2, 1, 3, 2, 3, 2, 2, 2]
[[3, 4], [3, 9], [5, 9], [5, 6]]
up
[1, 0, 1, 0, 1, 0, 2, 1, 2, 2]
[3, 3, 2, 1, 3, 2, 3, 2, 2, 2]
[[3, 4], [3, 9], [5, 9], [5, 6], [4, 6]]
end
[1, 0, 1, 0, 1, 0, 2, 1, 2, 2]
[3, 3, 2, 1, 3, 2, 2, 2, 2, 2]
**********************************************************************
4 5
[1, 0, 1, 0, 1, 0, 1, 1, 2, 1]
[3, 3, 2, 1, 3, 2, 2, 2, 2, 2]
[[4, 5], [4, 6]]
4 6
[1, 0, 1, 0, 0, 0, 1, 1, 2, 1]
[3, 3, 2, 1, 3, 2, 2, 2, 2, 2]
down
[[4, 5], [4, 6], [5, 6]]
end
[1, 0, 1, 0, 0, 0, 1, 1, 2, 1]
[3, 3, 2, 1, 3, 2, 1, 2, 2, 2]
**********************************************************************
5 6
[1, 0, 1, 0, 0, 0, 1, 1, 2, 1]
[3, 3, 2, 1, 3, 2, 1, 2, 2, 2]
[[5, 6], [5, 9]]
5 9
[1, 0, 1, 0, 0, -1, 1, 1, 2, 1]
[3, 3, 2, 1, 3, 2, 1, 2, 2, 2]
down
[[5, 6], [5, 9], [8, 9]]
left
[1, 0, 1, 0, 0, -1, 1, 1, 2, 1]
[3, 3, 2, 1, 3, 2, 1, 2, 2, 1]
[[5, 6], [5, 9], [8, 9], [8, 7]]
up
[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
[3, 3, 2, 1, 3, 2, 1, 2, 2, 1]
[[5, 6], [5, 9], [8, 9], [8, 7], [6, 7]]
end
[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
**********************************************************************
6 7
[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
**********************************************************************
7 8
[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
**********************************************************************
8 9
[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
7
[[[0, 1], [0, 2], [1, 2]], [[0, 1], [0, 5], [4, 5], [4, 3], [2, 3], [2, 1]], [[1, 2], [1, 7], [6, 7], [6, 5], [4, 5], [4, 3], [2, 3]], [[3, 4], [3, 9], [5, 9], [5, 6], [4, 6]], [[4, 5], [4, 6], [5, 6]], [[5, 6], [5, 9], [8, 9], [8, 7], [6, 7]], [[8, 9], [8, 9]]]
view raw loop_result.txt hosted with ❤ by GitHub

Monday, January 7, 2013

Loop identification

Moving on from branch identification (for the time being at least), I now take on the task of identifying the loops. Which actually is a little tricky.

Anyway, pasting what all the branches that have been identified look like as an matrix on a spreadsheet:



Its a pretty huge spreadsheet, so can only capture a small part of it as a snapshot. But this is just the matrix "branch_map" computed in the previous blog pasted into cells of a spreadsheet.

For any circuit, the number of independent loops is equal to (B-N+1) where B is the number of branches, N is the number of nodes. The length of "node_list" will give us N and the number of elements (non-null) in the upper triangular part of branch_matrix will give us B. This can be found by this simple block of code:
---------------------------------------------------------------------------------------------------------
number_of_branches=0
for c1 in range(len(node_list)):
                for c2 in range(c1+1, len(node_list)):
                                for parallel_branches in branch_map[c1][c2]:
                                                number_of_branches+=1
print number_of_branches
---------------------------------------------------------------------------------------------------------

So we can now set the number of loops we are expecting to find.

A basic starting idea on how to get loops.

1. Take the branch_map matrix and start from the first element in the upper triangular part.
2. The way nodes have been determined, this will be the uppermost row in the connected circuit of the input csv file. Nodes will then be in later columns of the same row and then in later rows. So esentially moving left to right and then down and then again left to right.
3. So by moving to the right from the first element (say element [0, 1] which is [0 5] ;[0 6] ;[0 7] ;[0 8]), we encounter element [0,2] which is [0 5] ;[0 4] ;[0 3] ;[0 2] ;[0 1] ;[1 1] ;[2 1].
4. Element [0,1] contains the branch which connects node [0, 5] to [0, 8]. Element [0,2] contains the branch which connects node [0, 5] to [2,1].
5. Since, we are on row 0 of branch_map, the common element in node 0 which is [0,5].
6. So, if we traverse element [0, 1] in the reverse direction and element [0, 2] in the forwarsd direction, we are moving from right to left and then down.
7. Now, in an attempt to complete the loop, we move down from element [0, 2]. The first non-empty element encountered is [1,2].
8. This is [0 8] ;[1 8] ;[2 8] ;[2 2] ;[2 1].
9. This connects node [2, 1] to [0, 8] through the the "jump1" jump label. And this essentially completes a loop because [0,8] was where we started.


10. Repeating this sequence gives some very good results on other loops.
11. [0 5] ;[0 6] ;[0 7] ;[0 8] in element [0, 1] in reverse direction and move right
[0 5] ;[1 5] ;[2 5] ;[3 5] ;[4 5] ;[5 5] ;[6 5] in forward direction and then move down.
[6 3] ;[6 4] ;[6 5] in the reverse direction and then move left
[6 3] ;[6 2] ;[6 1] ;[6 0] in the forward direction and then move up
[2 1] ;[2 0] ;[3 0] ;[4 0] ;[5 0] ;[6 0] in the reverse direction and then move left
[2 1] ;[2 2] ;[2 8] ;[1 8] ;[0 8] in the forward direction and the loop ends.

So this seems to be an algorithm! Need to code it. But still need to keep thinking about loopholes.

Saturday, January 5, 2013

Branch identification -IV

Another small addition to the code.

While adding jump labels, as mentioned in the previous post, the jump label should not be adjacent to a node as jumps should not happen from one node directly to the other but along segments of a branch. To ensure this doesn't happen:



# Check if a jump is not next to a node.
for c1 in range(len(node_list)):
for jump_check_dir in node_iter_rule[c1].keys():
if (jump_check_dir=="up"):
if (len(conn_matrix[node_list[c1][0]-1][node_list[c1][1]])>3):
if (conn_matrix[node_list[c1][0]-1][node_list[c1][1]].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0]-1, node_list[c1][1])
if (jump_check_dir=="down"):
if (len(conn_matrix[node_list[c1][0]+1][node_list[c1][1]])>3):
if (conn_matrix[node_list[c1][0]+1][node_list[c1][1]].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0]+1, node_list[c1][1])
if (jump_check_dir=="left"):
if (len(conn_matrix[node_list[c1][0]][node_list[c1][1]-1])>3):
if (conn_matrix[node_list[c1][0]][node_list[c1][1]-1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0], node_list[c1][1]-1)
if (jump_check_dir=="right"):
if (len(conn_matrix[node_list[c1][0]][node_list[c1][1]+1])>3):
if (conn_matrix[node_list[c1][0]][node_list[c1][1]+1].lower()[0:4]=="jump"):
print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0], node_list[c1][1]+1)
view raw branch7.py hosted with ❤ by GitHub



No need to post the entire code again.

A couple of additional comments:

1. Quite a lot of rules have been fabricated and messages printed, but no exceptions have been generated. This will be left for later.
2. Can different sheets of the same spreadsheet be used maybe for larger circuits? Worth looking into.


Friday, January 4, 2013

Branch identification - III

Another round of changes.

When a spreadsheet is saved as a csv file, a couple of things could be done depending on the settings:

1. The contents of the cells could be padded with an additional set of quotes.

2. The last element of every row contains a carriage return "\n".


An absolute requirement is that the column separator is a comma and not a semicolon.

With respect to the above, added the following block of code:


# Remove any leading or trailing quotes and also carriage returns (\n) that may have been added while generating the csv file.
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
if conn_matrix[c1][c2]:
if "\n" in conn_matrix[c1][c2]:
conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
if conn_matrix[c1][c2]:
while (conn_matrix[c1][c2][0]=='"' or conn_matrix[c1][c2][0]=="'"):
conn_matrix[c1][c2]=conn_matrix[c1][c2][1:]
while (conn_matrix[c1][c2][-1]=='"' or conn_matrix[c1][c2][-1]=="'"):
conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
view raw branch2.py hosted with ❤ by GitHub

So this ensures, that every element of the array (list of lists actually) conn_matrix is a regular string without an additional set of quotes or a carriage return at the end.

The next change is a huge one. In any circuit, it is always possible that wires may cross each other without forming a connection. So a jumper has to be included. The jumper also performs another task. In a large circuit where smaller networks may be included conveniently as modules with electrical connections, the jumper connections could make a huge difference because the modules can be conveniently lined up maybe at the top of the spreadsheet and the main circuit could be below.

So this means we need to add jumper connections to the circuit. A few rules devised:

1. A jumper connection has to be the end-point. It can't be a node and it can't have elements (wires or devices) both before and after it.
2. Also, jumper can be adjacent to a node. Bring the branch out from the node explicitly with a "wire" or a device and then connect a jumper. This is to make sure that we don't have to jump directly from one node to another. The jumps are between two branches. So there has to be at least one separator from a node.
3. The jumper name has to start with "jump". Case does not matter so "jump_a" is the same as "Jump_a" but the need to be sensible about labeling remains.
4. Can't have more than two jumpers of the same label. If there is a need t join more than two separate branches at a give node, split that terminating node up into two receiving branches and add two separate receiving jumper labels.
5. Every jumper must have another jumper.
6. Two jumps can't be next to each other - in the adjacent cells that is.

So with this, here is the code:

#! /usr/bin/env python
import sys, math, matrix
new_file = open("testckt.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire" where a zero impedance direct connection exists.
# Where no connection nor device (resitor, inductor etc) exists, a '' will be found.
# The devices will be strings. Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# Remove any leading or trailing quotes and also carriage returns (\n) that may have been added while generating the csv file.
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
if conn_matrix[c1][c2]:
if "\n" in conn_matrix[c1][c2]:
conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
if conn_matrix[c1][c2]:
while (conn_matrix[c1][c2][0]=='"' or conn_matrix[c1][c2][0]=="'"):
conn_matrix[c1][c2]=conn_matrix[c1][c2][1:]
while (conn_matrix[c1][c2][-1]=='"' or conn_matrix[c1][c2][-1]=="'"):
conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
jump_list=[]
# Check for jump label sanity and add a list of elements where jumps exist.
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2]==''):
del curr_element["exist"]
del curr_element["jump"]
elif (len(conn_matrix[c1][c2])>3):
if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
del curr_element["exist"]
else:
del curr_element["jump"]
else:
del curr_element["jump"]
if ("jump" in curr_element):
if (c1<conn_rows-1):
next_row_element = {"exist":0, "jump":1}
if (conn_matrix[c1+1][c2]==''):
del next_row_element["exist"]
del next_row_element["jump"]
elif (len(conn_matrix[c1+1][c2])>3):
if (conn_matrix[c1+1][c2].lower()[0:4] == "jump"):
del next_row_element["exist"]
else:
del next_row_element["jump"]
else:
del next_row_element["jump"]
else:
next_row_element = {}
if (c1>0):
prev_row_element = {"exist":0, "jump":1}
if (conn_matrix[c1-1][c2]==''):
del prev_row_element["exist"]
del prev_row_element["jump"]
elif (len(conn_matrix[c1-1][c2])>3):
if (conn_matrix[c1-1][c2].lower()[0:4] == "jump"):
del prev_row_element["exist"]
else:
del prev_row_element["jump"]
else:
del prev_row_element["jump"]
else:
prev_row_element = {}
if (c2<conn_columns-1):
next_col_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2+1]==''):
del next_col_element["exist"]
del next_col_element["jump"]
elif (len(conn_matrix[c1][c2+1])>3):
if (conn_matrix[c1][c2+1].lower()[0:4] == "jump"):
del next_col_element["exist"]
else:
del next_col_element["jump"]
else:
del next_col_element["jump"]
else:
next_col_element = {}
if (c2>0):
prev_col_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2-1]==''):
del prev_col_element["exist"]
del prev_col_element["jump"]
elif (len(conn_matrix[c1][c2-1])>3):
if (conn_matrix[c1][c2-1].lower()[0:4] == "jump"):
del prev_col_element["exist"]
else:
del prev_col_element["jump"]
else:
del prev_col_element["jump"]
else:
prev_col_element = {}
if ("jump" in next_row_element or "jump" in next_col_element or "jump" in prev_row_element or "jump" in prev_col_element):
print "Two jumps can't be adjacent to each other."
print "Check jump at row %d, column %d" %(c1, c2)
if ("exist" in next_row_element):
if ("exist" in next_col_element or "exist" in prev_row_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "down"])
elif ("exist" in next_col_element):
if ("exist" in next_row_element or "exist" in prev_row_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "right"])
elif ("exist" in prev_row_element):
if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "up"])
elif ("exist" in prev_col_element):
if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_row_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "left"])
# Create a dictionary of jumps - for each jump label - there is a list with two elements.
jump_matrix={}
for c1 in range(len(jump_list)):
jump_count=1
for c2 in range(len(jump_list)):
if not c1==c2:
if jump_list[c1][2]==jump_list[c2][2]:
jump_matrix[jump_list[c1][2]]=[[[jump_list[c1][0], jump_list[c1][1]], jump_list[c1][3]], [[jump_list[c2][0], jump_list[c2][1]], jump_list[c2][3]]]
jump_count=jump_count+1
if (jump_count<2):
print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
elif (jump_count>2):
print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
del jump_matrix[jump_list[c1][2]]
# A node is defined as a junction of 3 or more branches.
node_list=[]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2]==''):
del curr_element["exist"]
del curr_element["jump"]
elif (len(conn_matrix[c1][c2])>3):
if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
del curr_element["exist"]
else:
del curr_element["jump"]
if ("exist" in curr_element):
if ((c1==0 and c2==0) or (c1==conn_rows-1 and c2==conn_columns-1) or (c1==0 and c2==conn_columns-1) or (c1==conn_rows-1 and c2==0)):
# If its a corner point it can't be a node. This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (c1==0):
# If it is the first row,
# check if the element in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
# Then check if the element in next row and same column is connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]==''):
node_list.append([c1, c2])
if (c1==conn_rows-1):
# If it is the last row,
# check if the elements in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
if not (conn_matrix[c1-1][c2]==''):
# Then check if element in the previous row and same column is connected. Look for a T junction.
node_list.append([c1, c2])
if (c2==0):
# If it is the first column,
# check if the element in the next column and same row is connected.
if not (conn_matrix[c1][c2+1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c2==conn_columns-1):
# If it is the last column,
# check if the element in the previous column and same row is connected.
if not (conn_matrix[c1][c2-1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c1>0 and c1<conn_rows-1 and c2>0 and c2<conn_columns-1):
# If the element is not on the outer boundary
if (conn_matrix[c1][c2+1]!='' and conn_matrix[c1][c2-1]!=''):
# Check if the elements in next and previous columns and same row are connected
if (conn_matrix[c1+1][c2]!='' or conn_matrix[c1-1][c2]!=''):
# Then check if elements in either the next and previous row and same column are connected
node_list.append([c1, c2])
elif (conn_matrix[c1+1][c2]!='' and conn_matrix[c1-1][c2]!=''):
if (conn_matrix[c1][c2+1]!='' or conn_matrix[c1][c2-1]!=''):
node_list.append([c1, c2])
else:
pass
# This list contains all the nodes that are T or + junctions.
print "*"*60
print node_list
print "*"*60
print "*"*60
print "*"*60
print "*"*60
# Map of branches between nodes in node_list
branch_map=[]
# Creating an square of the dimension of node_list.
# Each element will be a list of the series connection of branches between the nodes.
for c1 in range(len(node_list)):
branch_rows=[]
for c2 in range(len(node_list)):
branch_rows.append([])
branch_map.append(branch_rows)
# Generate a search rule for each node.
# The concept is to start at a node and search until another node is reached.
node_iter_rule=[]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
iter_rule={"left":0, "down":1, "right":2, "up":3}
# For nodes in the outer edges, the rules going outwards will be removed.
if (node_row==0):
del(iter_rule["up"])
if (node_row==conn_rows-1):
del(iter_rule["down"])
if (node_column==0):
del(iter_rule["left"])
if (node_column==conn_columns-1):
del(iter_rule["right"])
# Depending on the non-existence of elements in a direction, those rules will be removed.
if (node_row>0) and (node_row<conn_rows-1) and (node_column>0) and (node_column<conn_columns-1):
if (conn_matrix[node_row-1][node_column]==''):
del(iter_rule["up"])
if (conn_matrix[node_row+1][node_column]==''):
del(iter_rule["down"])
if (conn_matrix[node_row][node_column+1]==''):
del(iter_rule["right"])
if (conn_matrix[node_row][node_column-1]==''):
del(iter_rule["left"])
node_iter_rule.append(iter_rule)
# For each node in node_list perform the search operation.
# Each node has a list of possible search rules.
# Perform a search for each rule.
# From the starting node, advance in the direction of the rule.
# After advancing, check if the next element is a node.
# If it is a node, stop.
# If it is not a node, there can be only two directions of movement.
# Move in a direction and check is an element exists.
# If it exists, check if it is not already an element encountered - shouldn't be moving backwards.
# If a new element is encountered, update the element is branch iter and continue.
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
print branch_dir
# This variable is used when jumps are encountered.
jump_executed=""
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and the sense of movement.
# Depending on the sense of movement, update the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement has taken place
# To ensure that we don't go back from the next element after the jump.
if (len(conn_matrix[next_node_row][next_node_column])>3):
if (conn_matrix[next_node_row][next_node_column].lower()[0:4] == "jump"):
jump_trace=conn_matrix[next_node_row][next_node_column]
if (jump_matrix[jump_trace][0][0] == [next_node_row, next_node_column]):
if (jump_matrix[jump_trace][1][1] == "left"):
next_node_row=jump_matrix[jump_trace][1][0][0]
next_node_column=jump_matrix[jump_trace][1][0][1] - 1
jump_executed="left"
elif (jump_matrix[jump_trace][1][1] == "right"):
next_node_row=jump_matrix[jump_trace][1][0][0]
next_node_column=jump_matrix[jump_trace][1][0][1] + 1
jump_executed="right"
elif (jump_matrix[jump_trace][1][1] == "up"):
next_node_row=jump_matrix[jump_trace][1][0][0] - 1
next_node_column=jump_matrix[jump_trace][1][0][1]
jump_executed="up"
elif (jump_matrix[jump_trace][1][1] == "down"):
next_node_row=jump_matrix[jump_trace][1][0][0] + 1
next_node_column=jump_matrix[jump_trace][1][0][1]
jump_executed="down"
elif (jump_matrix[jump_trace][1][0] == [next_node_row, next_node_column]):
if (jump_matrix[jump_trace][0][1] == "left"):
next_node_row=jump_matrix[jump_trace][0][0][0]
next_node_column=jump_matrix[jump_trace][0][0][1] - 1
jump_executed="left"
elif (jump_matrix[jump_trace][0][1] == "right"):
next_node_row=jump_matrix[jump_trace][0][0][0]
next_node_column=jump_matrix[jump_trace][0][0][1] + 1
jump_executed="right"
elif (jump_matrix[jump_trace][0][1] == "up"):
next_node_row=jump_matrix[jump_trace][0][0][0] - 1
next_node_column=jump_matrix[jump_trace][0][0][1]
jump_executed="up"
elif (jump_matrix[jump_trace][0][1] == "down"):
next_node_row=jump_matrix[jump_trace][0][0][0] + 1
next_node_column=jump_matrix[jump_trace][0][0][1]
jump_executed="down"
branch_iter.append([next_node_row, next_node_column])
# This temporary variable is to ensure, two advancements don't take place in one loop.
branch_proceed=0
if ((next_node_column>0) and branch_proceed==0):
# We are trying to go left, so check if we didn't jump right.
if (conn_matrix[next_node_row][next_node_column-1] != '' and jump_executed!="right"):
# Next check is if we are going backwards.
if not ([next_node_row, next_node_column-1] in branch_iter):
next_node_column=next_node_column-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_row>0) and branch_proceed==0):
# We are trying to go up, so check if we didn't jump down.
if (conn_matrix[next_node_row-1][next_node_column] != '' and jump_executed!="down"):
if not ([next_node_row-1, next_node_column] in branch_iter):
next_node_row=next_node_row-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_column<conn_columns-1) and branch_proceed==0):
# We are trying to go right, so check if we didn't jump left.
if (conn_matrix[next_node_row][next_node_column+1] != '' and jump_executed!="left"):
if not ([next_node_row, next_node_column+1] in branch_iter):
next_node_column=next_node_column+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_row<conn_rows-1) and branch_proceed==0):
# We are trying to go down, so check if we didn't jump up.
if (conn_matrix[next_node_row+1][next_node_column] != '' and jump_executed!="up"):
if not ([next_node_row+1, next_node_column] in branch_iter):
next_node_row=next_node_row+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches."
print [next_node_row, next_node_column]
break
else:
branch_iter.append([next_node_row, next_node_column])
branch_map[c1][node_list.index([next_node_row, next_node_column])].append(branch_iter)
print branch_iter
print "*"*70
view raw netw_inter.py hosted with ❤ by GitHub

The logic is as follows:

1. First create a list of jump labels, their co-ordinates, and the direction to move in to reach the adjacent element.
2. So, here when an jump is encountered, the checks performed are:
-Is it a node?
-Is it next to another jump?
-Is it a terminal element?



jump_list=[]
# Check for jump label sanity and add a list of elements where jumps exist.
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2]==''):
del curr_element["exist"]
del curr_element["jump"]
elif (len(conn_matrix[c1][c2])>3):
if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
del curr_element["exist"]
else:
del curr_element["jump"]
else:
del curr_element["jump"]
if ("jump" in curr_element):
if (c1<conn_rows-1):
next_row_element = {"exist":0, "jump":1}
if (conn_matrix[c1+1][c2]==''):
del next_row_element["exist"]
del next_row_element["jump"]
elif (len(conn_matrix[c1+1][c2])>3):
if (conn_matrix[c1+1][c2].lower()[0:4] == "jump"):
del next_row_element["exist"]
else:
del next_row_element["jump"]
else:
del next_row_element["jump"]
else:
next_row_element = {}
if (c1>0):
prev_row_element = {"exist":0, "jump":1}
if (conn_matrix[c1-1][c2]==''):
del prev_row_element["exist"]
del prev_row_element["jump"]
elif (len(conn_matrix[c1-1][c2])>3):
if (conn_matrix[c1-1][c2].lower()[0:4] == "jump"):
del prev_row_element["exist"]
else:
del prev_row_element["jump"]
else:
del prev_row_element["jump"]
else:
prev_row_element = {}
if (c2<conn_columns-1):
next_col_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2+1]==''):
del next_col_element["exist"]
del next_col_element["jump"]
elif (len(conn_matrix[c1][c2+1])>3):
if (conn_matrix[c1][c2+1].lower()[0:4] == "jump"):
del next_col_element["exist"]
else:
del next_col_element["jump"]
else:
del next_col_element["jump"]
else:
next_col_element = {}
if (c2>0):
prev_col_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2-1]==''):
del prev_col_element["exist"]
del prev_col_element["jump"]
elif (len(conn_matrix[c1][c2-1])>3):
if (conn_matrix[c1][c2-1].lower()[0:4] == "jump"):
del prev_col_element["exist"]
else:
del prev_col_element["jump"]
else:
del prev_col_element["jump"]
else:
prev_col_element = {}
if ("jump" in next_row_element or "jump" in next_col_element or "jump" in prev_row_element or "jump" in prev_col_element):
print "Two jumps can't be adjacent to each other."
print "Check jump at row %d, column %d" %(c1, c2)
if ("exist" in next_row_element):
if ("exist" in next_col_element or "exist" in prev_row_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "down"])
elif ("exist" in next_col_element):
if ("exist" in next_row_element or "exist" in prev_row_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "right"])
elif ("exist" in prev_row_element):
if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_col_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "up"])
elif ("exist" in prev_col_element):
if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_row_element):
print "Jump has to be the extreme connector on a branch segment."
print "Check jump at row %d, column %d" %(c1, c2)
else:
jump_list.append([c1, c2, conn_matrix[c1][c2], "left"])
view raw branch3.py hosted with ❤ by GitHub


3. Next is jump_matrix is created where the jump labels are keys in a dictionary and their corresponding values are the two co-ordinates and the direction to move in to reach the next element.



# Create a dictionary of jumps - for each jump label - there is a list with two elements.
jump_matrix={}
for c1 in range(len(jump_list)):
jump_count=1
for c2 in range(len(jump_list)):
if not c1==c2:
if jump_list[c1][2]==jump_list[c2][2]:
jump_matrix[jump_list[c1][2]]=[[[jump_list[c1][0], jump_list[c1][1]], jump_list[c1][3]], [[jump_list[c2][0], jump_list[c2][1]], jump_list[c2][3]]]
jump_count=jump_count+1
if (jump_count<2):
print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
elif (jump_count>2):
print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
del jump_matrix[jump_list[c1][2]]
view raw branch4.py hosted with ❤ by GitHub

 4. Finding the node is almost the same except that it can't be a jump so a small bit of code to check that:


for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
curr_element = {"exist":0, "jump":1}
if (conn_matrix[c1][c2]==''):
del curr_element["exist"]
del curr_element["jump"]
elif (len(conn_matrix[c1][c2])>3):
if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
del curr_element["exist"]
else:
del curr_element["jump"]
view raw branch5.py hosted with ❤ by GitHub

 5. Identifying a branch.
- Start from a node as usual and move in one of the valid directions.
- Then check if the next element is a jump.
- If it is go to the jump matrix and find out which co-ordinates, the jump tag links.
- Find out which co-ordinate we are currently at a pick the other.
- Move in the direction indicated by the other co-ordinate.
- This brings us to the next valid element after the jump.
- Store this direction of jumping.

Check which direction we can move in from the new element and check if that is not opposite to the direction that a jump was made.
If OK, move in that direction and make the jump direction a null string.
Continue until a node is reached.



for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
print branch_dir
# This variable is used when jumps are encountered.
jump_executed=""
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
# If a jump is encountered.
# Look for the label in the jump_matrix dictionary
# Check which element has been encountered.
# Check the co-ordinates of the other element and the sense of movement.
# Depending on the sense of movement, update the new co-ordinates with respect
# to the other element
# Add a flag to show which direction movement has taken place
# To ensure that we don't go back from the next element after the jump.
if (len(conn_matrix[next_node_row][next_node_column])>3):
if (conn_matrix[next_node_row][next_node_column].lower()[0:4] == "jump"):
jump_trace=conn_matrix[next_node_row][next_node_column]
if (jump_matrix[jump_trace][0][0] == [next_node_row, next_node_column]):
if (jump_matrix[jump_trace][1][1] == "left"):
next_node_row=jump_matrix[jump_trace][1][0][0]
next_node_column=jump_matrix[jump_trace][1][0][1] - 1
jump_executed="left"
elif (jump_matrix[jump_trace][1][1] == "right"):
next_node_row=jump_matrix[jump_trace][1][0][0]
next_node_column=jump_matrix[jump_trace][1][0][1] + 1
jump_executed="right"
elif (jump_matrix[jump_trace][1][1] == "up"):
next_node_row=jump_matrix[jump_trace][1][0][0] - 1
next_node_column=jump_matrix[jump_trace][1][0][1]
jump_executed="up"
elif (jump_matrix[jump_trace][1][1] == "down"):
next_node_row=jump_matrix[jump_trace][1][0][0] + 1
next_node_column=jump_matrix[jump_trace][1][0][1]
jump_executed="down"
elif (jump_matrix[jump_trace][1][0] == [next_node_row, next_node_column]):
if (jump_matrix[jump_trace][0][1] == "left"):
next_node_row=jump_matrix[jump_trace][0][0][0]
next_node_column=jump_matrix[jump_trace][0][0][1] - 1
jump_executed="left"
elif (jump_matrix[jump_trace][0][1] == "right"):
next_node_row=jump_matrix[jump_trace][0][0][0]
next_node_column=jump_matrix[jump_trace][0][0][1] + 1
jump_executed="right"
elif (jump_matrix[jump_trace][0][1] == "up"):
next_node_row=jump_matrix[jump_trace][0][0][0] - 1
next_node_column=jump_matrix[jump_trace][0][0][1]
jump_executed="up"
elif (jump_matrix[jump_trace][0][1] == "down"):
next_node_row=jump_matrix[jump_trace][0][0][0] + 1
next_node_column=jump_matrix[jump_trace][0][0][1]
jump_executed="down"
branch_iter.append([next_node_row, next_node_column])
# This temporary variable is to ensure, two advancements don't take place in one loop.
branch_proceed=0
if ((next_node_column>0) and branch_proceed==0):
# We are trying to go left, so check if we didn't jump right.
if (conn_matrix[next_node_row][next_node_column-1] != '' and jump_executed!="right"):
# Next check is if we are going backwards.
if not ([next_node_row, next_node_column-1] in branch_iter):
next_node_column=next_node_column-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_row>0) and branch_proceed==0):
# We are trying to go up, so check if we didn't jump down.
if (conn_matrix[next_node_row-1][next_node_column] != '' and jump_executed!="down"):
if not ([next_node_row-1, next_node_column] in branch_iter):
next_node_row=next_node_row-1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_column<conn_columns-1) and branch_proceed==0):
# We are trying to go right, so check if we didn't jump left.
if (conn_matrix[next_node_row][next_node_column+1] != '' and jump_executed!="left"):
if not ([next_node_row, next_node_column+1] in branch_iter):
next_node_column=next_node_column+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
if ((next_node_row<conn_rows-1) and branch_proceed==0):
# We are trying to go down, so check if we didn't jump up.
if (conn_matrix[next_node_row+1][next_node_column] != '' and jump_executed!="up"):
if not ([next_node_row+1, next_node_column] in branch_iter):
next_node_row=next_node_row+1
branch_proceed=1
# Set jump to null after a movement. We can't go back anyway.
jump_executed=""
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches."
print [next_node_row, next_node_column]
break
else:
branch_iter.append([next_node_row, next_node_column])
branch_map[c1][node_list.index([next_node_row, next_node_column])].append(branch_iter)
print branch_iter
print "*"*70
view raw branch6.py hosted with ❤ by GitHub




Chose another test circuit.

Here two jumps are defined.

The output of the program is:
----------------------------------------------------------------------------------------------------
************************************************************
[[0, 5], [0, 8], [2, 1], [6, 0], [6, 3], [6, 5], [6, 7], [6, 12], [8, 12], [9, 5]]
************************************************************
************************************************************
************************************************************
************************************************************
down
[[0, 5], [1, 5], [2, 5], [3, 5], [4, 5], [5, 5], [6, 5]]
**********************************************************************
right
[[0, 5], [0, 6], [0, 7], [0, 8]]
**********************************************************************
left
[[0, 5], [0, 4], [0, 3], [0, 2], [0, 1], [1, 1], [2, 1]]
**********************************************************************
down
[[0, 8], [1, 8], [2, 8], [2, 2], [2, 1]]
**********************************************************************
right
[[0, 8], [0, 9], [0, 10], [0, 11], [0, 12], [1, 12], [2, 12], [3, 12], [4, 12], [5, 12], [6, 12]]
**********************************************************************
left
[[0, 8], [0, 7], [0, 6], [0, 5]]
**********************************************************************
right
[[2, 1], [2, 2], [2, 8], [1, 8], [0, 8]]
**********************************************************************
up
[[2, 1], [1, 1], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]
**********************************************************************
left
[[2, 1], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0]]
**********************************************************************
down
[[6, 0], [7, 0], [8, 0], [9, 0], [9, 1], [9, 2], [9, 3], [9, 4], [9, 5]]
**********************************************************************
right
[[6, 0], [6, 1], [6, 2], [6, 3]]
**********************************************************************
up
[[6, 0], [5, 0], [4, 0], [3, 0], [2, 0], [2, 1]]
**********************************************************************
right
[[6, 3], [6, 4], [6, 5]]
**********************************************************************
up
[[6, 3], [5, 3], [5, 7], [6, 7]]
**********************************************************************
left
[[6, 3], [6, 2], [6, 1], [6, 0]]
**********************************************************************
down
[[6, 5], [7, 5], [8, 5], [9, 5]]
**********************************************************************
right
[[6, 5], [6, 6], [6, 7]]
**********************************************************************
up
[[6, 5], [5, 5], [4, 5], [3, 5], [2, 5], [1, 5], [0, 5]]
**********************************************************************
left
[[6, 5], [6, 4], [6, 3]]
**********************************************************************
right
[[6, 7], [6, 8], [6, 9], [6, 10], [6, 11], [6, 12]]
**********************************************************************
up
[[6, 7], [5, 7], [5, 3], [6, 3]]
**********************************************************************
left
[[6, 7], [6, 6], [6, 5]]
**********************************************************************
down
[[6, 12], [7, 12], [8, 12]]
**********************************************************************
up
[[6, 12], [5, 12], [4, 12], [3, 12], [2, 12], [1, 12], [0, 12], [0, 11], [0, 10], [0, 9], [0, 8]]
**********************************************************************
left
[[6, 12], [6, 11], [6, 10], [6, 9], [6, 8], [6, 7]]
**********************************************************************
down
[[8, 12], [9, 12], [10, 12], [11, 12], [11, 11], [11, 10], [11, 9], [11, 8], [11, 7], [11, 6], [11, 5], [10, 5], [9, 5]]
**********************************************************************
up
[[8, 12], [7, 12], [6, 12]]
**********************************************************************
left
[[8, 12], [8, 11], [8, 10], [8, 9], [8, 8], [9, 8], [9, 7], [9, 6], [9, 5]]
**********************************************************************
down
[[9, 5], [10, 5], [11, 5], [11, 6], [11, 7], [11, 8], [11, 9], [11, 10], [11, 11], [11, 12], [10, 12], [9, 12], [8, 12]]
**********************************************************************
right
[[9, 5], [9, 6], [9, 7], [9, 8], [8, 8], [8, 9], [8, 10], [8, 11], [8, 12]]
**********************************************************************
up
[[9, 5], [8, 5], [7, 5], [6, 5]]
**********************************************************************
left
[[9, 5], [9, 4], [9, 3], [9, 2], [9, 1], [9, 0], [8, 0], [7, 0], [6, 0]]
**********************************************************************
16


----------------------------------------------------------------------------------------------------

Thursday, January 3, 2013

Branch identification - II

A mistake in the previous code. If there are parallel branches between two nodes, there will be a problem. Take a look at the circuit again.


Between Elements 9E ([8,4]) and 8I ([7,8]) there are two parallel branches. The first one goes: 9E-9F-9G-8G-8H-8I. The second one goes: 9E-10E-11E-11F-11G-11H-11I-10I-9I-8I.

But the code that updates the branch matrix is:
----------------------------------------------------------------------------
branch_map[c1][node_list.index([next_node_row, next_node_column])] = branch_iter
----------------------------------------------------------------------------

This will overwrite the second branch when that is detected. So the statement needs to be changed as:
------------------------------------------------------------------------------
branch_map[c1][node_list.index([next_node_row, next_node_column])].append(branch_iter)
------------------------------------------------------------------------------

This adds the new branch to the existing branch found between the nodes. Again an array (list of lists) where an element is a list of lists of lists!

Wednesday, January 2, 2013

Branch identification

The previous program was to find the number of nodes in the circuit. A node was defined as a junction of three or four nodes. The next step is to be able to identify the branches between these nodes.

The method I have used is a search routine that starts from a node and continues until another node has reached. This is because of one major constraint imposed on the spreadsheet. Connections have to be made either vertical or horizontal and can't be made diagonal. So if you need a diagonal connection you have to go along a column and then a row.

So when starting from a node, there are certain search directions depending on the number of branches at that node - if is a +, all four search directions (up, down, right and left) are possible while if it is a T junction, three search directions may be possible (for example, up, right and left).

If the next element in the search direction is not a node, there can be two directions of searching - forward or backward. To ensure forward search, check if the new element has already been encountered. If so, that is the wrong direction.

If the next element is a node, stop the search.

If it is not a node, but another new element, continue as above.

Another test circuit has been taken:




Anyway, here is the code:


#! /usr/bin/env python
import sys, math, matrix
new_file = open("testckt.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire" where a zero impedance direct connection exists.
# Where no connection nor device (resitor, inductor etc) exists, a '' will be found.
# The devices will be strings. Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# A node is defined as a junction of 3 or more branches.
node_list=[]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
if not (conn_matrix[c1][c2]==''):
if ((c1==0 and c2==0) or (c1==conn_rows-1 and c2==conn_columns-1) or (c1==0 and c2==conn_columns-1) or (c1==conn_rows-1 and c2==0)):
# If its a corner point it can't be a node. This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (c1==0):
# If it is the first row,
# check if the element in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
# Then check if the element in next row and same column is connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]==''):
node_list.append([c1, c2])
if (c1==conn_rows-1):
# If it is the last row,
# check if the elements in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
if not (conn_matrix[c1-1][c2]==''):
# Then check if element in the previous row and same column is connected. Look for a T junction.
node_list.append([c1, c2])
if (c2==0):
# If it is the first column,
# check if the element in the next column and same row is connected.
if not (conn_matrix[c1][c2+1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c2==conn_columns-1):
# If it is the last column,
# check if the element in the previous column and same row is connected.
if not (conn_matrix[c1][c2-1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c1>0 and c1<conn_rows-1 and c2>0 and c2<conn_columns-1):
# If the element is not on the outer boundary
if (conn_matrix[c1][c2+1]!='' and conn_matrix[c1][c2-1]!=''):
# Check if the elements in next and previous columns and same row are connected
if (conn_matrix[c1+1][c2]!='' or conn_matrix[c1-1][c2]!=''):
# Then check if elements in either the next and previous row and same column are connected
node_list.append([c1, c2])
elif (conn_matrix[c1+1][c2]!='' and conn_matrix[c1-1][c2]!=''):
if (conn_matrix[c1][c2+1]!='' or conn_matrix[c1][c2-1]!=''):
node_list.append([c1, c2])
else:
pass
# This list contains all the nodes that are T or + junctions.
print "*"*60
print node_list
print "*"*60
print "*"*60
print "*"*60
print "*"*60
# Map of branches between nodes in node_list
branch_map=[]
# Creating an square of the dimension of node_list.
# Each element will be a list of the series connection of branches between the nodes.
for c1 in range(len(node_list)):
branch_rows=[]
for c2 in range(len(node_list)):
branch_rows.append([])
branch_map.append(branch_rows)
# Generate a search rule for each node.
# The concept is to start at a node and search until another node is reached.
node_iter_rule=[]
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
iter_rule={"left":0, "down":1, "right":2, "up":3}
# For nodes in the outer edges, the rules going outwards will be removed.
if (node_row==0):
del(iter_rule["up"])
if (node_row==conn_rows-1):
del(iter_rule["down"])
if (node_column==0):
del(iter_rule["left"])
if (node_column==conn_columns-1):
del(iter_rule["right"])
# Depending on the non-existence of elements in a direction, those rules will be removed.
if (node_row>0) and (node_row<conn_rows-1) and (node_column>0) and (node_column<conn_columns-1):
if (conn_matrix[node_row-1][node_column]==''):
del(iter_rule["up"])
if (conn_matrix[node_row+1][node_column]==''):
del(iter_rule["down"])
if (conn_matrix[node_row][node_column+1]==''):
del(iter_rule["right"])
if (conn_matrix[node_row][node_column-1]==''):
del(iter_rule["left"])
node_iter_rule.append(iter_rule)
# For each node in node_list perform the search operation.
# Each node has a list of possible search rules.
# Perform a search for each rule.
# From the starting node, advance in the direction of the rule.
# After advancing, check if the next element is a node.
# If it is a node, stop.
# If it is not a node, there can be only two directions of movement.
# Move in a direction and check is an element exists.
# If it exists, check if it is not already an element encountered - shouldn't be moving backwards.
# If a new element is encountered, update the element is branch iter and continue.
for c1 in range(len(node_list)):
node_row=node_list[c1][0]
node_column=node_list[c1][1]
for branch_dir in node_iter_rule[c1].keys():
branch_iter=[]
branch_iter.append([node_row, node_column])
# Initial advancement.
if (branch_dir=="left"):
if (node_column>0):
next_node_row=node_row
next_node_column=node_column-1
if (branch_dir=="down"):
if (node_row<conn_rows-1):
next_node_row=node_row+1
next_node_column=node_column
if (branch_dir=="right"):
if (node_column<conn_columns-1):
next_node_row=node_row
next_node_column=node_column+1
if (branch_dir=="up"):
if (node_row>0):
next_node_row=node_row-1
next_node_column=node_column
print branch_dir
# Termination condition - next element is a node.
while not ([next_node_row, next_node_column] in node_list):
branch_iter.append([next_node_row, next_node_column])
# This temporary variable is to ensure, two advancements don't take place in one loop.
branch_proceed=0
if ((next_node_column>0) and branch_proceed==0):
if not (conn_matrix[next_node_row][next_node_column-1]==''):
# Next check is if we are going backwards.
if not ([next_node_row, next_node_column-1] in branch_iter):
next_node_column=next_node_column-1
branch_proceed=1
if ((next_node_row>0) and branch_proceed==0):
if not (conn_matrix[next_node_row-1][next_node_column]==''):
if not ([next_node_row-1, next_node_column] in branch_iter):
next_node_row=next_node_row-1
branch_proceed=1
if ((next_node_column<conn_columns-1) and branch_proceed==0):
if not (conn_matrix[next_node_row][next_node_column+1]==''):
if not ([next_node_row, next_node_column+1] in branch_iter):
next_node_column=next_node_column+1
branch_proceed=1
if ((next_node_row<conn_rows-1) and branch_proceed==0):
if not (conn_matrix[next_node_row+1][next_node_column]==''):
if not ([next_node_row+1, next_node_column] in branch_iter):
next_node_row=next_node_row+1
branch_proceed=1
# If no advancement is possible, it means circuit is broken.
# Can improve on this error message later.
if ([next_node_row, next_node_column] in branch_iter):
print "Error. Circuit broken! Close all branches."
break
else:
branch_iter.append([next_node_row, next_node_column])
branch_map[c1][node_list.index([next_node_row, next_node_column])]=branch_iter
print branch_iter
print "*"*70
view raw branch1.py hosted with ❤ by GitHub


And this is the result:
---------------------------------------------------------------------------------------------------------
************************************************************
[[0, 4], [0, 6], [2, 1], [2, 4], [5, 0], [5, 4], [5, 8], [7, 8], [8, 4]]
************************************************************
************************************************************
************************************************************
************************************************************
down
[[0, 4], [1, 4], [2, 4]]
**********************************************************************
right
[[0, 4], [0, 5], [0, 6]]
**********************************************************************
left
[[0, 4], [0, 3], [0, 2], [0, 1], [1, 1], [2, 1]]
**********************************************************************
down
[[0, 6], [1, 6], [2, 6], [2, 5], [2, 4]]
**********************************************************************
right
[[0, 6], [0, 7], [0, 8], [1, 8], [2, 8], [3, 8], [4, 8], [5, 8]]
**********************************************************************
left
[[0, 6], [0, 5], [0, 4]]
**********************************************************************
right
[[2, 1], [2, 2], [2, 3], [2, 4]]
**********************************************************************
up
[[2, 1], [1, 1], [0, 1], [0, 2], [0, 3], [0, 4]]
**********************************************************************
left
[[2, 1], [2, 0], [3, 0], [4, 0], [5, 0]]
**********************************************************************
down
[[2, 4], [3, 4], [4, 4], [5, 4]]
**********************************************************************
right
[[2, 4], [2, 5], [2, 6], [1, 6], [0, 6]]
**********************************************************************
up
[[2, 4], [1, 4], [0, 4]]
**********************************************************************
left
[[2, 4], [2, 3], [2, 2], [2, 1]]
**********************************************************************
down
[[5, 0], [6, 0], [7, 0], [8, 0], [8, 1], [8, 2], [8, 3], [8, 4]]
**********************************************************************
right
[[5, 0], [5, 1], [5, 2], [5, 3], [5, 4]]
**********************************************************************
up
[[5, 0], [4, 0], [3, 0], [2, 0], [2, 1]]
**********************************************************************
down
[[5, 4], [6, 4], [7, 4], [8, 4]]
**********************************************************************
right
[[5, 4], [5, 5], [5, 6], [5, 7], [5, 8]]
**********************************************************************
up
[[5, 4], [4, 4], [3, 4], [2, 4]]
**********************************************************************
left
[[5, 4], [5, 3], [5, 2], [5, 1], [5, 0]]
**********************************************************************
down
[[5, 8], [6, 8], [7, 8]]
**********************************************************************
up
[[5, 8], [4, 8], [3, 8], [2, 8], [1, 8], [0, 8], [0, 7], [0, 6]]
**********************************************************************
left
[[5, 8], [5, 7], [5, 6], [5, 5], [5, 4]]
**********************************************************************
down
[[7, 8], [8, 8], [9, 8], [10, 8], [10, 7], [10, 6], [10, 5], [10, 4], [9, 4], [8, 4]]
**********************************************************************
up
[[7, 8], [6, 8], [5, 8]]
**********************************************************************
left
[[7, 8], [7, 7], [7, 6], [8, 6], [8, 5], [8, 4]]
**********************************************************************
down
[[8, 4], [9, 4], [10, 4], [10, 5], [10, 6], [10, 7], [10, 8], [9, 8], [8, 8], [7, 8]]
**********************************************************************
right
[[8, 4], [8, 5], [8, 6], [7, 6], [7, 7], [7, 8]]
**********************************************************************
up
[[8, 4], [7, 4], [6, 4], [5, 4]]
**********************************************************************
left
[[8, 4], [8, 3], [8, 2], [8, 1], [8, 0], [7, 0], [6, 0], [5, 0]]
**********************************************************************


---------------------------------------------------------------------------------------------------------


Which is the correct result.

1. One thing I could do to speed up the result is take advantage of the symmetry of the matrix. If node 1 is connected to node 3, node 3 is connected to node 1. No need to do the search again. So I need to to do the search for node i and node k if k>i. Then just take the lower triangular part to be equal to the upper triangular part.

2. The diagonal elements are null. What will happen if there is a self loop - a loop originating and terminating at a node? But will something like that happen in practical electrical circuits?

More issues will be examined with other circuits. Probably will be at least two more versions of this code.

Here, I need to stop and comment about Python. The fact that an embedded objects are possible and that too of any dimension is fantastic. In the above code, we have an array with the elements being lists of lists! And add to that, the lists are not of the same length. Anything goes! Makes like a whole lot simpler.

Network representation

I need a way to describe a circuit that is both convenient to the user but won't require horrendous effort in programming or be a drain on the system. So would like to avoid GUI based circuit drawing. Also, to ask the user to describe the circuit as a net list will drive most people away.

One way I can think of is a spreadsheet that is saved as a csv file. This can be done with just about any spread sheet software. A sample case:


The above is a circuit description.

1. I haven't bothered about the objects yet so they are just named as "a", "b", "c" etc.
2. Connections that are zero impedance are named as "wire".
3. Empty cells imply no connection.
4. Connections have to be along a row or a column. Can't make diagonal connections.

The .csv file as a text file looks like this:
------------------------------------------------------------
,"wire","wire","b","wire","wire","d","wire"
,"wire",,,"wire",,,"wire"
"wire","wire",,,"wire",,,"wire"
"a",,,,"c",,,"wire"
"wire",,,,"wire",,,"wire"
"wire","wire","f","wire","wire",,"wire","wire"
"wire",,,,"k",,,"h"
"wire",,,,,,,"wire"
"wire","i","wire","wire","wire","wire","e","wire"
,,,,"g",,,"wire"
,,,,"wire","wire","wire","wire"

------------------------------------------------------------

The code to interpret this is:


#! /usr/bin/env python
import sys, math, matrix
new_file = open("testckt.csv","r")
# This matrix will read the .csv file
# The .csv file will contain the string "wire" where a zero impedance direct connection exists.
# Where no connection nor device (resitor, inductor etc) exists, a '' will be found.
# The devices will be strings. Maybe later will be actual object constructor calls.
conn_matrix=[]
for line in new_file:
print line
conn_matrix.append(line.split(","))
conn_rows=len(conn_matrix)
conn_columns=len(conn_matrix[0])
# A node is defined as a junction of 3 or more branches.
node_list=[]
for c1 in range(0, conn_rows):
for c2 in range(0, conn_columns):
if not (conn_matrix[c1][c2]==''):
if ((c1==0 and c2==0) or (c1==conn_rows-1 and c2==conn_columns-1) or (c1==0 and c2==conn_columns-1) or (c1==conn_rows-1 and c2==0)):
# If its a corner point it can't be a node. This prevents array index going out of range.
pass
# The next cases, can't be outer edges or corner points.
else:
if (c1==0):
# If it is the first row,
# check if the element in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
# Then check if the element in next row and same column is connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]==''):
node_list.append([c1, c2])
if (c1==conn_rows-1):
# If it is the last row,
# check if the elements in the next and previous columns and same row are connected.
if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
if not (conn_matrix[c1-1][c2]==''):
# Then check if element in the previous row and same column is connected. Look for a T junction.
node_list.append([c1, c2])
if (c2==0):
# If it is the first column,
# check if the element in the next column and same row is connected.
if not (conn_matrix[c1][c2+1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c2==conn_columns-1):
# If it is the last column,
# check if the element in the previous column and same row is connected.
if not (conn_matrix[c1][c2-1]==''):
# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
node_list.append([c1, c2])
if (c1>0 and c1<conn_rows-1 and c2>0 and c2<conn_columns-1):
# If the element is not on the outer boundary
if (conn_matrix[c1][c2+1]!='' and conn_matrix[c1][c2-1]!=''):
# Check if the elements in next and previous columns and same row are connected
if (conn_matrix[c1+1][c2]!='' or conn_matrix[c1-1][c2]!=''):
# Then check if elements in either the next and previous row and same column are connected
node_list.append([c1, c2])
elif (conn_matrix[c1+1][c2]!='' and conn_matrix[c1-1][c2]!=''):
# This one is probably a redundant check but I'll keep it anyway.
if (conn_matrix[c1][c2+1]!='' or conn_matrix[c1][c2-1]!=''):
node_list.append([c1, c2])
else:
pass
print "*"*60
# This list contains all the nodes that are T or + junctions.
print node_list
view raw net1.py hosted with ❤ by GitHub



The output is:
-------------------------------------------------------------------------------------
,"wire","wire","b","wire","wire","d","wire"

,"wire",,,"wire",,,"wire"

"wire","wire",,,"wire",,,"wire"

"a",,,,"c",,,"wire"

"wire",,,,"wire",,,"wire"

"wire","wire","f","wire","wire",,"wire","wire"

"wire",,,,"k",,,"h"

"wire",,,,,,,"wire"

"wire","i","wire","wire","wire","wire","e","wire"

,,,,"g",,,"wire"

,,,,"wire","wire","wire","wire"

************************************************************
[[0, 4], [5, 0], [5, 4], [5, 7], [8, 4], [8, 7]]

-------------------------------------------------------------------------------------


A couple of comments:

1. A break in the network won't be detected. For example, E8 and F6 are empty. Which means E6 or [5,4] is not a node. This will have to be dealt later maybe by filling up breaks with high resistances or simply throwing error exceptions. The user has to ensure all connections. If its open, connect a large resistance.

2. The circuit starts from the top of the spreadsheet. But even if there are a couple of empty lines, the program still works. There will be an offset in the row indices, that can be removed by detecting the number of empty rows.


The concept behind this node list is that while finding the loops to apply KVL, you can start at a node and snake your way until you other nodes and make your way back to the starting node. I will also need the number of branches so that I can determine the number of loops. That will be the next task.

Ahead, the actual objects will have to be embedded. For example, AC_Voltage(mag=100, freq=60, res=0.1) could be one of the elements above. This may need something like regular expressions.

Tuesday, January 1, 2013

Network interpreter

Happy New Year to all my blog readers. I hope this project reaches a significant stage by the end of this year.

There are two significant tasks to be taken up next:

1. Deciding on a manner in which a circuit will be represented that is convenient to the user and also that can be translated to matrices E, A and B in the ODE solver.

2. The ODE was solved with a fixed time step which may not work later. Reason - there may be branches of the circuit with ridiculously small time constants for which the integration time step will have to be decreased. Also, the control may use methods such as sine triangle pulse width modulation where to determine the crossing between the modulation signal and the carrier wave would need to the integration time step to be chosen according to the value of the modulation signal during a carrier wave.

I am going to take up task 1 first and will spend quite some time on it. My initial approach would be to use spreadsheets to design the circuit. The spreadsheet can be saved as a csv file that will be read by Python. The circuit will have to be represented as a connectivity matrix first from which the loops will have to be determined.