using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
namespace Test_30_1_2008
{
class Node
{
public Dictionary<string, int> Edge = new Dictionary<string, int>();
public int Component = -1;
public int ComponentSize;
public int InDegree = 0;
}
class Graph : IComparer<string>
{
Dictionary<string, Node> Node = new Dictionary<string, Node>();
public Graph(StreamReader sin)
{
Console.Error.WriteLine("Reading from stream...");
string line = sin.ReadLine();
while (line != null)
{
line = line.Trim();
if (line != "" && !line.StartsWith("#"))
{
int sep = line.IndexOf(':');
if (sep == -1)
AddNode(line);
else
{
string from = line.Substring(0, sep);
foreach (string untrimmedto in line.Substring(sep + 1).Split(';'))
{
string to = untrimmedto.Trim();
if (to != "")
{
sep = to.IndexOf(',');
AddEdge(from, to.Substring(0, sep), int.Parse(to.Substring(sep + 1)));
}
}
}
}
line = sin.ReadLine();
}
}
void AddNode(string node)
{
if (!Node.ContainsKey(node))
Node[node] = new Node();
}
void AddEdge(string from, string to, int weight)
{
if (!Node.ContainsKey(from))
Node[from] = new Node();
if (!Node.ContainsKey(to))
Node[to] = new Node();
Node[from].Edge[to] = weight;
Node[to].InDegree += weight;
if (!Node[to].Edge.ContainsKey(from))
Node[to].Edge[from] = -1;
}
static void Center(StreamWriter sout, string str, int width)
{
width = width - str.Length;
sout.Write("".PadLeft(width / 2));
sout.Write(str);
sout.Write("".PadLeft((width + 1) / 2));
}
public int Compare(string name1, string name2)
{
Node node1 = Node[name1];
Node node2 = Node[name2];
int ret;
ret = node1.ComponentSize - node2.ComponentSize;
if (ret == 0)
{
ret = node1.Component - node2.Component;
if (ret == 0)
{
ret = node1.InDegree - node2.InDegree;
if (ret == 0)
{
return string.Compare(name1, name2);
}
}
}
return ret;
}
public void Write(StreamWriter sout)
{
List<string> nodes = new List<string>(Node.Keys);
Console.Error.WriteLine("Sorting...");
nodes.Sort(this);
Console.Error.WriteLine("Determining column widths...");
Dictionary<string, int> widths = new Dictionary<string,int>();
foreach (string node in Node.Keys)
widths[node] = node.Length;
foreach(Node node in Node.Values)
{
foreach(KeyValuePair<string, int> to in node.Edge)
{
if(to.Value != -1)
{
int width = to.Value.ToString().Length;
if(widths[to.Key] < width)
widths[to.Key] = width;
}
}
}
int max = 0;
foreach (string node in nodes)
if (node.Length > max)
max = node.Length;
Console.Error.WriteLine("Writing to stream...");
sout.Write("".PadLeft(max));
foreach (string node in nodes)
{
sout.Write(' ');
Center(sout, node, widths[node]);
}
sout.Write(Environment.NewLine);
foreach (string row in nodes)
{
sout.Write(row.PadRight(max));
foreach (string col in nodes)
{
sout.Write(' ');
if (Node[row].Edge.ContainsKey(col) && Node[row].Edge[col] != -1)
Center(sout, Node[row].Edge[col].ToString(), widths[col]);
else
Center(sout, "-", widths[col]);
}
sout.Write(Environment.NewLine);
}
sout.Flush();
}
int FindComponent(Node node, int id)
{
Queue<Node> queue = new Queue<Node>();
int size = 0;
queue.Enqueue(node);
while (queue.Count > 0)
{
node = queue.Dequeue();
size++;
foreach (string toname in node.Edge.Keys)
{
Node tonode = Node[toname];
if (tonode.Component == -1)
{
tonode.Component = id;
queue.Enqueue(tonode);
}
}
}
return size;
}
public void FindComponents()
{
Console.Error.WriteLine("Detecting components...");
int id = 0;
List<int> sizes = new List<int>();
foreach (Node node in Node.Values)
{
if (node.Component == -1)
sizes.Add(FindComponent(node, id++));
node.ComponentSize = sizes[node.Component];
}
}
}
class Program
{
static void Main(string[] args)
{
if (args.Length != 2)
{
Console.Error.WriteLine("Syntax: <infile> <outfile>");
return;
}
Graph g = null;
try
{
using (FileStream fin = new FileStream(args[0], FileMode.Open))
{
g = new Graph(new StreamReader(fin));
}
}
catch (Exception e)
{
Console.Error.WriteLine(e.Message);
return;
}
g.FindComponents();
try
{
using (FileStream fout = new FileStream(args[1], FileMode.Create))
{
g.Write(new StreamWriter(fout));
}
}
catch (Exception e)
{
Console.Error.WriteLine(e.Message);
}
}
}
}