How do I implement a Bipartite Graph in Java?

Question

UPDATE

Some answers so far have suggested using an adjacency list. How would an adjacency list look like in Java? ... no pointers right :)

---

I'm trying to implement a Bipartite Graph in Java to sort into 2 groups information from a file. I found this example and it actually does the job:

http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html

However, I would like to implement my own version... if you look at a previous post of mine, you'd understand why I want to do this myself.

So I have to read a file from which I can get the number of vertices easily, but the number of edges not so easily. An example line would be: PersonA PersonB. The following is a drawing what I came up with as a solution to a specific input:

The drawing is what the input REALLY means... which could be read as "A says B", "C says B", "D says B", "B says D", "E says A & C". So the groups would be {A,D,C} and {B,E}.

How would I go about implementing this bipartite graph? What is a good resource for this task? What things (algorithms) should I be considering and thinking about when creating the BipartiteGraph class... perhaps traversing/sorting algorithms?

Thanks in advance!

Answer 1

A directed graph is one in which an edge connecting nodes A and B has a direction; if there is an edge from A to B, this does not mean there is an edge from B to A. In your example, the edges have direction. (B to D would be two edges, one from B to D and one from D to B.)

One way to implement this would be in a similar way to a linked list, with nodes having references to each other as appropriate. Referring back to your example, nodeA would have a reference to nodeB, but not the reverse. nodeE would have a reference to nodeA and nodeC, and so on. You're really creating a (sort of) data structure, which has a notion of nodes and perhaps edges. There are a number of ways you could go about it.

A possible Java implementation would be having a class called AdjacencyList that has a Map<Vertex, List<Vertex>> containing a vertex and its adjacent vertices. AdjacencyList would then have the ability to perform operations on its Map.

As for algorithms and things to keep in mind, take a look at the properties of bipartite graphs on Wikipedia, particularly

• A graph is bipartite if and only if it does not contain an odd cycle. Therefore, a bipartite graph cannot contain a clique of size 3 or more.
• Every tree is bipartite.
• Cycle graphs with an even number of vertices are bipartite.

A good test would be implementing a 2-coloring algorithm to confirm that the graph is indeed bipartite. Depth first search, breadth first search are good exercises of the implementation.

Answer 2

It should be pretty straight forward to implement with an adjacency list. If it were an undirected bipartite graph I might suggest using an incidence matrix.

So you'd have an array of linked lists then, or an array of some sort of dynamically allocated list, for each node. It should make adding edges fairly natural, for instance in your example you have an edge:

Person A-> Person B

Then you'd go the array index corresponding to Person A and push back the index corresponding to Persona B:

[Person A]= Person B

Then maybe you get another edge

Persona A-> Person C

Then your index there would look like:

[Persona A]= Person B , Person C

As one last example this would be the adjacency list for your example graph:

[A] B

[B] D

[C] B

[D] B

[E] A,C

Each index has a list of the nodes reachable from that node.

" What things (algorithms) should I be considering and thinking about when creating the BipartiteGraph class... perhaps traversing/sorting algorithms?"

It really depends on what you want to do with the graph...

For Reference: Similar Question with Code on Sun Forums

adjacency-list-of-a-directed-weighted-graph