Get all networks of connected nodes (Logic puzzle)

Question

I know this is a question which is more about logic than an actual programming issue, but I hope that someone may guide me into the correct direction to solve this. Look at it like the advent programming riddles :)

I have nodes, that are connected with each other over a port. I know the nodes and I know all relations. Now I need to get all possible networks.

To further clarify what I need, I made the following draft: Image of the network layout: https://ibb.co/51zmkfj

Legend:

• A-F: Nodes
• 1-5: Relations
• 6: Redundant relation (In case node D is out of order)
• I-IV: Networks I need to get in a List (All nodes per network, therefore a node can be in multiple networks)
• V: Redundant network which I must get in a separate list (With source and target node)

Please note, that the network can be much bigger and there may be more than one of these redundant networks

As written, I need these networks I-V. I tried various things and got a version working for I-IV, but it is a lot of code and I am probably overthinking the whole thing.

My approach:

• looping through the relations and creating a Dictionary<int, List<String>> with a random int identifier and the id+portNumber as a unique string of all relations that are connected with each other.
• Then I do a nested foreach with the Dictionary to compare each entry with the other entries to find any duplicates and Groups that are not complete.
• Then I remove these wrong groups from the Dictionary.
• After that, I remove the portNumber from all values in the list of the dictionary.

I also made a .NET Fiddle which is prepared with the data exactly as in the image above. https://dotnetfiddle.net/SQnZYs

Answer 1

As someone with a bit of networking experience I'd first like to point out that you can't plug multiple cables into the same port like that

I can see a couple of approaches here but you'll need to add some more information to your data model, such as a way of labelling a backup link as a seperate connection that doesn't get involved in a 'normal' network and therefore needs to be segregated.

The big thing though is that your terms need more refined definitions:

Object	Definition
Node	A collection of Ports (including Backup versions of those Ports).
Port	An object that can belong to one Network and has an arbitrary number of Connections.
Connection	Links two Ports, contained by a single Network.
Network	A collection of Ports and the Connections that link them together.
Backup	A Port, Connection or Network that is separate from the normal set such than Backup Ports and Backup Connections exist exclusively in Backup Networks.

Ok that last one is a bit clumsy, but I think it's a necessary part of the problem in this case. Withou some distinction between a standard link and a backup link you can't separate network V from the other networks. Of course not all of those objects are actual classes, they're concepts. The useful minimum seems to be: Node, Port and Connection, with Network and Backup becoming attributes... although in fairness you could probably replace Port with some logic, but it's useful in some ways.

---

With those definitions it should be possible to solve the problem. A psudo-code algorithm for it might be something like this:

For each Node:
    For each connected Port with no assigned network:
        Add port to new network.
        Add all Connections to network.
        Repeat for all connected ports.
    For each connected Backup Port with no assigned Backup Network:
        Add port to new Backup Network
        Add all Backup Connections to network.
        Repeat for all connected ports.

We could merge the two inner loops into one with the right data structure of course.

And since I'm fond of overly-engineered objects that make my top-level code easier to read (if not always easier to understand), the fact that I had some time on my hands today, and probably in the spirit of Xmas... I wrote a fun implementation for you.

Caution: not for production use!

(Seriously, don't even look at all the fun I had with ToString() overrides.)