harshaga97's blog

By harshaga97, 4 weeks ago, In English,

I have a weighted undirected graph where each node has been assigned a color (there can be multiple nodes with the same color) and the nodes having the same color are connected.

The color information is stored in an array int color[no_vertices]

I want to create a new graph where all the nodes of the same color have been merged into a single node and the merged nodes are connected using the minimum weighted edge present between two nodes in the original graph.

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by harshaga97 (previous revision, new revision, compare).

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Once you found the connected components, you can do what you want in O(V + E), where E is the number of edges and V the number of nodes. You give an ID to each connected component, and mark each node with the ID of its connected component. Then, you go through the edges and build a new adjacency list by adding the edges between the ID of the nodes of each edge. If you don't want to have repeating nodes in the adjacency list, you can use set and then go back to vectors. You are done :) each connected component is a node represented by its ID, and you have built an adjacency list to represent the graph made by the connected components. Edit: I didn't see that the graph was undirected, in this case the question makes no sense.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Since it is a weighted graph, I want the edge in the new adjacency list between 2 components to be the minimum edge connecting the 2 components in the original graph.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Assuming that what you want is to build the compressed graph where you only store the shortest edge between two linked components, you can iterate through the list of edges, and add an edge between color[x] and color[y] with z where z is the length of the edge between x and y. Now you might have added multiple edges between 2 components and you can just use a vector < pair < int, int > > to store them and after adding all of them, sort the edges by their id, find the continuous subsegments with the same id and keep only one instance of that id with the shortest edge.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

There is no such thing as a strongly connected component in an undirected graph

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by harshaga97 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Cheapest edge between two connected components in undirected graph, very funny xD. My hint is that you can not worry about it because it doesn't exist. One can get an idea that you meant directed graphs and SCCs everywhere, but then using F&U makes no sense.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Components are connected colorwise, and edges are taken from the initial graph. So the problem is to find the minimum edge connecting two vertices of some given colors,and it does make sense.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Now when the blog has been edited you can be mr smart here :D