Grafos – detecção de ciclos e componentes conexas – implementação

No artigo anterior, apresentei um vídeo no qual é descrito um processo para determinar a existência de ciclos e de várias componentes conexas dum grafo, tomando como base um pequeno exemplo. No presente, pretendo apresentar uma pequena implementação na linguagem de programação que estou a utilizar no tempo corrente, C#.

Começo pelas classes auxiliares. A primeira, representa uma aresta definida pelos vértices extremos. Como queremos implementar uma funcionalidade independentemente da estrutura que escolhemos para representar os vértices, definimos as classes como genéricas. Então, para a aresta, temos

namespace CycleDetection
{
    class Edge<VertexType>
    {
        public VertexType Source
        {
            get;
            set;
        }

        public VertexType Target
        {
            get;
            set;
        }

        public override string ToString()
        {
            return string.Format("{0}->{1}", this.Source, this.Target);
        }
    }
}

Para traçarmos os vértices que vão constituir um ciclo, definimos uma nova classe que representa o nó de uma árvore. Cada nó dessa árvore tem uma referência para o respectivo pai e, caso seja a raíz, essa referência é nula. O código fica como se segue:

namespace CycleDetection
{
    class CycleGraphElement<VertexType>
    {
        private VertexType vertex;
        private List<CycleGraphElement<VertexType>> nextElements = new List<CycleGraphElement<VertexType>>();
        private CycleGraphElement<VertexType> previousElement = null;

        public VertexType Vertex
        {
            get
            {
                return this.vertex;
            }
        }

        public CycleGraphElement<VertexType> Previous
        {
            get
            {
                return this.previousElement;
            }
        }

        public CycleGraphElement(VertexType vertex)
        {
            this.vertex = vertex;
        }

        public CycleGraphElement(VertexType vertex, CycleGraphElement<VertexType> previous)
        {
            this.vertex = vertex;
            this.previousElement = previous;
        }

        public void AddNextElement(CycleGraphElement<VertexType> elementToAdd)
        {
            this.nextElements.Add(elementToAdd);
        }

        public void RemoveNextElement(CycleGraphElement<VertexType> elementToRemove)
        {
            this.nextElements.Remove(elementToRemove);
        }

        public int CountNextElementsNumber()
        {
            return this.nextElements.Count;
        }

        public IEnumerator<CycleGraphElement<VertexType>> GetNextElementsEnumerator()
        {
            return this.nextElements.GetEnumerator();
        }

        public class ElementComparer : IEqualityComparer<CycleGraphElement<VertexType>>
        {
            public bool Equals(CycleGraphElement<VertexType> x, CycleGraphElement<VertexType> y)
            {
                return x.vertex.Equals(y.vertex);
            }

            public int GetHashCode(CycleGraphElement<VertexType> obj)
            {
                return obj.vertex.GetHashCode();
            }
        }
    }
}

Definimos uma classe aninhada, ElementComparer, a qual permite comparar dois elementos deste tipo. Antes de apresentar uma implementação das funções que permitem detectar ciclos e componentes conexas, aproveito para enfatizar o facto de que seria possível construir uma árvore que contivesse todos os vértices, a qual poderia ser utilizada para traçar os ciclos. No entanto, a implementação que apresento cinge-se ao algoritmo apresentado no vídeo.

No código que se segue, a função genérica CheckForCycles permite retornar um conjunto de ciclos (apenas ciclos independentes) relativo ao grafo. Recebe a lista de todas as arestas do grafo e retorna uma lista de listas de vértices. Cada lista de vértices representa um ciclo. Durante o processo, escreve na consola qual é o número da componente conexa que está a tratar – apenas para delinear onde e como é possível detectá-las. As funções ProcessCycle e GetCyclesFromTree são auxiliares da primeira. Por fim, surge a função que permite imprimir os resultados.

static List<List<VertexType>> CheckForCycles<VertexType>(
            List<Edge<VertexType>> edgesToCheck)
        {
            if (edgesToCheck == null)
            {
                throw new Exception("Argument must not be null.");
            }
            if (edgesToCheck.Count == 0)
            {
                throw new Exception("There is no edges to process.");
            }
            List<List<VertexType>> result = new List<List<VertexType>>();
            List<Edge<VertexType>> unOrderedEdges = new List<Edge<VertexType>>();
            List<Edge<VertexType>> orderedEdges = new List<Edge<VertexType>>();
            unOrderedEdges.AddRange(edgesToCheck);
            int component = 1;
            while (unOrderedEdges.Count > 0)
            {
                Console.WriteLine("Treating component {0}...", component++);
                Queue<VertexType> vertexQueue = new Queue<VertexType>();
                vertexQueue.Enqueue(unOrderedEdges[0].Source);
                while (vertexQueue.Count > 0)
                {
                    List<Edge<VertexType>> treatedEdges = new List<Edge<VertexType>>();
                    VertexType queueVertex = vertexQueue.Dequeue();
                    var edgesWithQueueVertex = from edge in unOrderedEdges
                                               where edge.Source.Equals(queueVertex) || edge.Target.Equals(queueVertex)
                                              select edge;
                    foreach (var selectedEdge in edgesWithQueueVertex)
                    {
                        VertexType otherVertex = selectedEdge.Source.Equals(queueVertex) ?
                            selectedEdge.Target : selectedEdge.Source;
                        treatedEdges.Add(selectedEdge);
                        if (vertexQueue.Contains(otherVertex))
                        {
                            VertexType firstVertex = selectedEdge.Source.Equals(otherVertex) ?
                            selectedEdge.Target : selectedEdge.Source;
                            result.AddRange(ProcessCycle<VertexType>(firstVertex, otherVertex, orderedEdges));
                        }
                        else
                        {
                            vertexQueue.Enqueue(otherVertex);
                        }
                    }
                    orderedEdges.AddRange(treatedEdges);
                    foreach (var edge in treatedEdges)
                    {
                        unOrderedEdges.Remove(edge);
                    }
                }
            }
            return result;
        }

        static List<List<VertexType>> ProcessCycle<VertexType>(
            VertexType startVertex,
            VertexType endVertex,
            List<Edge<VertexType>> orderedEdges)
        {
            List<List<VertexType>> result = new List<List<VertexType>>();
            List<Edge<VertexType>> edges = new List<Edge<VertexType>>();
            edges.AddRange(orderedEdges);
            Queue<CycleGraphElement<VertexType>> vertexQueue = new Queue<CycleGraphElement<VertexType>>();
            CycleGraphElement<VertexType> rootElement = new CycleGraphElement<VertexType>(startVertex, null);
            vertexQueue.Enqueue(rootElement);
            while (vertexQueue.Count > 0)
            {
                CycleGraphElement<VertexType> queueVertexElement = vertexQueue.Dequeue();
                List<Edge<VertexType>> treatedEdges = new List<Edge<VertexType>>();
                var edgesWithQueueVertex = from edge in edges
                                           where edge.Source.Equals(queueVertexElement.Vertex) ||
                                           edge.Target.Equals(queueVertexElement.Vertex)
                                           select edge;
                foreach (var edge in edgesWithQueueVertex)
                {
                    VertexType otherVertex = edge.Source.Equals(queueVertexElement.Vertex) ?
                            edge.Target : edge.Source;
                    treatedEdges.Add(edge);
                    CycleGraphElement<VertexType> otherVertexElement = new CycleGraphElement<VertexType>(
                        otherVertex,
                        queueVertexElement);
                    if (!vertexQueue.Contains(otherVertexElement, new CycleGraphElement<VertexType>.ElementComparer()))
                    {
                        queueVertexElement.AddNextElement(otherVertexElement);
                        vertexQueue.Enqueue(otherVertexElement);
                    }
                }
                foreach (var edge in treatedEdges)
                {
                    edges.Remove(edge);
                }
            }
            return GetCyclesFromTree<VertexType>(rootElement, endVertex);
        }

        static List<List<VertexType>> GetCyclesFromTree<VertexType>(CycleGraphElement<VertexType> treeRootNode, VertexType endVertex)
        {
            List<List<VertexType>> result = new List<List<VertexType>>();
            Stack<VertexType> vertexStack = new Stack<VertexType>();
            vertexStack.Push(treeRootNode.Vertex);
            Stack<IEnumerator<CycleGraphElement<VertexType>>> visitingTreeStack = new Stack<IEnumerator<CycleGraphElement<VertexType>>>();
            visitingTreeStack.Push(treeRootNode.GetNextElementsEnumerator());
            while (visitingTreeStack.Count > 0)
            {
                VertexType tempVertex = vertexStack.Pop();
                if (tempVertex.Equals(endVertex))
                {
                    List<VertexType> currentBranch = new List<VertexType>();
                    currentBranch.AddRange(vertexStack);
                    currentBranch.Add(tempVertex);
                    result.Add(currentBranch);
                }
                vertexStack.Push(tempVertex);
                IEnumerator<CycleGraphElement<VertexType>> currentEnumerator = visitingTreeStack.Pop();
                if (currentEnumerator.MoveNext())
                {
                    visitingTreeStack.Push(currentEnumerator);
                    vertexStack.Push(currentEnumerator.Current.Vertex);
                    visitingTreeStack.Push(currentEnumerator.Current.GetNextElementsEnumerator());
                }
                else
                {
                    vertexStack.Pop();
                }
            }
            return result;
        }

        static void PrintCycleList<VertexType>(List<List<VertexType>> cycles, TextWriter writer)
        {
            writer.WriteLine("---------CYCLES--------------");
            foreach (var cycle in cycles)
            {
                Console.Write("[");
                if (cycle.Count > 0)
                {
                    Console.Write(cycle[0]);
                    for (int i = 1; i < cycle.Count; ++i)
                    {
                        Console.Write(", {0}", cycle[i]);
                    }
                }
                Console.WriteLine("]");
            }
            writer.WriteLine("-----------------------------");
        }
    }

As funções estão marcadas como estáticas e deverão ser colocadas na classe onde surge a função Main. Contudo, é possível declará-las numa classe independente. Podemos testá-las, recorrendo ao grafo que utilizei no vídeo para referência. Para o efeito, introduzimos o código na função Main:

        static void Main(string[] args)
        {
            List<Edge<int>> edges = new List<Edge<int>>();
            edges.Add(new Edge<int>() { Source = 1, Target = 2 });
            edges.Add(new Edge<int>() { Source = 3, Target = 4 });
            edges.Add(new Edge<int>() { Source = 1, Target = 3 });
            edges.Add(new Edge<int>() { Source = 2, Target = 4 });
            edges.Add(new Edge<int>() { Source = 2, Target = 5 });
            edges.Add(new Edge<int>() { Source = 4, Target = 6 });
            edges.Add(new Edge<int>() { Source = 2, Target = 6 });
            edges.Add(new Edge<int>() { Source = 5, Target = 6 });
            edges.Add(new Edge<int>() { Source = 6, Target = 7 });
            edges.Add(new Edge<int>() { Source = 7, Target = 8 });
            edges.Add(new Edge<int>() { Source = 3, Target = 7 });
            List<List<int>> result = CheckForCycles<int>(edges);
            PrintCycleList<int>(result, Console.Out);
}

Para ilustrar o funcionamento desta implementação com vértices de outro tipo, definimos a classe CoordVertex que consiste na representação das coordenadas de um ponto no plano.

namespace CycleDetection
{
    class CoordVertex
    {
        public double X
        {
            get;
            set;
        }

        public double Y
        {
            get;
            set;
        }

        public override string ToString()
        {
            return string.Format("({0:0.####};{1:0.####})", this.X, this.Y);
        }

        public override bool Equals(object obj)
        {
            return this.X == (obj as CoordVertex).X && this.Y == (obj as CoordVertex).Y;
        }
    }
}

Na função Main podemos inserir o código (cujas arestas representam linhas que desenham um triângulo no topo de um quadrado);

        static void Main(string[] args)
        {
List<Edge<CoordVertex>> coordEdges = new List<Edge<CoordVertex>>();
            coordEdges.Add(new Edge<CoordVertex>(){
                Source = new CoordVertex(){X = 0.0, Y = 0.0},
                Target = new CoordVertex(){X = 2.0, Y = 0.0}});
            coordEdges.Add(new Edge<CoordVertex>()
            {
                Source = new CoordVertex() { X = 2.0, Y = 0.0 },
                Target = new CoordVertex() { X = 2.0, Y = 2.0 }
            });
            coordEdges.Add(new Edge<CoordVertex>()
            {
                Source = new CoordVertex() { X = 2.0, Y = 2.0 },
                Target = new CoordVertex() { X = 0.0, Y = 2.0 }
            });
            coordEdges.Add(new Edge<CoordVertex>()
            {
                Source = new CoordVertex() { X = 0.0, Y = 2.0 },
                Target = new CoordVertex() { X = 0.0, Y = 0.0 }
            });
            coordEdges.Add(new Edge<CoordVertex>()
            {
                Source = new CoordVertex() { X = 2.0, Y = 2.0 },
                Target = new CoordVertex() { X = 1.0, Y = 3.0 }
            });
            coordEdges.Add(new Edge<CoordVertex>()
            {
                Source = new CoordVertex() { X = 0.0, Y = 2.0 },
                Target = new CoordVertex() { X = 1.0, Y = 3.0 }
            });
            List<List<CoordVertex>> result1 = CheckForCycles<CoordVertex>(coordEdges);
            PrintCycleList<CoordVertex>(result1, Console.Out);
        }

Neste último caso, o programa detecta o quadrado e o triângulo como ciclos. Existe um ciclo que envolve estes dois. Contudo, não é independente.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Computadores e Internet. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s