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();
        }
    }
}

Answer 3

This is c# implementation but the concept can be used in Java also. I used Adjacency Matrix to represent graph. Checking if there is a cycle an odd cycle in the graph.

A Graph is called Bipartite if there exist a partition in that graph say u and v where (u union v) = Graph and (u intersection v ) = null if you consider the picture below 1,2,3,4,5,6,7 are the vertices in the graph G. lets consider the vertices on the left (1,4,5,6) as U and on the right (2,3,7) as V

Consider there is no red connection in the graph for now. You could see there is a connection from u to v and v to u as its a undirected graph. but there is no connection with in the partition. That is the concept am going to use.

Consider the graph as shown below its the same graph above, except its drawn more like a tree structure. In this case if you can see the nodes present on the alternate levels 1,3,5 can together form a partition and 2,4 can form another partition. So we could easily say the graph is BiPartite. What if there is a red edge between the elements on the same level? then the graph is not bipartite.If you are could modify the BFS algorithm we can achieve this.

Here is the code for that.

   int[,] BPGraph = new int[7,7]{
                                    {0,1,0,1,0,0,0},
                                    {1,0,1,0,1,1,0},
                                    {0,1,0,1,0,0,1},
                                    {1,0,1,0,1,1,0},
                                    {0,1,0,1,0,0,1},
                                    {0,1,0,1,0,0,1},
                                    {0,0,1,0,1,1,0}
                                };

    int[] BPArray = new int[7] { 0, 0, 0, 0, 0, 0, 0 };

    public Boolean BiPartite()
    {
        Queue<int> VertexQueue = new Queue<int>();
        int level = 0;
        int nextlevel=0;
        Boolean BPFlg = true;

        VertexQueue.Enqueue(0);

        while(VertexQueue.Count!=0)
        {
            int current = VertexQueue.Dequeue();
            level = BPArray[current];

            if (level == 0)
                level = 1;

            if (level == 2)
                nextlevel=1;
            else
                nextlevel=2;

            if(BPArray[current]==0) 
                BPArray[current] = level;

            for (int i = 0; i < 7; i++)
            {
                if (BPGraph[current, i] == 1)
                {
                    if (BPArray[i] == 0)
                    {
                        BPArray[i] = nextlevel;
                        VertexQueue.Enqueue(i);
                    }
                    else if (BPArray[i] == level)
                    {
                        BPFlg = false;
                        break;
                    }
                }
            }
            if (!BPFlg)
                break;
        }
        return BPFlg;

    }

Answer 4

1.) Choose random node. Put it in the "left" side of the bipartite graph.

2.) Choose all nodes adjacent to the node you selected in 1 and put them all at the "right" side.

3.) The remaining nodes all belong to the "left" side of the bipartite graph.

END

Answer 5

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.