I have a really nasty problem (for me) at hand and I was wishing some of you may

Question

I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance.
My problem

I have a set of elements (that I would describe as a graph) that may be of three categories:

Provider nodes
Consumer nodes
Interconnections between nodes

Each node can have one or more interconnections tied to it.

My goal is to correlate each consumer to a set of providers to whom is connected, both directly through an interconnection or indirectly through multiple hops from one consumer to the other. Indirect interconnections can't go through a provider, only a consumer.

Our current approach is to analyze this graph starting with providers, hopping through interconnections recursively until a all unvisited consumers are hit. We then take this "island" of consumers bordered by a set of producers and assign these producers to each consumer we visited.

The approach gave us the right results but at a very high cost, in terms of time spent analyzing the graph.

Do you have any suggestion for an algorithm that can come in handy to solve this problem? I would also consider alternative data structures to hold our input (right now they are a set of tuples in a relational database describing the correlation between nodes and interconnections).

Explanation / Answer

I can't tell if my answer will be applicable because the question is not precisely defined. But let me make some guesses here:

Input graphs with 2 types of vertex.

Provider node (P)
Consumer node (C)

The edges are constrained by:

(P) can connect to (C)
(C) can connect to (C)
(P) can not connect to (P) (or we just don't care if they're connected)

We say that a producer p?P can reach c??C denoted with p?c? if:

there is a path starting from p then going through customers only c1,c2,

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.