src/main/java/org/xerial/util/graph/GraphHelper.java

   1 /*--------------------------------------------------------------------------\r
   2  *  Copyright 2008 Taro L. Saito\r
   3  *\r
   4  *  Licensed under the Apache License, Version 2.0 (the "License");\r
   5  *  you may not use this file except in compliance with the License.\r
   6  *  You may obtain a copy of the License at\r
   7  *\r
   8  *     http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  *  Unless required by applicable law or agreed to in writing, software\r
  11  *  distributed under the License is distributed on an "AS IS" BASIS,\r
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  *  See the License for the specific language governing permissions and\r
  14  *  limitations under the License.\r
  15  *--------------------------------------------------------------------------*/\r
  16 //--------------------------------------\r
  17 // XerialJ\r
  18 //\r
  19 // GraphHelper.java\r
  20 // Since: Oct 24, 2008 11:03:03 AM\r
  21 //\r
  22 // $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/GraphHelper.java $\r
  23 // $Author: leo $\r
  24 //--------------------------------------\r
  25 package org.xerial.util.graph;\r
  26 \r
  27 /**\r
  28  * A helper class to implement graph related methods\r
  29  * \r
  30  * package scope\r
  31  * \r
  32  * @author leo\r
  33  * \r
  34  */\r
  35 public class GraphHelper\r
  36 {\r
  37     /**\r
  38      * Prohibit construction\r
  39      */\r
  40     private GraphHelper()\r
  41     {};\r
  42 \r
  43     public static <NodeLabel, EdgeLabel> NodeLabel getSourceNodeLabel(Graph<NodeLabel, EdgeLabel> graph, Edge edge)\r
  44     {\r
  45         return graph.getNodeLabel(edge.getSourceNodeID());\r
  46     }\r
  47 \r
  48     public static <NodeLabel, EdgeLabel> NodeLabel getDestNodeLabel(Graph<NodeLabel, EdgeLabel> graph, Edge edge)\r
  49     {\r
  50         return graph.getNodeLabel(edge.getDestNodeID());\r
  51     }\r
  52 \r
  53     public static <NodeLabel, EdgeLabel> String toString(Graph<NodeLabel, EdgeLabel> graph, Edge edge)\r
  54     {\r
  55         return String.format("(%s,%s)", graph.getNodeLabel(edge.getSourceNodeID()).toString(), graph.getNodeLabel(\r
  56                 edge.getDestNodeID()).toString());\r
  57     }\r
  58 \r
  59     /**\r
  60      * compute the transitive closure of the input graph\r
  61      * \r
  62      * @param <NodeLabel>\r
  63      * @param <EdgeLabel>\r
  64      * @param original\r
  65      * @return\r
  66      */\r
  67     public static <NodeLabel, EdgeLabel> Graph<NodeLabel, EdgeLabel> transitiveClosure(Graph<NodeLabel, EdgeLabel> input)\r
  68     {\r
  69         Graph<NodeLabel, EdgeLabel> graph = AdjacencyList.copy(input);\r
  70 \r
  71         int numChange = 0;\r
  72         do\r
  73         {\r
  74             numChange = 0;\r
  75             for (NodeLabel from : graph.getNodeLabelSet())\r
  76             {\r
  77                 for (NodeLabel to : graph.getNodeLabelSet())\r
  78                 {\r
  79                     if (graph.hasEdge(from, to))\r
  80                         continue;\r
  81 \r
  82                     int destNodeID = graph.getNodeID(to);\r
  83                     for (Edge startPoint : graph.getOutEdgeSet(from))\r
  84                     {\r
  85                         int intermediateNodeID = startPoint.getDestNodeID();\r
  86 \r
  87                         if (graph.hasEdge(new Edge(intermediateNodeID, destNodeID)))\r
  88                         {\r
  89                             graph.addEdge(from, to);\r
  90                             ++numChange;\r
  91                             break;\r
  92                         }\r
  93                     }\r
  94                 }\r
  95             }\r
  96         }\r
  97         while (numChange > 0);\r
  98 \r
  99         return graph;\r
 100     }\r
 101 \r
 102 }\r