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

data structuresgraph

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

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?

Best Answer

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.

Related Solutions

C++ Data Structures – Modeling a Network of Nodes and Edges

Graphs can be implemented in many ways, and the one you've outlined is certainly not wrong.

For C++ I think you should take a gander into the Boost C++ libraries (BGL) that also has a library specifically for implementing graphs. If you use that then you can also use algorithms implemented in BGL (searches and traversals) or even use the _edge and _vertex visitors directly.

Generic Adjacency List Graph implementation

Here's an implementation that I dug up from when I was dealing with graphs. Although it's in C#, with a few minor adjustments it could compile in Java.

To make it directed you would have to copy v.Adjacents.Add(new Edge(w, cost)); and reverse the direction, thereby taking up double the space.

I don't think it's any better than what you have though.

class Edge
{
    public Vertex Destination { get; set; }
    public double Cost { get; set; }

    public Edge(Vertex destination, double cost)
    {
        Destination = destination;
        Cost = cost;
    }

}

class Vertex
{
    public string Name { get; set; }
    public List<Edge> Adjacents { get; set; }
    public double Distance { get; set; }

    public Vertex(string name)
    {
        Name = name;
        Adjacents = new List<Edge>();
        Distance = double.MaxValue;
    }
}

class Graf
{
    private readonly Dictionary<string, Vertex> vertexmap = new Dictionary<string, Vertex>();

    public void AddEdge(string source, string dest, double cost)
    {
        var v = GetVertex(source);
        var w = GetVertex(dest);
        v.Adjacents.Add(new Edge(w, cost));
    }

    private Vertex GetVertex(string vertexname)
    {
        Vertex v;
        vertexmap.TryGetValue(vertexname, out v);
        if (v == null)
        {
            v = new Vertex(vertexname);
            vertexmap.Add(vertexname, v);
        }
        return v;
    }
}

Best Answer

Related Solutions

C++ Data Structures – Modeling a Network of Nodes and Edges

Generic Adjacency List Graph implementation

Related Topic