Easiest implementation of a barpartite graph in javascript?

Question

I'm working on a project that the algorithm requires using a bipartite graph, and I'm wondering what the best, or rather easiest, way of creating such a data structure in javascript is?

I haven't been able to find any good explanations online, so if someone could either help me themselves or point me in the right way that would be great.

Answer 1

The easiest

The easiest one would be probably the most most obvious one

You can create 2 list where each list represents a partition in a bipartite graph. Each element in that list represents a vertex in the graph.

And you create a list of edges where each element is stored like a pair (p1, p2) where p1 is an edge index from the first array, and p2 is an edge from the second array.

For example to represent the above graph you would write

var partition1 = ['a', 'b', 'c', 'd', 'e'];
var partition2 = ['f', 'g', 'h', 'i', 'j'];

var edges      = [ [1,2], [3, 0], [1, 1] ];

This is a modified version of an Adjacency List graph representation data structure.

Some simple algorithms with this representation

function addEdge( vertexFrom1, vertexFrom2 ) {
    edges.push( [vertexFrom1, vertexFrom2] );
}

function connected( vertexFrom1, vertexFrom2 ) {
    for( var i =0, len=edges.length; i < len; i++ ) {
        if( edges[i][0] === vertexFrom1 && edges[i][1] === vertexFrom2 ) {
            return true;    
        }
    }
    
    return false;
}

As you can see adding or removing an edge is very easy, but checking if two vertices are connected is slow.

Maybe a better approach

If you want to achieve faster connection checking, you could do something similar to this.

Instead of using a pair of vertex indexes you could store only the outgoing connections from the first partition, making use of the fact that bipartite graphs can't have connections inside of a partition.

So to represent the above graph this way, you would write:

var partition1 = ['a', 'b', 'c', 'd', 'e'];
var partition2 = ['f', 'g', 'h', 'i', 'j'];

var edges      = [ [], [2,4], [], [0], [] ];

Which would make the connection check faster, but would require more memory to store the edges.