Coloring nodes in the same strongly connected components

Help
1

Hi,

I have a directed graph, which I would like to color all the nodes in the same strongly connected components with the same color using some script (without any manual work, since the graph changes occasionally). There are only a few strongly connected components, so distinguishing between the colors won’t be an issue.

Can that be done with sccmap, and some other trickery (probably, gvpr)?

Thanks in advance!

2

sccmap is not too well suited to this task (output is awkward), but it seems to work in a pinch.

Here is a very lightly tested gvpr script named stronglyColored.gvpr.

/******************************************************************
 apply unique color to all nodes in a strongly-connected set

- two files
  - 1st - the output of sccmap
  - 2nd - the original file

********************************************************************/
BEGIN{
  graph_t Root;
  int     sccmapFinished, DEL[];
  string  Color[], currColor, help;

  help="future";

  ////////////////////////////////////////////////////////////////////////////
  string X2color(string KEY) {
    string ret;
    int    r1, r2, r3;
    float  H, S, V, dH=1./19.;

    if(Color[KEY]!="") {
      ret=Color[KEY];
      print("//  old color: ",ret);
    } else {
      H+=rand()+dH;
      if(H>1.)H-=1.;
      S=.477+(rand()/2.);
      V=1.-(rand()/2.5);
      ret=sprintf("%.3f %.3f %.3f", H, S, V);
      print("// new color: ",ret);
      Color[KEY]=ret;
    }
    print("//  returning color: ", ret);
    return(ret);
  }
  //////////////////////////////////////////////////////////////////////////
  srand();  // used by edge colorizing rtn
}
///// end of BEGIN //////////////////////////////////////////////////////
BEG_G{
  print("////  start: ",$.name);
  Root=$G;
  if (sccmapFinished==0)
    currColor=X2color($.name)
  }
N{
  print("//  node ",$.name, " ", Root.name);
  if (sccmapFinished==0) {
    print("//   currcolor:  ", currColor);
    Color[$.name]=currColor;
  } else {
    if(Color[$.name]!="") {
      if (hasAttr($, "style") && $.style!="")
        $.style=$.style + ", filled";
      else
        $.style="filled";
      $.fillcolor=Color[$.name];
    }
  }
}
END_G{
  if (sccmapFinished==1)
    write($G);
  if ($G.name=="scc_map")
    sccmapFinished=1;
}

A linux command sequence:

f=myFile.gv
F=${f%.*}
T=png
sccmap $f -S >j1
gvpr -f stronglyColored.gvpr  j1  $f  | dot -T$T >$F.S.$T
1 Like
3

Fantastic! Thanks @steveroush ! Here’s the final result:

microcrypt
microcrypt2604×1667 723 KB

(To avoid any confusion, the red edges were removed before I computed the strongly connected component.)