How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear

Question

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):

1. 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
2. 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
3. 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?

Answer 1

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?

It seems to me that you should use what we could label ”layered graphs”, i.e. add a combinator for graphs, say @, so that:

• If A and B are graphs then A@B is also a graph (i.e. can be fed to the algorithms of your graph library).
• The set of vertices in A@B is the union of vertices in A and B.
• The set of edges in A@B is the union of edges in A and B.
• The structure A@B does not own any vertex or edge, but rather uses A and B as data containers.

With such layered graphs, you can define K to be the kommon available information and R, G, B each private information so that each player is actually seeing R@K, G@K, B@K.

To actually implement this, you may look for a graph library implementing algorithms generically, i.e. so that the longest path algorithm etc. are parametrised by the actual representation of your graph. So if your library says

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

you can easily replace it with

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

where you are supplying the LayeredGraphs and borrowing the rest from the library.

Answer 2

What you need is called an "attributed graph". In an attributed graph, information (attributes) are attached to the arcs. A weighed graph one of the simplest attributed graphs.

To represent an attributed graph, you can use an adjacency list by adding extra columns or adjacency matrices by adding more information in each cell. Most algorithms for non-attributed graphs will work if you filter the arcs, based on the attributes. Many algorithms have been developed for attributed graphs, so I won't describe them here.

Answer 3

For those working in python, the networkX library has ready to use implementations:

For undirected graphs:
Multigraph

For directed graphs:
MultiDiGraph