Witam

Chciałbym zaimplementować w c# metodę Hard-Cross do liczenia sieci wodociągowych. O ile sam liczenia algorytm (http://en.wikipedia.org/wiki/Hardy_Cross_method) jest dla mnie łatwy i zrozumiały, o tyle już z jego implementacja jest gorzej. Zatrzymałem się na podzieleniu grafu na pętle. Przykładowo mając graf z wiki:

Chciałbym otrzymać dwa grafy zamknięte, z wierzchołkami: 1,2,3 oraz 2,3,4. Oczywiście rozwiązanie będzie służyło mi do wiele bardziej skomplikowanych grafów/

Jakich haseł szukać?

Korzystam z gotowego narzędzia do grafów Quickgraph (https://quickgraph.codeplex.com/), jednak ze względu na ubogą dokumentację nie doszukałem się gotowego algorytmu.

Niniejszy post umieściłem w Newbie, bo wydaje mi się, że odpowiedź jest trywialna.

1. Tworzysz minimalny graf rozpinający.
2. Każda krawędź która nie weszła do minimalnego grafu rozpinającego zamyka pętle.
3. Pozostałą część pętli można znaleźć jako najkrótszą drogę w minimalnym graf rozpinającym łączącym dwa węzły.

A co to wg ciebie jest pętla? ;]

_13th_Dragon napisał(a):

Tworzysz minimalny graf rozpinający.

1. Każda krawędź która nie weszła do minimalnego grafu rozpinającego zamyka pętle.
2. Pozostałą część pętli można znaleźć jako najkrótszą drogę w minimalnym graf rozpinającym łączącym dwa węzły.

Dzięki wielkie, o to mi chodziło. Nawet Quickgraph ma gotową metodę "Minimum Spanning Tree".

P.S. Może nieprecyzyjnie się wyraziłem, ale zgodnie z zapisem artykułu w wiki, to na co chcę podzielić graf to loop. A loop zawsze tłumaczyłem jako pętla.

Znalazłem czas na implementacje twojego sposobu. Popełniłem taki kod:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using QuickGraph;
using QuickGraph.Graphviz;
using QuickGraph.Algorithms;
using QuickGraph.Algorithms.ShortestPath;

   class GraphManager
    {
           private HydraulicElement lastVertex = null;
           public Func<Edge<HydraulicElement>, double> edgeWeights = s => 1.0;

           public BidirectionalGraph<HydraulicElement, Edge<HydraulicElement>> Graph { get; protected set; }
       
      
           public GraphManager(){
               this.Graph = new BidirectionalGraph<HydraulicElement, Edge<HydraulicElement>>();                     
           }
          
           public void AddNextElement(HydraulicElement _target)
           {
               
               this.Graph.AddVertex(_target);

               if (lastVertex != null)
                   this.AddElement(lastVertex, _target);
                          
               lastVertex = _target;

           }

           public void AddElement(HydraulicElement _target, HydraulicElement _source)
           {
               this.Graph.AddVertex(_target);
               this.Graph.AddEdge(new Edge<HydraulicElement>(_source, _target));
            
               lastVertex = _target;
           }
          
           public void ConnectElements(HydraulicElement _target, int _number)
           {
                AddElement(_target,
                           this.Graph.Vertices
                           .Where(x => x.Identify.number == _number)
                           .Select(x => x)
                           .FirstOrDefault()
                           );
           }

           public IEnumerable<IEnumerable<Edge<HydraulicElement>>> GetCycles()
           {
               List<IEnumerable<Edge<HydraulicElement>>> returnValue = new List<IEnumerable<Edge<HydraulicElement>>>();

               foreach (var z in this.Graph.Edges.Except(GetMinimumSpanningTree())) //foreach po krawędziach grafu, które nie weszły do min. drzewa rozpinającego
               {
                   var tmpUnGraph = new UndirectedBidirectionalGraph<HydraulicElement, Edge<HydraulicElement>>(this.Graph)
                                   .Edges
                                   .ToUndirectedGraph<HydraulicElement, Edge<HydraulicElement>>();
                 
                   tmpUnGraph.RemoveEdge(z); //usuwanie krawędzi bazowej cyklu z tymczasowego grafu, 
                                             //aby unikąć znalezienia skrótu pomiędzy z.Source i Z.Target

                   var tryGetPaths = tmpUnGraph.ShortestPathsDijkstra<HydraulicElement, Edge<HydraulicElement>>(edgeWeights, z.Source);
                 
                   IEnumerable<Edge<HydraulicElement>> path;

                   tryGetPaths(z.Target, out path); 
               
                   returnValue.Add(
                       path.Concat(new[] {z}) //dodanie krawędzi bazowej cyklu do znalezionej najkrótszej ścieżki
                       );                                     

                 }

               return returnValue;
               
           }

           public IEnumerable<Edge<HydraulicElement>> GetMinimumSpanningTree()
           {
               return new UndirectedBidirectionalGraph<HydraulicElement, Edge<HydraulicElement>>(this.Graph)
                          .MinimumSpanningTreePrim(edgeWeights);
           
           }

           public void CloseCycle()
           {
               if (lastVertex != null)
                   this.AddElement(lastVertex, this.Graph.Vertices.First());
           }
         
           public void CloseCycle(int _number)
           {
               if (lastVertex != null)
                   this.AddElement(lastVertex, this.Graph.Vertices
                                                   .Where(x=> x.Identify.number == _number)
                                                   .Select(x => x)
                                                   .FirstOrDefault()
                                   );
           }
          
          public void DrawGraph()
           {
               DrawGraph(this.Graph);
           }

          public void DrawGraph(IEdgeListGraph<HydraulicElement, Edge<HydraulicElement>> _g)
          {
              var graphviz = new GraphvizAlgorithm<HydraulicElement, Edge<HydraulicElement>>(_g);
              string output = graphviz.Generate(new FileDotEngine(), "graph");
          }
          
            
    }

Problem pojawia się jeżeli graf przyjmuje postać:

Klasa testowa tworząca powyższy graf i drukująca cykle:

class TestClass
    {
        public TestClass()
        {


            GraphManager gm = new GraphManager();

            gm.AddNextElement(new Valve(1));
            gm.AddNextElement(new Valve(2));
            gm.AddNextElement(new Valve(3));
            gm.AddNextElement(new Valve(4));
            gm.CloseCycle();

            gm.ConnectElements(new Hydrant(10), 2);
            gm.AddNextElement(new Hydrant(20));
            gm.CloseCycle(1);

            gm.ConnectElements(new Hydrant(20), 2);
            gm.AddNextElement(new Hydrant(30));
            gm.CloseCycle(5);

            gm.ConnectElements(new Valve(10), 1);
            gm.AddNextElement(new Hydrant(30));
            gm.CloseCycle(6);

            gm.ConnectElements(new Valve(10), 5);
            gm.AddNextElement(new Valve(20));
            gm.CloseCycle(6);                
              
                  
            foreach (var z in gm.GetCycles())
            {
                Console.WriteLine("Cycle");
                foreach (var s in z.OrderBy(x=> x.Source.Identify.number)
                                   .ThenBy(x=> x.Target.Identify.number))
                {
                    Console.WriteLine("{0} <-> {1}", s.Source.Identify.number, s.Target.Identify.number);
                }
            }

        }
    }
 

Valve i Hydrant dziedziczą po abstrakcyjnej klasie HydraulicElement.

Output powyższego:

Cycle
2 <-> 5
2 <-> 7
5 <-> 8
8 <-> 7
Cycle
1 <-> 4
2 <-> 1
3 <-> 2
4 <-> 3
Cycle
2 <-> 5
2 <-> 7
5 <-> 8
8 <-> 7
Cycle
1 <-> 6
1 <-> 9
6 <-> 10
10 <-> 9
Cycle
5 <-> 11
6 <-> 5
6 <-> 12
12 <-> 11

 

Jak widać pierwszy i trzeci cykl są takie same. Pytanie jak uzyskać tylko unikalne cykle?