Hi,
I have a graph as in attached figure. I have to extract connected nodes from graph based on edge weights. If edge weight is less than a certain threshold, we have to consider that there will be not be any connectivity between that nodes. I have attached expected subgraph with this mail. Is there any efficient algorithms available to extract these type of nodes? In this attached sub graphs, all nodes are grouped if the edge weights are above 1
Dear Manu Francis
Have a look:
1. https://stackoverflow.com/questions/20085929/extracting-connected-nodes-from-weighted-undirected-graph-based-on-the-weight-of
2. https://www.geeksforgeeks.org/shortest-path-weighted-graph-weight-edge-1-2/
3. https://www.geeksforgeeks.org/find-minimum-weight-cycle-undirected-graph/
Kind Regards
Qamar Ul Islam
If I understood correctly, as Peter Breuer said:
1. Remove all edges with weight less than trash-hold (which is O(|E|)
2. Apply some algorithm to find maximum connected components. For example,
- "Enumerating all connected maximal common subgraphs in two graphs", Ina Koch
2'. Use brute force algorithm
- for each vertex
- put vertex in the empty set
- for each vertex from the set find all adjacent vertices and put them in the set
- repeat procedure until the set doesn't change
After the procedure you will have for each vertex v the set of vertices that are connected to the vertex v including the vertex v The sets will repeat k times where k is the number of the elements in the set. That set will induce the connected component.
Alternatively you could use incidence matrix and operations on it.
I hope that this is of some help.
I posted a presentation about Eulerian paths. Take a look at it.
Presentation Topology and Structure of Directed Graphs - DNA Sequencing
Another presentation about "Seven Bridges of Königsberg" is in the making.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs