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

Answer 2

TRY THIS:--

Bipartite.java

/*************************************************************************
 *  Compilation:  javac Bipartite.java
 *  Dependencies: Graph.java 
 *
 *  Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
 *  Runs in O(E + V) time.
 *
 *
 *************************************************************************/

/**
 *  The <tt>Bipartite</tt> class represents a data type for 
 *  determining whether an undirected graph is bipartite or whether
 *  it has an odd-length cycle.
 *  The <em>isBipartite</em> operation determines whether the graph is
 *  bipartite. If so, the <em>color</em> operation determines a
 *  bipartition; if not, the <em>oddCycle</em> operation determines a
 *  cycle with an odd number of edges.
 *  <p>
 *  This implementation uses depth-first search.
 *  The constructor takes time proportional to <em>V</em> + <em>E</em>
 *  (in the worst case),
 *  where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
 *  Afterwards, the <em>isBipartite</em> and <em>color</em> operations
 *  take constant time; the <em>oddCycle</em> operation takes time proportional
 *  to the length of the cycle.
 */
public class Bipartite {
    private boolean isBipartite;   // is the graph bipartite?
    private boolean[] color;       // color[v] gives vertices on one side of bipartition
    private boolean[] marked;      // marked[v] = true if v has been visited in DFS
    private int[] edgeTo;          // edgeTo[v] = last edge on path to v
    private Stack<Integer> cycle;  // odd-length cycle

    /**
     * Determines whether an undirected graph is bipartite and finds either a
     * bipartition or an odd-length cycle.
     * @param G the graph
     */
    public Bipartite(Graph G) {
        isBipartite = true;
        color  = new boolean[G.V()];
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];

        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
        assert check(G);
    }

    private void dfs(Graph G, int v) { 
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if odd-length cycle found
            if (cycle != null) return;

            // found uncolored vertex, so recur
            if (!marked[w]) {
                edgeTo[w] = v;
                color[w] = !color[v];
                dfs(G, w);
            } 

            // if v-w create an odd-length cycle, find it
            else if (color[w] == color[v]) {
                isBipartite = false;
                cycle = new Stack<Integer>();
                cycle.push(w);  // don't need this unless you want to include start vertex twice
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
            }
        }
    }

    /**
     * Is the graph bipartite?
     * @return <tt>true</tt> if the graph is bipartite, <tt>false</tt> otherwise
     */
    public boolean isBipartite() {
        return isBipartite;
    }

    /**
     * Returns the side of the bipartite that vertex <tt>v</tt> is on.
     * param v the vertex
     * @return the side of the bipartition that vertex <tt>v</tt> is on; two vertices
     *    are in the same side of the bipartition if and only if they have the same color
     * @throws UnsupportedOperationException if this method is called when the graph
     *    is not bipartite
     */
    public boolean color(int v) {
        if (!isBipartite)
            throw new UnsupportedOperationException("Graph is not bipartite");
        return color[v];
    }

    /**
     * Returns an odd-length cycle if the graph is not bipartite, and
     * <tt>null</tt> otherwise.
     * @return an odd-length cycle (as an iterable) if the graph is not bipartite
     *    (and hence has an odd-length cycle), and <tt>null</tt> otherwise
     */
    public Iterable<Integer> oddCycle() {
        return cycle; 
    }

    private boolean check(Graph G) {
        // graph is bipartite
        if (isBipartite) {
            for (int v = 0; v < G.V(); v++) {
                for (int w : G.adj(v)) {
                    if (color[v] == color[w]) {
                        System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
                        return false;
                    }
                }
            }
        }

        // graph has an odd-length cycle
        else {
            // verify cycle
            int first = -1, last = -1;
            for (int v : oddCycle()) {
                if (first == -1) first = v;
                last = v;
            }
            if (first != last) {
                System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                return false;
            }
        }

        return true;
    }

    /**
     * Unit tests the <tt>Bipartite</tt> data type.
     */
    public static void main(String[] args) {
        // create random bipartite graph with V vertices and E edges; then add F random edges
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        int F = Integer.parseInt(args[2]);

        Graph G = new Graph(V);
        int[] vertices = new int[V];
        for (int i = 0; i < V; i++) vertices[i] = i;
        StdRandom.shuffle(vertices);
        for (int i = 0; i < E; i++) {
            int v = StdRandom.uniform(V/2);
            int w = StdRandom.uniform(V/2);
            G.addEdge(vertices[v], vertices[V/2 + w]);
        }

        // add F extra edges
        for (int i = 0; i < F; i++) {
            int v = (int) (Math.random() * V);
            int w = (int) (Math.random() * V);
            G.addEdge(v, w);
        }

        StdOut.println(G);

        Bipartite b = new Bipartite(G);
        if (b.isBipartite()) {
            StdOut.println("Graph is bipartite");
            for (int v = 0; v < G.V(); v++) {
                StdOut.println(v + ": " + b.color(v));
            }
        }
        else {
            StdOut.print("Graph has an odd-length cycle: ");
            for (int x : b.oddCycle()) {
                StdOut.print(x + " ");
            }
            StdOut.println();
        }
    }
}