failed attempts to draw graphs

CSES has several really hard graph-related tasks, for example

• New Flight Routes with directed graph (btw this task was borrowed from russian olympiad contest)
  
• Forbidden Cities with undirected graph
   

It would be a good idea to visualize those graphs. One of well-known tool to do this is Graphviz, so I wrote simple perl script to render graph from CSES plain text into their DSL. On small graphs all goes well and we can enjoy with something like

But seems that on big graphs with 200k nodes dot just can`t finish rendering and after ~2 hours of hard work met with OOM killer. Lets think how we can reduce size of graph

merging nodes with degree 2

Look at picture above. We can notice that vertex 5 has 2 edge: to v2 and v7 and can be replaced with just 1 edge between 2 & 7. This process can be repeated until no vertices with degree 2 remains. For directed graphs we can merge vertex when it has 1 in & 1 out edges

New picture (you can use option -c for my script) with merged nodes has only 19 edges vs 38 in old:

You can notice that now node 2 and 6 has single edge - nodes 1 & 8 was removed. Vertices with blue color are so-called cut-points and this lead us to

Condensation on Strongly Connected Components

For directed graphs can be done with Kosaraju's algorithm
For undirected graph we can just merge all nodes between cut-points. My script support -k option for such graph condensation:

Here for example box v4 contains vertices 4, 5, 7. And now see what happened with both -c & -k options:

Only 10 edges remained

Unfortunately this is anyway too much for graphviz - now it can draw 3 shape:

1. very long straight line from nodes and lots of edges between them (using dot)
2. black square of Malevich (using neato)
3. black ball using circo
   

So it`s time to look for another tools for graph plotting. Like

R igraph package

It has convenient method read.csv, so I add option -r to my script to produce couple of CSV files:

• nodes.csv & dedges.csv for directed graphs
• nodes.csv & edges.csv for undirected graphs

Use simple R script for graph loading - it expect to see couple of this .csv files in current directory. You can install igraph package with command
install.packages("igraph")

Again result looks like hairball :-(