001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.graphs.base.compact; 018 019import java.util.ArrayList; 020import java.util.Collection; 021import java.util.Collections; 022import java.util.List; 023 024import net.automatalib.commons.util.array.ResizingObjectArray; 025import net.automatalib.commons.util.collections.CollectionsUtil; 026import net.automatalib.graphs.abstractimpl.AbstractMutableGraph; 027import net.automatalib.graphs.concepts.NodeIDs; 028 029public abstract class AbstractCompactGraph<E extends CompactEdge<EP>,NP, EP> extends 030 AbstractMutableGraph<Integer, E, NP, EP> implements NodeIDs<Integer> { 031 032 protected int size; 033 protected final ResizingObjectArray edges; 034 035 public AbstractCompactGraph() { 036 this.size = 0; 037 this.edges = new ResizingObjectArray(); 038 } 039 040 public AbstractCompactGraph(int initialCapacity) { 041 this.edges = new ResizingObjectArray(initialCapacity); 042 } 043 044 @SuppressWarnings("unchecked") 045 protected List<E> getOutEdgeList(int node) { 046 return (List<E>)edges.array[node]; 047 } 048 049 @Override 050 public Collection<Integer> getNodes() { 051 return CollectionsUtil.intRange(0, size); 052 } 053 054 @Override 055 public NodeIDs<Integer> nodeIDs() { 056 return this; 057 } 058 059 @Override 060 public Collection<E> getOutgoingEdges(Integer node) { 061 return getOutgoingEdges(node.intValue()); 062 } 063 064 public Collection<E> getOutgoingEdges(int node) { 065 List<E> edgeList = getOutEdgeList(node); 066 return Collections.unmodifiableCollection(edgeList); 067 } 068 069 @Override 070 public Integer getTarget(E edge) { 071 return Integer.valueOf(edge.getTarget()); 072 } 073 074 @Override 075 public Integer addNode(NP properties) { 076 return Integer.valueOf(addIntNode(properties)); 077 } 078 079 public int addIntNode() { 080 return addIntNode(null); 081 } 082 083 public int addIntNode(NP properties) { 084 edges.ensureCapacity(size + 1); 085 edges.array[size] = new ArrayList<CompactEdge<EP>>(); 086 int n = size++; 087 setNodeProperty(n, properties); 088 return n; 089 } 090 091 @Override 092 public E connect(Integer source, Integer target, EP properties) { 093 return connect(source.intValue(), target.intValue(), properties); 094 } 095 096 public E connect(int source, int target, EP property) { 097 E edge = createEdge(source, target, property); 098 List<E> edges = getOutEdgeList(source); 099 edge.outIndex = edges.size(); 100 edges.add(edge); 101 return edge; 102 } 103 104 public CompactEdge<EP> connect(int source, int target) { 105 return connect(source, target, null); 106 } 107 108 @Override 109 public int getNodeId(Integer node) { 110 return node.intValue(); 111 } 112 113 @Override 114 public Integer getNode(int id) { 115 return Integer.valueOf(id); 116 } 117 118 public abstract NP getNodeProperties(int node); 119 120 public abstract void setNodeProperty(int node, NP property); 121 122 123 /* (non-Javadoc) 124 * @see net.automatalib.graphs.MutableGraph#setNodeProperty(java.lang.Object, java.lang.Object) 125 */ 126 @Override 127 public void setNodeProperty(Integer node, NP property) { 128 setNodeProperty(node.intValue(), property); 129 } 130 131 /* (non-Javadoc) 132 * @see net.automatalib.graphs.MutableGraph#setEdgeProperty(java.lang.Object, java.lang.Object) 133 */ 134 @Override 135 public void setEdgeProperty(E edge, EP property) { 136 edge.setProperty(property); 137 } 138 139 /* (non-Javadoc) 140 * @see net.automatalib.graphs.UniversalIndefiniteGraph#getNodeProperties(java.lang.Object) 141 */ 142 @Override 143 public NP getNodeProperty(Integer node) { 144 return getNodeProperties(node.intValue()); 145 } 146 147 @Override 148 public EP getEdgeProperty(E edge) { 149 return edge.getProperty(); 150 } 151 152 protected abstract E createEdge(int source, int target, EP property); 153 154}