CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithmgraph-traversal
usuyus22
usuyus22

Reputation: 13

Algorithm to 'trim' a graph

I am trying to create an algorithm to calculate the total resistance for a given an undirected graph with weighted edges. The algorithm will also be given a starting node and an ending node, which will represent the terminals connected to the power supply. For example, the graph on the top with starting node 1 and ending at node 6 will represent this circuit

         (3)
          |
          |6 
     3    | 
(2)------(4)
 |        |
 |5       |1
 |        |
 |    3   |   1
(1)------(5)------(6)

As you would realize, the 6 ohm resistor doesn't really matter in this context as current wouldn't flow through it if a voltage was applied between nodes 1 and 6. So, I figured that I should first of all 'trim' this graph. Here is the explanation of this process:

Trimming a graph is basically cutting off the parts of the graph which cannot be contained in a path between the starting node and the ending node which passes over any node at most once.

   4                 4              
   |                /|
   |               / |
2--3              2--3              2--3
|  |              |  |              |  |
|  |              |  |              |  |
1--5--6           1--5--6           1--4--5

  (1)               (2)               (3)

For example, in graph (1), node 4 should be trimmed because in any path between 1 and 6, visiting node 4 means visiting node 3 at least twice as there is no path from node 4 which doesn't visit node 3 again. If this graph is trimmed, it will become graph (3). However, if graph (2) is trimmed, it won't change because all nodes can be visited on a path from 1 to 6, including node 4.

So, how can I devise an algorithm that trims a graph with given starting and ending nodes?

EDIT: So, I have learned about the maxflow / mincut problem, and it seems like this could be used for the solution of this problem. I haven't tried it yet, but I will post another edit if I can manage to do it using flows.

Upvotes: 1

Views: 1410

Answers (3)

visleck
visleck

Reputation: 331

This can be a possible solution for this:

If starting from a node (say v) if we can reach both the source and terminal nodes with no vertices in common then that node has to be considered for the calculation of the total resistance.

By this I mean, suppose one of the path from v to source is (v, a1, a2, a3, a4, ..., source) And the path from v to terminal be (v, b1, b2, b3, ..., terminal)

Then if the intersection of these gives zero elements, then the node v can not be trimmed. Otherwise it can be left out.

So we can have the following two solutions for this: 1. Do a depth-first search from each vertex and check if the paths have some common vertex or not.

  1. Find all the bridges in the graph. You can look for it here: https://en.wikipedia.org/wiki/Bridge_(graph_theory)

The way to find all the bridges in a graph is given here: https://www.geeksforgeeks.org/bridge-in-a-graph/

If after removing a bridge-edge, the source and terminal vertices are in the same connected component then all the nodes on the other side of connected component can be trimmed from the graph. For example: In the graph (1), there is only one bridge 3-4.

If we remove that we get two connected components (1,2,3,5,6) and (4). We can see that both 1 and 6 are in the same connected component, hence all other connected component nodes (here only node numbered 4) can be trimmed.

Upvotes: 0

Shuki Avraham
Shuki Avraham

Reputation: 1043

  1. Find the tree of Biconnected components.
  2. Any node that is not on the path from s to t in the tree (or part of the component that is on the path) can be removed.

The time complexity is linear.

Biconnected component: https://en.wikipedia.org/wiki/Biconnected_component

Upvotes: 1

Dialecticus
Dialecticus

Reputation: 16761

Just remove all nodes with only one edge (not counting for the two ending nodes).

But this does not account for the nodes "beyond" the ending nodes. If in your original graph we want to calculate the resistance between nodes 5 and 6 then we do not need any other node (nodes 1, 2, 3 and 4 are all irrelevant).

To remove really all nodes that are irrelevant you have to find all different paths between the two ending nodes, and remove all nodes that are not part of any of those paths.

Upvotes: 0

Related Questions