BigBaz wrote:

If we have a graph G=(N,E), where N is the set of nodes, and E is the

set of edges. If we partition N into k parts (partition 1, 2,3...k).

And this partition is given by an array, with the node number as the

index. For example, C[x]=a means node x is belongs to partition a.

We define the "Quotient graph" with respect to the above partition as:

A simple graph with no multiple edges. With the set of nodes 1 to K,

and the set of edges (i,j) such that for each each edge (u,v) in E

(the original set of edges in G), there is C[u]=i and C[v]=j.

In English, the quotient graph is a graph with all the K partition

numbers as the edges.

How can I give an algorithm to construct a Quotient Graph from G, with

running time O(size(N)+size(E)).

a) This is off-topic since it is unrelated to C++.

b) It also smells like homework.

c) When posting to a more topical group, you also might want to specify the

data structure for the graph. If the edges are described as an incidence

matrix, then the input is a size(N) x size(N) matrix and the result is a

size(K) x size(K) matrix. So input and output alone will be worse than

O(size(N)+size(E)).

d) A book on graph algorithms might be a good start.

Best

Kai-Uwe Bux