001: /*
002: * Copyright 2006-2007 Pentaho Corporation. All rights reserved.
003: * This software was developed by Pentaho Corporation and is provided under the terms
004: * of the Mozilla Public License, Version 1.1, or any later version. You may not use
005: * this file except in compliance with the license. If you need a copy of the license,
006: * please go to http://www.mozilla.org/MPL/MPL-1.1.txt.
007: *
008: * Software distributed under the Mozilla Public License is distributed on an "AS IS"
009: * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. Please refer to
010: * the license for the specific language governing your rights and limitations.
011: *
012: * Additional Contributor(s): Martin Schmid gridvision engineering GmbH
013: */
014: package org.pentaho.reportdesigner.lib.common.graph;
015:
016: import org.jetbrains.annotations.NotNull;
017:
018: import java.util.Collections;
019: import java.util.HashSet;
020: import java.util.Iterator;
021: import java.util.LinkedList;
022: import java.util.List;
023:
024: public class Graph {
025:
026: @NotNull
027: private HashSet<Edge> edges;
028: @NotNull
029: private HashSet<Vertex> vertices;
030:
031: public Graph() {
032: edges = new HashSet<Edge>();
033: vertices = new HashSet<Vertex>();
034: }
035:
036: public int getNumberOfVertices() {
037: return vertices.size();
038: }
039:
040: public int getNumberOfEdges() {
041: return edges.size();
042: }
043:
044: @NotNull
045: public Iterator<Edge> getIncidentEdges(@NotNull
046: Vertex v) {
047: return v.getIncidenceContainer().getIncidentEdgeIterator();
048: }
049:
050: @NotNull
051: public Iterator<Edge> getInIncidentEdges(@NotNull
052: Vertex v) {
053: return v.getIncidenceContainer().getInIncidentEdgeIterator();
054: }
055:
056: @NotNull
057: public Iterator<Edge> getOutIncidentEdges(@NotNull
058: Vertex v) {
059: return v.getIncidenceContainer().getOutIncidentEdgeIterator();
060: }
061:
062: @NotNull
063: public Vertex getOpposite(@NotNull
064: Vertex v, @NotNull
065: Edge edge) {
066: //noinspection ObjectEquality
067: if (edge.getFromVertex() == v) {
068: return edge.getToVertex();
069: } else {
070: return edge.getFromVertex();
071: }
072: }
073:
074: public void addVertex(@NotNull
075: Vertex vertex) {
076: vertices.add(vertex);
077: }
078:
079: public void addEdge(@NotNull
080: Edge edge) {
081: edges.add(edge);
082: }
083:
084: @NotNull
085: public Iterator<Vertex> getVertexIterator() {
086: return vertices.iterator();
087: }
088:
089: @NotNull
090: public LinkedList<Vertex> getCycles() {
091: LinkedList<Vertex> remainingVertices = new LinkedList<Vertex>(
092: vertices);
093: LinkedList<Vertex> startVertices;
094: while (!(startVertices = findStartVertices(remainingVertices))
095: .isEmpty()) {
096: for (Vertex startVertice : startVertices) {
097: Vertex vertex = startVertice;
098: vertex.detachEdges();
099: }
100: }
101: for (Edge edge1 : edges) {
102: Edge edge = edge1;
103: edge.attachToVertices();
104: }
105:
106: return remainingVertices;
107: }
108:
109: @NotNull
110: public LinkedList<LinkedList<Vertex>> topSortToSpanList() {
111: LinkedList<Vertex> remainingVertices = new LinkedList<Vertex>(
112: vertices);
113: LinkedList<LinkedList<Vertex>> topSortedList = new LinkedList<LinkedList<Vertex>>();
114: LinkedList<Vertex> startVertices;
115: while (!(startVertices = findStartVertices(remainingVertices))
116: .isEmpty()) {
117: topSortedList.add(startVertices);
118: for (Vertex startVertice : startVertices) {
119: Vertex vertex = startVertice;
120: vertex.detachEdges();
121: }
122: }
123:
124: for (Edge edge1 : edges) {
125: Edge edge = edge1;
126: edge.attachToVertices();
127: }
128:
129: return topSortedList;
130: }
131:
132: @NotNull
133: private LinkedList<Vertex> findStartVertices(@NotNull
134: LinkedList<Vertex> remainingVertices) {
135: LinkedList<Vertex> startVerticesList = new LinkedList<Vertex>();
136: for (Iterator<Vertex> iterator = remainingVertices.iterator(); iterator
137: .hasNext();) {
138: Vertex vertex = iterator.next();
139: if (vertex.getIncidenceContainer()
140: .getOutIncidentEdgeCount() == 0) {
141: startVerticesList.add(vertex);
142: iterator.remove();
143: }
144: }
145: return startVerticesList;
146: }
147:
148: @NotNull
149: public LinkedList<Graph> divideIntoSubgraphList() {
150: Graph graphCopy = new Graph();
151: HashSet<Edge> edgesCopy = new HashSet<Edge>(edges);
152: HashSet<Vertex> verticesCopy = new HashSet<Vertex>(vertices);
153: graphCopy.edges = edgesCopy;
154: graphCopy.vertices = verticesCopy;
155: return graphCopy.divide();
156: }
157:
158: @NotNull
159: private LinkedList<Graph> divide() {
160: LinkedList<Graph> graphList = new LinkedList<Graph>();
161:
162: while (vertices.iterator().hasNext()) {
163: Graph subGraph = new Graph();
164: DFS.FindAllVerticesDFS dfs = new DFS.FindAllVerticesDFS();
165: dfs.execute(this , vertices.iterator().next());
166: List<Vertex> verticesList = dfs.getVertices();
167: for (Vertex aVerticesList : verticesList) {
168: Vertex vertex = aVerticesList;
169: subGraph.addVertex(vertex);
170: for (Iterator<Edge> edgeIterator = vertex
171: .getIncidenceContainer()
172: .getIncidentEdgeIterator(); edgeIterator
173: .hasNext();) {
174: Edge edge = edgeIterator.next();
175: subGraph.addEdge(edge);
176: }
177: vertices.remove(vertex);
178: }
179:
180: graphList.add(subGraph);
181: }
182: Collections.sort(graphList, new GraphSizeComparator(false));
183: return graphList;
184: }
185:
186: }
|