How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear
- by Pops
I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage.
In my scenario, a number of users who are hostile to each other are all trying to form networks of computers where all potential connections are known. The computers that one user needs to connect may not be the same as the ones another user needs to connect, though; user 1 might need to connect computers A, B and D while user 2 might need to connect computers B, C and E.
Image generated with the help of NCTM Graph Creator
I think the core of this is going to be an undirected cyclic graph, with nodes representing computers and edges representing Ethernet cables. However, due to the nature of the scenario, there are a few uncommon features that rule out adjacency lists and adjacency matrices (at least, without non-trivial modifications):
edges can become restricted-use; that is, if one user acquires a given network connection, no other user may use that connection
in the example, the green user cannot possibly connect to computer A, but the red user has connected B to E despite not having a direct link between them
in some cases, a given pair of nodes will be connected by more than one edge
in the example, there are two independent cables running from D to E, so the green and blue users were both able to connect those machines directly; however, red can no longer make such a connection
if two computers are connected by more than one cable, each user may own no more than one of those cables
I'll need to do several operations on this graph, such as:
determining whether any particular pair of computers is connected for a given user
identifying the optimal path for a given user to connect target computers
identifying the highest-latency computer connection for a given user (i.e. longest path without branching)
My first thought was to simply create a collection of all of the edges, but that's terrible for searching. The best thing I can think to do now is to modify an adjacency list so that each item in the list contains not only the edge length but also its cost and current owner. Is this a sensible approach? Assuming space is not a concern, would it be reasonable to create multiple copies of the graph (one for each user) rather than a single graph?
