Git
Ранее уже был пример для поиска цикла в орграфе, теперь поиск цикла во взвешенном орграфе. Отличие здесь в том, что мы перебираем ребра и берем вершину To(). В остальном класс точно такой же. При обнаружении цикла, он заносится в стэк, для последующей возможной трассировки, работы с ним.
Класс поиска циклов через ребра
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class EdgeWeightedDirectedCycle { private bool[] marked; // marked[v] = has vertex v been marked? private DirectedEdge[] edgeTo; // edgeTo[v] = previous edge on path to v private bool[] onStack; // onStack[v] = is vertex on the stack? private Stack<DirectedEdge> cycle; // directed cycle (or null if no such cycle) public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) { marked = new bool[G.V()]; onStack = new bool[G.V()]; edgeTo = new DirectedEdge[G.V()]; for (int v = 0; v < G.GetVertices(); v++) if (!marked[v]) Dfs(G, v); } // check that algorithm computes either the topological order or finds a directed cycle private void Dfs(EdgeWeightedDigraph G, int v) { onStack[v] = true; marked[v] = true; foreach(DirectedEdge e in G.GetAdj(v)) { int w = e.To(); // short circuit if directed cycle found if (cycle != null) return; // found new vertex, so recur else if (!marked[w]) { edgeTo[w] = e; Dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<DirectedEdge>(); DirectedEdge f = e; while (f.From() != w) { cycle.Push(f); f = edgeTo[f.From()]; } cycle.Push(f); return; } } onStack[v] = false; } public bool HasCycle() { return cycle != null; } public IEnumerable<DirectedEdge> GetCycle() { return cycle; } } } |
Класс поиска циклов через вершины
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class Cycle { private bool[] marked; private int[] edgeTo; private bool[] onStack; private Stack<int> cycle; public Cycle(EdgeWeightedDigraph G) { marked = new bool[G.GetVertices()]; onStack = new bool[G.GetVertices()]; edgeTo = new int[G.GetVertices()]; for (int v = 0; v < G.GetVertices(); v++) if (!marked[v] && cycle == null) Dfs(G, v); } private void Dfs(EdgeWeightedDigraph G, int v) // v is start vertex here { onStack[v] = true; marked[v] = true; foreach (DirectedEdge e in G.GetAdj(v)) { int w = e.To(); // short circuit if directed cycle found if (cycle != null) return; // found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; Dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<int>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.Push(x); } cycle.Push(w); cycle.Push(v); // Debug.Assert(Check()); } } onStack[v] = false; } public bool IsCycle() { return cycle != null; } // --getCycle public Stack<int> GetCycle() { return cycle; } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
8 13 5 4 0,35 4 7 0,37 5 7 0,28 5 1 0,32 4 0 0,38 0 2 0,26 3 7 0,39 1 3 0,29 7 2 0,34 6 2 0,40 3 6 0,52 6 0 0,58 6 4 0,93 |
Циклический граф
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
8 15 4 5 0,35 5 4 0,35 4 7 0,37 5 7 0,28 7 5 0,28 5 1 0,32 0 4 0,38 0 2 0,26 7 3 0,39 1 3 0,29 2 7 0,34 6 2 0,40 3 6 0,52 6 0 0,58 6 4 0,93 |
Проверка в консоли
|
1 2 3 4 5 6 7 8 |
EdgeWeightedDigraph G1 = new EdgeWeightedDigraph("tinyEWD.txt"); EdgeWeightedDigraph G2 = new EdgeWeightedDigraph("tinyEWDAG.txt"); // Acyclic WOrGraph Cycle c1 = new Cycle(G1); Cycle c2 = new Cycle(G2); if (c1.IsCycle()) Console.WriteLine("Cycle in tinyEWD yes"); else Console.WriteLine("Cycle in tinyEWD no"); if (c2.IsCycle()) Console.WriteLine("Cycle in tinyEWDAG yes"); else Console.WriteLine("Cycle in tinyEWDAG no"); |