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", which can be read as "PersonA says PersonB". So reading these lines...

"A says B"
"C says B"
"D says B"
"B says D"
"E says A & C"

... produces this grouping:

{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?

Answer 1

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