Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please excuse my small knowledge of graph theory vocabulary.

I can only describe the problem with common english words. Maybe someone can point me into the right direction and/or terms to look up.

The problem came up as part of the implementation of a visual programming language. Where a vertex is a function/method and the edges transport data between the functions. Now there is the following problem:

It could be allowed to connect the output of vertex A with the type of Collection< TItem > to the input of vertex B with type TItem. And then the output of vertex B with type TItem to the input vertex C with type Collection< TItem >. This would tell the compiler that it has to wrap a foreach function around vertex B to apply the function of B to each item in the collection from A and output the new items as collection to the input of C. So the edge from A to B is a many to one connection and from B to C is one to many.

Now the actual problem is, what kind of algorithm would find a subgraph that is surrounded/isolated by one to many connections? so that the compiler would wrap a foreach function around this particular subgraph? I've treid to visualize the problem in this picture:

find subgraph

share|improve this question
    
It sounds like you're trying to distinguish between edges in your graph. Edges between blue and white vertices are "many" while edges between white vertices are "one" (and I guess there are no edges between blue vertices). Is this a correct interpretation of your problem? –  jamisans Mar 5 at 17:23
    
@jamisans, the right image is still a simplification there can be edges between the blue vertices as well. those edges would need no special 'treatment' since the data type would be 'many'... –  thalm Mar 5 at 18:59
    
Also, are the graphs arbitrary or are they trees as picture suggest? –  hbm Mar 5 at 19:05
    
@hbm, they are arbitrary, theoretically every vertex from above could be connected to each vertex below. it would not make much sense for the actual output, but it is allowed and quite common that a vertex from above is connected to more than one vertex below. –  thalm Mar 5 at 19:20
    
have a small update on this... the graph is directed. from top to bottom. so the rightmost vertex which is yellow should NOT be in the subgraph, because it comes from above... does this help or simplify the finding algorithm? –  thalm Mar 7 at 15:41

1 Answer 1

up vote 0 down vote accepted

By the way, this question has a good answer over at stackoverflow:

Find subgraphs in a directed graph which are isolated by certain properties

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.