using System; using System.IO; using System.Collections.Generic; using System.Text; namespace Test_30_1_2008 { class Node { public Dictionary Edge = new Dictionary(); public int Component = -1; public int ComponentSize; public int InDegree = 0; } class Graph : IComparer { Dictionary Node = new Dictionary(); 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 nodes = new List(Node.Keys); Console.Error.WriteLine("Sorting..."); nodes.Sort(this); Console.Error.WriteLine("Determining column widths..."); Dictionary widths = new Dictionary(); foreach (string node in Node.Keys) widths[node] = node.Length; foreach(Node node in Node.Values) { foreach(KeyValuePair 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 queue = new Queue(); 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 sizes = new List(); 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: "); 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); } } } }