Algorithm - Graph

http://www.geeksforgeeks.org/largest-subset-graph-vertices-edges-2-colors/

Given an undirected complete graph with N nodes or vertices. Edges of the graph are colored, find the largest subset of vertices with edges of 2 or more colors. We are given graph as adjacency matrix C[][] where C[i][j] is color of edge from vertex i to vertex j. Since graph is undirected, values C[i][j] of C[j][i] are same.

We define C[i][i] to be zero, although there is no such edge present. i.e. the graph does not contain self-loops.

Let’s call a vertex “bad” if all its neighbors are of the same color. Obviously, we can’t have any such bad vertex in our subset, so remove such bad vertex from the graph. This might introduce some more bad vertices, but we can keep repeating this process until we find a subset free of bad vertices. So, at last, we should remain through a graph which does not have any bad vertex means every vertex of our subset has at least two different color edges with other adjacent vertices.

// Number of vertices

const int N = 6;

 

// function to calculate max subset size

int subsetGraph(int C[][N])

{

    // set for number of vertices

    set<int> vertices;

    for (int i = 0; i < N; ++i)

        vertices.insert(i);

 

    // loop for deletion of vertex from set

    while (!vertices.empty())

    {

        // if subset has only 1 vertex return 0

        if (vertices.size() == 1)

            return 1;

 

        // for each vertex iterate and keep removing

        // a vertix while we find a vertex with all

        // edges of same color.

        bool someone_removed = false;

        for (int x : vertices)

        {

            // note down different color values

            // for each vertex

            set<int> values;

            for (int y : vertices)

                if (y != x)

                    values.insert(C[x][y]);

 

            // if only one color is found

            // erase that vertex (bad vertex)

            if (values.size() == 1)

            {

                vertices.erase(x);

                someone_removed = true;

                break;

            }

        }

 

        // If no vertex was removed in the

        // above loop.

        if (!someone_removed)

            break;

    }

 

    return (vertices.size());

}

http://www.geeksforgeeks.org/count-number-edges-undirected-graph/

Given an adjacency list representation undirected graph. Write a function to count the number of edges in the undirected graph.

Expected time complexity : O(V)

Idea is based on Handshaking Lemma. Handshaking lemma is about undirected graph. In every finite undirected graph number of vertices with odd degree is always even. The handshaking lemma is a consequence of the degree sum formula (also sometimes called the handshaking lemma)

So we traverse all vertices, compute sum of sizes of their adjacency lists, and finally returns sum/2. 

int Graph :: countEdges()

{

    int sum = 0;

    //traverse all vertex

    for (int i = 0 ; i < V ; i++)

        // add all edge that are linked to the

        // current vertex

        sum += adj[i].size();

    // The count of edge is always even because in

    // undirected graph every edge is connected

    // twice between two vertices

    return sum/2;

}