1 /* 2 * Copyright 2014 Google Inc. All rights reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef FRUIT_META_GRAPH_H 18 #define FRUIT_META_GRAPH_H 19 20 #include <fruit/impl/meta/immutable_map.h> 21 #include <fruit/impl/meta/map.h> 22 #include <fruit/impl/meta/set.h> 23 #include <fruit/impl/meta/triplet.h> 24 25 namespace fruit { 26 namespace impl { 27 namespace meta { 28 29 // A Graph is a Map from each node to a set containing its neighbors. 30 31 using GetGraphNodes = GetImmutableMapKeys; 32 33 using GraphFindNeighbors = FindInImmutableMap; 34 35 using GraphContainsNode = ImmutableMapContainsKey; 36 37 // Returns a loop in the given graph as a Vector<N1, ..., Nk> such that the graph contains a loop 38 // N1->...->Nk->N1, or None if there are no loops. 39 struct GraphFindLoop { 40 template <typename G> 41 struct apply { 42 using ImmutableG = VectorToImmutableMap(G); 43 44 // DfsVisit(VisitedSet, VisitingSet, Node) does a DFS visit starting at Node and returns a 45 // Triplet<NewVisitedSet, Loop, IsLoopComplete>, where Loop is the Vector representing the part 46 // of the loop starting at Node (if any loop was found) or Null otherwise. 47 struct DfsVisit { 48 template <typename VisitedSet, typename VisitingSet, typename Node> 49 struct apply { 50 using NewVisitingSet = AddToSetUnchecked(VisitingSet, Node); 51 52 struct VisitSingleNeighbor { 53 // CurrentResult is a Triplet<VisitedSet, Loop, IsLoopComplete> (where IsLoopComplete 54 // is only meaningful when Loop is not None). 55 template <typename CurrentResult, typename Neighbor> 56 struct apply { 57 using type = If(IsNone(typename CurrentResult::Second), 58 // Go ahead, no loop found yet. 59 DfsVisit(typename CurrentResult::First, NewVisitingSet, Neighbor), 60 // Found a loop in another neighbor of the same node, we don't need to 61 // visit this neighbor. 62 CurrentResult); 63 }; 64 }; 65 66 using NewVisitedSet = AddToSet(VisitedSet, Node); 67 using Neighbors = GraphFindNeighbors(ImmutableG, Node); 68 using Result = FoldVector(Neighbors, VisitSingleNeighbor, ConsTriplet(NewVisitedSet, None, Bool<false>)); 69 using type = If(IsNone(Neighbors), 70 // No neighbors. 71 ConsTriplet(NewVisitedSet, None, Bool<false>), 72 If(IsInSet(Node, VisitingSet), 73 // We've just found a loop, since Node is another node that we're currently 74 // visiting 75 Triplet<VisitedSet, Vector<Node>, Bool<false>>, 76 If(IsNone(GetSecond(Result)), 77 // No loop found. 78 Result, 79 // Found a loop 80 If(GetThird(Result) /* IsLoopComplete */, Result, 81 If(VectorEndsWith(GetSecond(Result) /* Loop */, Node), 82 // The loop is complete now. 83 ConsTriplet(GetFirst(Result), GetSecond(Result), Bool<true>), 84 // Loop still not complete, add the current node. 85 ConsTriplet(GetFirst(Result), PushFront(GetSecond(Result), Node), Bool<false>)))))); 86 }; 87 }; 88 89 struct VisitStartingAtNode { 90 // CurrentResult is a Pair<CurrentVisitedSet, Loop> 91 template <typename CurrentResult, typename Node> 92 struct apply { 93 using DfsResult = DfsVisit(GetFirst(CurrentResult), EmptySet, Node); 94 using type = If(IsNone(GetSecond(CurrentResult)), 95 // No loop found yet. 96 MakePair(GetFirst(DfsResult), GetSecond(DfsResult)), 97 // Found a loop, return early 98 CurrentResult); 99 }; 100 }; 101 102 using type = GetSecond(FoldVector(GetMapKeys(G), VisitStartingAtNode, Pair<EmptySet, None>)); 103 }; 104 }; 105 106 } // namespace meta 107 } // namespace impl 108 } // namespace fruit 109 110 #endif // FRUIT_META_GRAPH_H 111