algorithms.cs

Data Structures and Algorithms with Object-Oriented Design Patterns in C# 这本书的范例代码dll自己反编译的source

namespace Opus6
{
    using System;
    using System.IO;
    using System.Runtime.InteropServices;

    [Version("$Id: Algorithms.cs,v 1.8 2001/10/28 19:50:09 brpreiss Exp $"), Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng.")]
    public class Algorithms
    {
        public static void BreadthFirstTraversal(Tree tree)
        {
            Queue queue1 = new QueueAsLinkedList();
            if (!tree.IsEmpty)
            {
                queue1.Enqueue(tree);
            }
            while (!queue1.IsEmpty)
            {
                Tree tree1 = (Tree) queue1.Dequeue();
                Opus6.Console.WriteLine(tree1.Key);
                for (int num1 = 0; num1 < tree1.Degree; num1++)
                {
                    Tree tree2 = tree1.GetSubtree(num1);
                    if (!tree2.IsEmpty)
                    {
                        queue1.Enqueue(tree2);
                    }
                }
            }
        }

        public static void Calculator(TextReader reader, TextWriter writer)
        {
            int num1;
            Stack stack1 = new StackAsLinkedList();
            while ((num1 = reader.Read()) > 0)
            {
                char ch1 = (char) ((ushort) num1);
                if (char.IsDigit(ch1))
                {
                    stack1.Push(ch1 - '0');
                }
                else
                {
                    if (ch1 == '+')
                    {
                        int num2 = (int) stack1.Pop();
                        int num3 = (int) stack1.Pop();
                        stack1.Push(num3 + num2);
                        continue;
                    }
                    if (ch1 == '*')
                    {
                        int num4 = (int) stack1.Pop();
                        int num5 = (int) stack1.Pop();
                        stack1.Push(num5 * num4);
                        continue;
                    }
                    if (ch1 == '=')
                    {
                        int num6 = (int) stack1.Pop();
                        writer.WriteLine(num6);
                    }
                }
            }
        }

        public static Digraph CriticalPathAnalysis(Digraph g)
        {
            int num1 = g.NumberOfVertices;
            int[] numArray1 = new int[num1];
            numArray1[0] = 0;
            g.TopologicalOrderTraversal(new EarliestTimeVisitor(numArray1));
            int[] numArray2 = new int[num1];
            numArray2[num1 - 1] = numArray1[num1 - 1];
            g.DepthFirstTraversal(new PostOrder(new LatestTimeVisitor(numArray2)), 0);
            Digraph digraph1 = new DigraphAsLists(num1);
            for (int num2 = 0; num2 < num1; num2++)
            {
                digraph1.AddVertex(num2);
            }
            foreach (Edge edge1 in g.Edges)
            {
                int num3 = (numArray2[edge1.V1.Number] - numArray1[edge1.V0.Number]) - ((int) edge1.Weight);
                digraph1.AddEdge(edge1.V0.Number, edge1.V1.Number, (int) edge1.Weight);
            }
            return Algorithms.DijkstrasAlgorithm(digraph1, 0);
        }

        public static Digraph DijkstrasAlgorithm(Digraph g, int s)
        {
            int num1 = g.NumberOfVertices;
            Opus6.Algorithms.Entry[] entryArray1 = new Opus6.Algorithms.Entry[num1];
            for (int num2 = 0; num2 < num1; num2++)
            {
                entryArray1[num2] = new Opus6.Algorithms.Entry(false, 0x7fffffff, 0x7fffffff);
            }
            entryArray1[s].distance = 0;
            PriorityQueue queue1 = new BinaryHeap(g.NumberOfEdges);
            queue1.Enqueue(new Association(0, g.GetVertex(s)));
            while (!queue1.IsEmpty)
            {
                Association association1 = (Association) queue1.DequeueMin();
                Vertex vertex1 = (Vertex) association1.Value;
                if (!entryArray1[vertex1.Number].known)
                {
                    entryArray1[vertex1.Number].known = true;
                    foreach (Edge edge1 in vertex1.EmanatingEdges)
                    {
                        Vertex vertex2 = edge1.MateOf(vertex1);
                        int num3 = entryArray1[vertex1.Number].distance + ((int) edge1.Weight);
                        if (entryArray1[vertex2.Number].distance > num3)
                        {
                            entryArray1[vertex2.Number].distance = num3;
                            entryArray1[vertex2.Number].predecessor = vertex1.Number;
                            queue1.Enqueue(new Association(num3, vertex2));
                        }
                    }
                }
            }
            Digraph digraph1 = new DigraphAsLists(num1);
            for (int num4 = 0; num4 < num1; num4++)
            {
                digraph1.AddVertex(num4, entryArray1[num4].distance);
            }
            for (int num5 = 0; num5 < num1; num5++)
            {
                if (num5 != s)
                {
                    digraph1.AddEdge(num5, entryArray1[num5].predecessor);
                }
            }
            return digraph1;
        }

        public static void EquivalenceClasses(TextReader reader, TextWriter writer)
        {
            string text1 = reader.ReadLine();
            int num1 = Convert.ToInt32(text1);
            Partition partition1 = new PartitionAsForest(num1);
            while ((text1 = reader.ReadLine()) != null)
            {
                string[] textArray1 = text1.Split(null);
                int num2 = Convert.ToInt32(textArray1[0]);
                int num3 = Convert.ToInt32(textArray1[1]);
                Set set1 = partition1.Find(num2);
                Set set2 = partition1.Find(num3);
                if (set1 != set2)
                {
                    partition1.Join(set1, set2);
                }
                else
                {
                    writer.WriteLine("redundant pair:{0},{1}", num2, num3);
                }
            }
            writer.WriteLine(partition1);
        }

        public static Digraph FloydsAlgorithm(Digraph g)
        {
            int num1 = g.NumberOfVertices;
            int[,] numArray1 = new int[num1, num1];
            for (int num2 = 0; num2 < num1; num2++)
            {
                for (int num3 = 0; num3 < num1; num3++)
                {
                    numArray1[num2, num3] = 0x7fffffff;
                }
            }
            foreach (Edge edge1 in g.Edges)
            {
                numArray1[edge1.V0.Number, edge1.V1.Number] = (int) edge1.Weight;
            }
            for (int num4 = 0; num4 < num1; num4++)
            {
                for (int num5 = 0; num5 < num1; num5++)
                {
                    for (int num6 = 0; num6 < num1; num6++)
                    {
                        if ((numArray1[num5, num4] != 0x7fffffff) && (numArray1[num4, num6] != 0x7fffffff))
                        {
                            int num7 = numArray1[num5, num4] + numArray1[num4, num6];
                            if (numArray1[num5, num6] > num7)
                            {
                                numArray1[num5, num6] = num7;
                            }
                        }
                    }
                }
            }
            Digraph digraph1 = new DigraphAsMatrix(num1);
            for (int num8 = 0; num8 < num1; num8++)
            {
                digraph1.AddVertex(num8);
            }
            for (int num9 = 0; num9 < num1; num9++)
            {
                for (int num10 = 0; num10 < num1; num10++)
                {
                    if (numArray1[num9, num10] != 0x7fffffff)
                    {
                        digraph1.AddEdge(num9, num10, numArray1[num9, num10]);
                    }
                }
            }
            return digraph1;
        }

        public static Graph KruskalsAlgorithm(Graph g)