Connectivity.cs

Go to the documentation of this file.

#region License
/*This file is part of Satsuma Graph Library
Copyright © 2013 Balázs Szalkai

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

   1. The origin of this software must not be misrepresented; you must not
   claim that you wrote the original software. If you use this software
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.

   2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

   3. This notice may not be removed or altered from any source
   distribution.*/
#endregion

using System;
using System.Collections.Generic;

namespace Satsuma
{
    public sealed class ConnectedComponents
    {
        [Flags]
        public enum Flags
        {
            None = 0,
            CreateComponents = 1 << 0
        }

        public IGraph Graph { get; private set; }
        public int Count { get; private set; }
        public List<HashSet<Node>> Components { get; private set; }

        private class MyDfs : Dfs
        {
            public ConnectedComponents Parent;

            protected override void Start(out Direction direction)
            {
                direction = Direction.Undirected;
            }

            protected override bool NodeEnter(Node node, Arc arc)
            {
                if (arc == Arc.Invalid)
                {
                    Parent.Count++;
                    if (Parent.Components != null) Parent.Components.Add(new HashSet<Node> { node });
                }
                else if (Parent.Components != null) Parent.Components[Parent.Count - 1].Add(node);

                return true;
            }
        }

        public ConnectedComponents(IGraph graph, Flags flags = 0)
        {
            Graph = graph;
            if (0 != (flags & Flags.CreateComponents)) Components = new List<HashSet<Node>>();
            new MyDfs { Parent = this }.Run(graph);
        }
    }

    public sealed class Bipartition
    {
        [Flags]
        public enum Flags
        {
            None = 0,
            CreateRedNodes = 1 << 0,
            CreateBlueNodes = 1 << 1
        }

        public IGraph Graph { get; private set; }
        public bool Bipartite { get; private set; }
        public HashSet<Node> RedNodes { get; private set; }
        public HashSet<Node> BlueNodes { get; private set; }

        private class MyDfs : Dfs
        {
            public Bipartition Parent;
            private HashSet<Node> redNodes;

            protected override void Start(out Direction direction)
            {
                direction = Direction.Undirected;
                Parent.Bipartite = true;
                redNodes = Parent.RedNodes ?? new HashSet<Node>();
            }

            protected override bool NodeEnter(Node node, Arc arc)
            {
                if ((Level & 1) == 0)
                    redNodes.Add(node);
                else
                    if (Parent.BlueNodes != null) Parent.BlueNodes.Add(node);
                return true;
            }

            protected override bool BackArc(Node node, Arc arc)
            {
                Node other = Graph.Other(arc, node);
                if (redNodes.Contains(node) == redNodes.Contains(other))
                {
                    Parent.Bipartite = false;
                    if (Parent.RedNodes != null) Parent.RedNodes.Clear();
                    if (Parent.BlueNodes != null) Parent.BlueNodes.Clear();
                    return false;
                }
                return true;
            }
        }

        public Bipartition(IGraph graph, Flags flags = 0)
        {
            Graph = graph;
            if (0 != (flags & Flags.CreateRedNodes)) RedNodes = new HashSet<Node>();
            if (0 != (flags & Flags.CreateBlueNodes)) BlueNodes = new HashSet<Node>();
            new MyDfs { Parent = this }.Run(graph);
        }
    }

    public sealed class TopologicalOrder
    {
        [Flags]
        public enum Flags
        {
            None = 0,
            CreateOrder = 1 << 0 
        }

        public IGraph Graph { get; private set; }
        public bool Acyclic { get; private set; }
        public List<Node> Order { get; private set; }

        private class MyDfs : Dfs
        {
            public TopologicalOrder Parent;
            private HashSet<Node> exited;

            protected override void Start(out Direction direction)
            {
                direction = Direction.Forward;
                Parent.Acyclic = true;
                exited = new HashSet<Node>();
            }

            protected override bool NodeEnter(Node node, Arc arc)
            {
                if (arc != Arc.Invalid && Graph.IsEdge(arc))
                {
                    Parent.Acyclic = false;
                    return false;
                }
                return true;
            }

            protected override bool NodeExit(Node node, Arc arc)
            {
                if (Parent.Order != null) Parent.Order.Add(node);
                exited.Add(node);
                return true;
            }

            protected override bool BackArc(Node node, Arc arc)
            {
                Node other = Graph.Other(arc, node);
                if (!exited.Contains(other))
                {
                    Parent.Acyclic = false;
                    return false;
                }
                return true;
            }

            protected override void StopSearch()
            {
                if (Parent.Order != null)
                {
                    if (Parent.Acyclic) Parent.Order.Reverse();
                    else Parent.Order.Clear();
                }
            }
        }

        public TopologicalOrder(IGraph graph, Flags flags = 0)
        {
            Graph = graph;
            if (0 != (flags & Flags.CreateOrder)) Order = new List<Node>();
            new MyDfs { Parent = this }.Run(graph);
        }
    }

    public sealed class StrongComponents
    {
        [Flags]
        public enum Flags
        {
            None = 0,
            CreateComponents = 1 << 0
        }

        public IGraph Graph { get; private set; }
        public int Count { get; private set; }
        public List<HashSet<Node>> Components { get; private set; }

        private class ForwardDfs : Dfs
        {
            public List<Node> ReverseExitOrder;

            protected override void Start(out Direction direction)
            {
                direction = Direction.Forward;
                ReverseExitOrder = new List<Node>();
            }

            protected override bool NodeExit(Node node, Arc arc)
            {
                ReverseExitOrder.Add(node);
                return true;
            }

            protected override void StopSearch()
            {
                ReverseExitOrder.Reverse();
            }
        }

        private class BackwardDfs : Dfs
        {
            public StrongComponents Parent;

            protected override void Start(out Direction direction)
            {
                direction = Direction.Backward;
            }

            protected override bool NodeEnter(Node node, Arc arc)
            {
                if (arc == Arc.Invalid)
                {
                    Parent.Count++;
                    if (Parent.Components != null) Parent.Components.Add(new HashSet<Node> { node });
                }
                else if (Parent.Components != null) Parent.Components[Parent.Components.Count - 1].Add(node);

                return true;
            }
        }

        public StrongComponents(IGraph graph, Flags flags = 0)
        {
            Graph = graph;
            if (0 != (flags & Flags.CreateComponents)) Components = new List<HashSet<Node>>();

            var forwardDfs = new ForwardDfs();
            forwardDfs.Run(graph);
            var backwardDfs = new BackwardDfs { Parent = this };
            backwardDfs.Run(graph, forwardDfs.ReverseExitOrder);
        }
    }

    internal class LowpointDfs : Dfs
    {
        protected Dictionary<Node, int> level;
        protected Dictionary<Node, int> lowpoint;

        private void UpdateLowpoint(Node node, int newLowpoint)
        {
            if (lowpoint[node] > newLowpoint) lowpoint[node] = newLowpoint;
        }

        protected override void Start(out Direction direction)
        {
            direction = Direction.Undirected;
            level = new Dictionary<Node, int>();
            lowpoint = new Dictionary<Node, int>();
        }

        protected override bool NodeEnter(Node node, Arc arc)
        {
            level[node] = Level;
            lowpoint[node] = Level;
            return true;
        }

        protected override bool NodeExit(Node node, Arc arc)
        {
            if (arc != Arc.Invalid)
            {
                Node parent = Graph.Other(arc, node);
                UpdateLowpoint(parent, lowpoint[node]);
            }
            return true;
        }

        protected override bool BackArc(Node node, Arc arc)
        {
            Node other = Graph.Other(arc, node);
            UpdateLowpoint(node, level[other]);
            return true;
        }

        protected override void StopSearch()
        {
            level = null;
            lowpoint = null;
        }
    }

    internal class BridgeDfs : LowpointDfs
    {
        public int ComponentCount;
        public HashSet<Arc> Bridges;
        
        protected override void Start(out Direction direction)
        {
            base.Start(out direction);
            ComponentCount = 0;
            Bridges = new HashSet<Arc>();
        }

        protected override bool NodeExit(Node node, Arc arc)
        {
            if (arc == Arc.Invalid) ComponentCount++;
            else
            {
                if (lowpoint[node] == Level)
                {
                    Bridges.Add(arc);
                    ComponentCount++;
                }
            }

            return base.NodeExit(node, arc);
        }
    }

    public sealed class BiEdgeConnectedComponents
    {
        [Flags]
        public enum Flags
        {
            None = 0,
            CreateComponents = 1 << 0,
            CreateBridges = 1 << 1 
        }

        public IGraph Graph { get; private set; }
        public int Count { get; private set; }
        public List<HashSet<Node>> Components { get; private set; }
        public HashSet<Arc> Bridges { get; private set; }

        public BiEdgeConnectedComponents(IGraph graph, Flags flags = 0)
        {
            Graph = graph;
            var dfs = new BridgeDfs();
            dfs.Run(graph);

            Count = dfs.ComponentCount;
            if (0 != (flags & Flags.CreateBridges)) Bridges = dfs.Bridges;
            if (0 != (flags & Flags.CreateComponents))
            {
                Subgraph withoutBridges = new Subgraph(graph);
                foreach (var arc in dfs.Bridges) withoutBridges.Enable(arc, false);
                Components = new ConnectedComponents(withoutBridges, ConnectedComponents.Flags.CreateComponents).Components;
            }
        }
    }

    public class BiNodeConnectedComponents
    {
        [Flags]
        public enum Flags
        {
            None = 0,
            CreateComponents = 1 << 0,
            CreateCutvertices = 1 << 1
        }

        public IGraph Graph { get; private set; }
        public int Count { get; private set; }
        public List<HashSet<Node>> Components { get; private set; }
        public Dictionary<Node, int> Cutvertices { get; private set; }

        private class BlockDfs : LowpointDfs
        {
            public BiNodeConnectedComponents Parent;
            private Stack<Node> blockStack;
            private bool oneNodeComponent;

            protected override void Start(out Direction direction)
            {
                base.Start(out direction);
                if (Parent.Components != null) blockStack = new Stack<Node>();
            }

            protected override bool NodeEnter(Node node, Arc arc)
            {
                if (!base.NodeEnter(node, arc)) return false;

                if (Parent.Cutvertices != null && arc == Arc.Invalid) Parent.Cutvertices[node] = -1;
                if (Parent.Components != null) blockStack.Push(node);
                oneNodeComponent = (arc == Arc.Invalid);
                return true;
            }

            protected override bool NodeExit(Node node, Arc arc)
            {
                if (arc == Arc.Invalid)
                {
                    if (oneNodeComponent) 
                    {
                        Parent.Count++;
                        if (Parent.Components != null) Parent.Components.Add(new HashSet<Node> { node });
                    }

                    if (Parent.Cutvertices != null && Parent.Cutvertices[node] == 0) Parent.Cutvertices.Remove(node);
                    if (Parent.Components != null) blockStack.Clear();
                }
                else
                {
                    // parent is a cutvertex or root?
                    Node parent = Graph.Other(arc, node);
                    if (lowpoint[node] >= Level - 1)
                    {
                        if (Parent.Cutvertices != null)
                        {
                            int degree;
                            Parent.Cutvertices[parent] = (Parent.Cutvertices.TryGetValue(parent, out degree) ? degree : 0) + 1;
                        }

                        Parent.Count++;
                        if (Parent.Components != null)
                        {
                            HashSet<Node> block = new HashSet<Node>();
                            while (true)
                            {
                                Node n = blockStack.Pop();
                                block.Add(n);
                                if (n == node) break;
                            }
                            block.Add(parent);
                            Parent.Components.Add(block);
                        }
                    }
                }

                return base.NodeExit(node, arc);
            }
        }

        public BiNodeConnectedComponents(IGraph graph, Flags flags = 0)
        {
            Graph = graph;
            if (0 != (flags & Flags.CreateComponents)) Components = new List<HashSet<Node>>();
            if (0 != (flags & Flags.CreateCutvertices)) Cutvertices = new Dictionary<Node, int>();
            new BlockDfs { Parent = this }.Run(graph);
        }
    }

    public static class FindPathExtensions
    {
        private class PathDfs : Dfs
        {
            // input
            public Direction PathDirection;
            public Func<Node, bool> IsTarget;

            // output
            public Node StartNode;
            public List<Arc> Path;
            public Node EndNode;

            protected override void Start(out Direction direction)
            {
                direction = PathDirection;

                StartNode = Node.Invalid;
                Path = new List<Arc>();
                EndNode = Node.Invalid;
            }

            protected override bool NodeEnter(Node node, Arc arc)
            {
                if (arc == Arc.Invalid)
                    StartNode = node;
                else Path.Add(arc);

                if (IsTarget(node))
                {
                    EndNode = node;
                    return false;
                }

                return true;
            }

            protected override bool NodeExit(Node node, Arc arc)
            {
                if (arc != Arc.Invalid && EndNode == Node.Invalid)
                    Path.RemoveAt(Path.Count - 1);
                return true;
            }
        }

        public static IPath FindPath(this IGraph graph, IEnumerable<Node> source, Func<Node, bool> target,
            Dfs.Direction direction)
        {
            var dfs = new PathDfs() { PathDirection = direction, IsTarget = target };
            dfs.Run(graph, source);
            if (dfs.EndNode == Node.Invalid) return null;

            var result = new Path(graph);
            result.Begin(dfs.StartNode);
            foreach (var arc in dfs.Path) result.AddLast(arc);
            return result;
        }

        public static IPath FindPath(this IGraph graph, Node source, Node target,
            Dfs.Direction direction)
        {
            return FindPath(graph, new Node[] { source }, x => x == target, direction);
        }
    }
}