Strongly-connected components in digraph with edge labels

Discuss interdimensional programming, Java applets and so forth.

Strongly-connected components in digraph with edge labels

Postby quickfur » Sat Nov 12, 2011 8:00 pm

Alright, here's a question for the programming geniuses among you:

I have a digraph (directed graph) whose edges have color (you can think of it as an integer label). I want to compute a sequence S of edge colors, such that the number of strongly-connected components in the graph under edge colors S[0...i], for each i, forms the longest and slowest strictly-decreasing sequence.

For example, suppose the graph has black, red, and blue edges. Suppose we pick the sequence of colors [black, red, blue]. Then we compute the number of strongly-connected components firstly under black edges (say we get 50 SCCs), then under both black and red edges (say we get 40 SCCs), and then under black, red, and blue edges (say we get 20 SCCs). I want to find the sequences of colors such that the reduction in the number of SCCs in each step is the smallest possible.

What's the most efficient algorithm for computing this sequence?
quickfur
Pentonian
 
Posts: 2483
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Strongly-connected components in digraph with edge label

Postby quickfur » Sat Nov 12, 2011 8:04 pm

Another example: suppose the graph has black, red, green, and blue edges. Suppose we start with black edges, and find 50 SCCs. Suppose adding red edges doesn't reduce the number of SCCs. Then I want to exclude red from the sequence of colors. Suppose further that the number of SCCs under black and green edges is 40, and the number of SCCs under black and blue edges is 45. Then blue should come before green in the sequence.
quickfur
Pentonian
 
Posts: 2483
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Strongly-connected components in digraph with edge label

Postby Mrrl » Thu Nov 17, 2011 12:50 am

Something is strange here. Let we have nodes 1,2,3; red edges (1,2) and (2,3) and blue edges (3,2) and (2,1). In this case we can't start our sequence because if we take only red or only blue edges, we have three components (same as in graph with no edges), but when we take both red and blue edges, result is one component. And the answer is "NO". Is it really what you want?
If the first step is possible (i.e. we don't care that number of components with one color is the same as number of nodes), then the example is: "red: (1,2), blue: (2,3), black: (3,1)". Here we can't make the second step.
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Strongly-connected components in digraph with edge label

Postby quickfur » Thu Nov 17, 2011 6:26 am

Well for the first step it's OK to have the number of SCCs equal to the number of nodes. (This is extremely rare for the type of digraphs I'm dealing with, but it does happen for very small graphs, so it's permissible.)

You're right about the second step, though... I guess i made a mistake in my definitions. What I wanted to exclude was edge colors that don't add anything more to the SCC graph. For your examples, I would have to allow colors that add edges to the SCC graph even if they don't reduce the number of SCCs. The bottom line is that I want the chosen color to increase reachability of the SCCs. In the ideal case it will cause SCCs to merge, but i guess it's OK if it just makes the SCC graph more connected.
quickfur
Pentonian
 
Posts: 2483
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest