Finding specifig edges in a graph

Question

I have an undirected graph which has some amount of nodes and edges.

Each of the nodes is of certain color and each of the edges is of certain type, determined by the color of nodes it connects to :

An edge connecting a red and blue node is of type red-blue.
Since the graph is undirected: red-blue == blue-red.

I am tasked with writing the algorithm that will find all the edges that are "isolated".

An edge is isolated when there is at least a 2 edges distance between the original edge and the next edge of the same type as the original one.

What would be the best way to do this? Most likely it can be solved using breadth/depth first search, but I cannot figure out a way to connect them to this specific problem

Is an edge isolated if its 2 vertex do not have another edge of same color or also those neighbors cant have edges of that color? — juvian
@juvian The latter. The neighbours should also not have an edge of the same type - The next edge of the same colour should be at least 2 edges away from the original one. — janvr
do you have any amount of nodes/edges constraints? Also, do you have a complexity you are aiming for? — juvian
@juvian Amount of nodes is <10^4 and edges <10^5. I'm not sure abou time limit, but usually its ~2 seconds — janvr
@janvr can you also update the post with an input data and required output data, that will also help me to think for an algorithm. — zenwraight

juvian juvian · Accepted Answer · 2018-04-26T17:44:38

I´m pretty sure this would work, not sure about complexity

For each node n:
    For each edge (n, n2) e:
        n.colors[edgeColor(e)] += 1
For each node n:
    n.colors2 = n.colors.copy()
    For each edge (n, n2) e:
        n.colors2 = mergeSum(n.colors2, n2.colors)
For each edge (n, n2) e:
   if n.colors2[edgeColor(e)] == 2 and n2.colors2[edgeColor(e)] == 2:
       isolated edge

Finding specifig edges in a graph

1 Answers