11

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.

enter image description here

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?

  • This somehow seems relevant. youtube.com/watch?v=xdiL-ADRTxQ – RubberDuck Aug 15 '14 at 17:25
  • I'm not really seeing how that's going to help here. – Pops Aug 15 '14 at 17:58
  • So I thought about this for a while. In most algorithms for graphs, you have primarily two things you need to do: enumerate neighbors or find the weight of an edge. The questions you listed all involve only one user. For a single user, enumerating neighbors or finding the weight of an edge can be answered either in constant time (if the user count is bounded) or in log N by simply mirroring either adjacency list or matrix with an "ownership". To that end, I think either can be extended easily and should be chosen based on traditional strengths, rather than getting distracted by the user part. – J Trana Aug 16 '14 at 4:52
6

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.

  • Whoops, disregard my previous comment, I misread your answer a bit. This is basically what I'm doing, although I failed to take advantage of existing graph libraries, because I foolishly didn't think to see if any existed. – Pops Aug 18 '14 at 23:41
1

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.

  • 1
    surely an adjacency matrix normally can't represent more than 1 edge between each pair of nodes – jk. Aug 20 '14 at 6:00
  • 1
    @jk, normally you are correct. But the info attached in the adjacency matrix could have the number of arcs and separate attributes for each arc. But in most cases, I would use an adjacency list because it would be simpler. – walrii Aug 20 '14 at 20:28
  • 1
    if you are attaching info for every edge to the cell you effectively have an adjaceny list anyway, you lose the benefit a matrix gives you for dense graphs – jk. Aug 21 '14 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.