abstractgraph.cs

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

namespace Opus6
{
    using System;
    using System.Collections;
    using System.Text;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: AbstractGraph.cs,v 1.11 2001/11/04 20:49:34 brpreiss Exp $")]
    public abstract class AbstractGraph : AbstractContainer, Graph, Container, IComparable, IEnumerable
    {
        public AbstractGraph(int size)
        {
            this.vertex = new Vertex[size];
        }

        public override void Accept(Visitor visitor)
        {
            for (int num1 = 0; num1 < this.numberOfVertices; num1++)
            {
                if (visitor.IsDone)
                {
                    return;
                }
                visitor.Visit(this.vertex[num1]);
            }
        }

        protected abstract void AddEdge(Edge edge);
        public virtual void AddEdge(int v, int w)
        {
            this.AddEdge(v, w, null);
        }

        public virtual void AddEdge(int v, int w, object weight)
        {
            this.AddEdge(new GraphEdge(this, v, w, weight));
        }

        protected virtual void AddVertex(Vertex v)
        {
            if (this.numberOfVertices == this.vertex.Length)
            {
                throw new ContainerFullException();
            }
            if (v.Number != this.numberOfVertices)
            {
                throw new ArgumentException("invalid vertex number");
            }
            this.vertex[this.numberOfVertices] = v;
            this.numberOfVertices++;
        }

        public virtual void AddVertex(int v)
        {
            this.AddVertex(v, null);
        }

        public virtual void AddVertex(int v, object weight)
        {
            this.AddVertex(new GraphVertex(this, v, weight));
        }

        public void BreadthFirstTraversal(Visitor visitor, int start)
        {
            bool[] flagArray1 = new bool[this.numberOfVertices];
            for (int num1 = 0; num1 < this.numberOfVertices; num1++)
            {
                flagArray1[num1] = false;
            }
            Opus6.Queue queue1 = new QueueAsLinkedList();
            queue1.Enqueue(this.vertex[start]);
            flagArray1[start] = true;
            while (!queue1.IsEmpty && !visitor.IsDone)
            {
                Vertex vertex1 = (Vertex) queue1.Dequeue();
                visitor.Visit(vertex1);
                foreach (Vertex vertex2 in vertex1.Successors)
                {
                    if (!flagArray1[vertex2.Number])
                    {
                        queue1.Enqueue(vertex2);
                        flagArray1[vertex2.Number] = true;
                    }
                }
            }
        }

        public virtual void DepthFirstTraversal(PrePostVisitor visitor, int start)
        {
            bool[] flagArray1 = new bool[this.numberOfVertices];
            for (int num1 = 0; num1 < this.numberOfVertices; num1++)
            {
                flagArray1[num1] = false;
            }
            this.DepthFirstTraversal(visitor, this.vertex[start], flagArray1);
        }

        protected virtual void DepthFirstTraversal(PrePostVisitor visitor, Vertex v, bool[] visited)
        {
            if (!visitor.IsDone)
            {
                visitor.PreVisit(v);
                visited[v.Number] = true;
                foreach (Vertex vertex1 in v.Successors)
                {
                    if (!visited[vertex1.Number])
                    {
                        this.DepthFirstTraversal(visitor, vertex1, visited);
                    }
                }
                visitor.PostVisit(v);
            }
        }

        public abstract Edge GetEdge(int v, int w);
        protected abstract IEnumerable GetEmanatingEdges(int v);
        public override IEnumerator GetEnumerator()
        {
            return this.Vertices.GetEnumerator();
        }

        protected abstract IEnumerable GetIncidentEdges(int v);
        public Vertex GetVertex(int v)
        {
            Bounds.Check(v, 0, this.numberOfVertices);
            return this.vertex[v];
        }

        public abstract bool IsEdge(int v, int w);
        public override void Purge()
        {
            for (int num1 = 0; num1 < this.numberOfVertices; num1++)
            {
                this.vertex[num1] = null;
            }
            this.numberOfVertices = 0;
            this.numberOfEdges = 0;
        }

        public static void TestDigraph(Digraph g)
        {
            AbstractGraph.TestGraph(g);
            Opus6.AbstractGraph.PrintingVisitor visitor1 = new Opus6.AbstractGraph.PrintingVisitor();
            Opus6.Console.WriteLine("TopologicalOrderTraversal");
            g.TopologicalOrderTraversal(visitor1);
            visitor1.Finish();
            Opus6.Console.WriteLine("IsCyclic returns " + g.IsCyclic);
            Opus6.Console.WriteLine("IsStronglyConnected returns " + g.IsStronglyConnected);
        }

        public static void TestGraph(Graph g)
        {
            g.AddVertex(0);
            g.AddVertex(1);
            g.AddVertex(2);
            g.AddEdge(0, 1);
            g.AddEdge(0, 2);
            g.AddEdge(1, 2);
            Opus6.Console.WriteLine(g);
            Opus6.Console.WriteLine("IsDirected returns " + g.IsDirected);
            Opus6.Console.WriteLine("Using Vertex Enumeration");
            foreach (Vertex vertex1 in g.Vertices)
            {
                Opus6.Console.WriteLine(vertex1);
            }
            Opus6.Console.WriteLine("Using Edge Enumeration");
            foreach (Edge edge1 in g.Edges)
            {
                Opus6.Console.WriteLine(edge1);
            }
            Opus6.AbstractGraph.PrintingVisitor visitor1 = new Opus6.AbstractGraph.PrintingVisitor();
            Opus6.Console.WriteLine("DepthFirstTraversal");
            g.DepthFirstTraversal(new PreOrder(visitor1), 0);
            visitor1.Finish();
            Opus6.Console.WriteLine("BreadthFirstTraversal");
            g.BreadthFirstTraversal(visitor1, 0);
            visitor1.Finish();
            Opus6.Console.WriteLine("IsConnected returns " + g.IsConnected);
        }

        public static void TestWeightedDigraph(Digraph g)
        {
            AbstractGraph.TestWeightedGraph(g);
            Opus6.Console.WriteLine("Dijkstra's Algorithm");
            Graph graph1 = Algorithms.DijkstrasAlgorithm(g, 0);
            Opus6.Console.WriteLine(graph1);
            Opus6.Console.WriteLine("Floyd's Algorithm");
            graph1 = Algorithms.FloydsAlgorithm(g);
            Opus6.Console.WriteLine(graph1);
        }

        public static void TestWeightedGraph(Graph g)
        {
            g.AddVertex(0);
            g.AddVertex(1);
            g.AddVertex(2);
            g.AddEdge(0, 1, 3);
            g.AddEdge(0, 2, 1);
            g.AddEdge(1, 2, 4);
            Opus6.Console.WriteLine(g);
            Opus6.Console.WriteLine("Using Vertex Enumeration");
            foreach (Vertex vertex1 in g.Vertices)
            {
                Opus6.Console.WriteLine(vertex1);
            }
            Opus6.Console.WriteLine("Using Edge Enumeration");
            foreach (Edge edge1 in g.Edges)
            {
                Opus6.Console.WriteLine(edge1);
            }
            Opus6.Console.WriteLine("Prim's Algorithm");
            Graph graph1 = Algorithms.PrimsAlgorithm(g, 0);
            Opus6.Console.WriteLine(graph1);
            Opus6.Console.WriteLine("Kruskal's Algorithm");
            graph1 = Algorithms.KruskalsAlgorithm(g);
            Opus6.Console.WriteLine(graph1);
        }

        public void TopologicalOrderTraversal(Visitor visitor)
        {
            int num3;
            int[] numArray1 = new int[this.numberOfVertices];
            for (int num1 = 0; num1 < this.numberOfVertices; num1++)
            {
                numArray1[num1] = 0;
            }
            foreach (Edge edge1 in this.Edges)
            {
                Vertex vertex1 = edge1.V1;
                numArray1[num3 = vertex1.Number] = numArray1[num3] + 1;
            }
            Opus6.Queue queue1 = new QueueAsLinkedList();
            for (int num2 = 0; num2 < this.numberOfVertices; num2++)
            {
                if (numArray1[num2] == 0)
                {
                    queue1.Enqueue(this.vertex[num2]);
                }
            }
            while (!queue1.IsEmpty && !visitor.IsDone)
            {
                Vertex vertex2 = (Vertex) queue1.Dequeue();
                visitor.Visit(vertex2);
                foreach (Vertex vertex3 in vertex2.Successors)
                {
                    int[] numArray2;
                    if (((numArray2 = numArray1)[num3 = vertex3.Number] = numArray2[num3] - 1) == 0)
                    {
                        queue1.Enqueue(vertex3);
                    }
                }
            }
        }

        public override string ToString()
        {
            Opus6.AbstractGraph.ToStringVisitor visitor1 = new Opus6.AbstractGraph.ToStringVisitor();
            this.Accept(visitor1);
            return string.Concat(new object[] { base.GetType().FullName, " {\r\n", visitor1, "}" });
        }


        public abstract IEnumerable Edges { get; }

        public bool IsConnected
        {
            get
            {
                CountingVisitor visitor1 = new CountingVisitor();
                this.DepthFirstTraversal(new PreOrder(visitor1), 0);
                return (visitor1.Count == this.numberOfVertices);
            }
        }

        public bool IsCyclic
        {
            get
            {
                CountingVisitor visitor1 = new CountingVisitor();
                this.TopologicalOrderTraversal(visitor1);
                return (visitor1.Count != this.numberOfVertices);
            }
        }

        public bool IsDirected
        {
            get
            {
                return (this is Digraph);
            }
        }

        public bool IsStronglyConnected
        {
            get
            {
                for (int num1 = 0; num1 < this.numberOfVertices; num1++)
                {
                    CountingVisitor visitor1 = new CountingVisitor();
                    this.DepthFirstTraversal(new PreOrder(visitor1), num1);
                    if (visitor1.Count != this.numberOfVertices)
                    {
                        return false;
                    }
                }
                return true;
            }
        }

        public int NumberOfEdges
        {
            get
            {
                return this.numberOfEdges;
            }
        }

        public int NumberOfVertices
        {
            get
            {
                return this.numberOfVertices;
            }
        }

        public virtual IEnumerable Vertices
        {
            get
            {
                return new Enumerable(new VertexEnumerator(this));
            }
        }


        protected int numberOfEdges;
        protected int numberOfVertices;
        protected Vertex[] vertex;


        protected class CountingVisitor : AbstractVisitor
        {
            public CountingVisitor()
            {
                this.count = 0;
            }

            public override void Visit(object obj)
            {
                this.count++;
            }


            public int Count
            {
                get
                {