Split undirected graph by negative edges

Question

Wondering if there exists an algorithm to split an undirected connected component graph given negative edges.

Essentially the vertices provided in negative edges should be unreachable.

I guess DFS while removing negative edge should accomplish it - why do you need special algorithm? — dWinder
@AdiGuN Not sure I understand what you're trying to accomplish can you elaborate? — beaker
I have a list of edges positive and negative. I'm looking to build connected components with positive edges such that each connected component does not have any negative edges — Adi GuN
If you don't want any negative edges in the connected component(s), then, as suggested before, use only the positive edges when you run your connected component algorithm. I am unsure what part you need elaboration on. — beaker

RobertBaron RobertBaron · Accepted Answer · 2019-05-24T19:18:56

If you want the connected components of your graph that contains only positive edges, then first delete all negative edges from your graph. Then run a DFS (depth-first-search) to find all connected components.

Here is the algorithm.

Begin 
    For each edge e in graph G, if e is negative, remove e from G.

    For each vertex v in G, do:
        If v is not labeled as visited
            Let c be a new component, and add c to set C.
            Call procedure DFS(v, c) to find one component of positive edges only.
        End If
    End For

    The set C contains all the connected components consisting of positive edges only.
End

Procedure DFS(v, c)
    Add v to c, and label v as visited.
    For each edge from v to w, do
        If vertex w is not labeled as visited then
            Call DFS(G,w)
        End If
    End For
End Procedure

Split undirected graph by negative edges

1 Answers