structures in modern computer science: graphs.
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DepthFirstDirectedPaths.class
package edu.uoc.mecm.eda.utils; public synchronized class DepthFirstDirectedPaths { private boolean[] marked; private int[] edgeTo; private final int s; public void DepthFirstDirectedPaths(Digraph, int); private void dfs(Digraph, int); public boolean hasPathTo(int); public Iterable pathTo(int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Stack$ListIterator.class
package edu.uoc.mecm.eda.utils; synchronized class Stack$ListIterator implements java.util.Iterator { private Stack$Node current; public void Stack$ListIterator(Stack, Stack$Node); public boolean hasNext(); public void remove(); public Object next(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/BreadthFirstPaths.class
package edu.uoc.mecm.eda.utils; public synchronized class BreadthFirstPaths { private static final int INFINITY = 2147483647; private boolean[] marked; private int[] edgeTo; private int[] distTo; public void BreadthFirstPaths(Graph, int); public void BreadthFirstPaths(Graph, Iterable); private void bfs(Graph, int); private void bfs(Graph, Iterable); public boolean hasPathTo(int); public int distTo(int); public Iterable pathTo(int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/IndexMinPQ$HeapIterator.class
package edu.uoc.mecm.eda.utils; synchronized class IndexMinPQ$HeapIterator implements java.util.Iterator { private IndexMinPQ copy; public void IndexMinPQ$HeapIterator(IndexMinPQ); public boolean hasNext(); public void remove(); public Integer next(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/CC.class
package edu.uoc.mecm.eda.utils; public synchronized class CC { private boolean[] marked; private int[] id; private int[] size; private int count; public void CC(Graph); private void dfs(Graph, int); public int id(int); public int size(int); public int count(); public boolean connected(int, int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/AcyclicSP.class
package edu.uoc.mecm.eda.utils; public synchronized class AcyclicSP { private double[] distTo; private DirectedEdge[] edgeTo; public void AcyclicSP(EdgeWeightedDigraph, int); private void relax(DirectedEdge); public double distTo(int); public boolean hasPathTo(int); public Iterable pathTo(int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/EdgeWeightedDigraph.class
package edu.uoc.mecm.eda.utils; public synchronized class EdgeWeightedDigraph { private final int V; private int E; private Bag[] adj; public void EdgeWeightedDigraph(int); public void EdgeWeightedDigraph(int, int); public void EdgeWeightedDigraph(In); public void EdgeWeightedDigraph(EdgeWeightedDigraph); public int V(); public int E(); private void validateVertex(int); public void addEdge(DirectedEdge); public Iterable adj(int); public int outdegree(int); public Iterable edges(); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DepthFirstSearch.class
package edu.uoc.mecm.eda.utils; public synchronized class DepthFirstSearch { private boolean[] marked; private int count; public void DepthFirstSearch(Graph, int); private void dfs(Graph, int); public boolean marked(int); public int count(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Edge.class
package edu.uoc.mecm.eda.utils; public synchronized class Edge implements Comparable { private final int v; private final int w; private final double weight; public void Edge(int, int, double); public double weight(); public int either(); public int other(int); public int compareTo(Edge); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/KosarajuSharirSCC.class
package edu.uoc.mecm.eda.utils; public synchronized class KosarajuSharirSCC { private boolean[] marked; private int[] id; private int count; static void <clinit>(); public void KosarajuSharirSCC(Digraph); private void dfs(Digraph, int); public int count(); public boolean stronglyConnected(int, int); public int id(int); private boolean check(Digraph); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Stack.class
package edu.uoc.mecm.eda.utils; public synchronized class Stack implements Iterable { private int N; private Stack$Node first; public void Stack(); public boolean isEmpty(); public int size(); public void push(Object); public Object pop(); public Object peek(); public String toString(); public java.util.Iterator iterator(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Queue$Node.class
package edu.uoc.mecm.eda.utils; synchronized class Queue$Node { private Object item; private Queue$Node next; private void Queue$Node(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DirectedDFS.class
package edu.uoc.mecm.eda.utils; public synchronized class DirectedDFS { private boolean[] marked; private int count; public void DirectedDFS(Digraph, int); public void DirectedDFS(Digraph, Iterable); private void dfs(Digraph, int); public boolean marked(int); public int count(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Queue$ListIterator.class
package edu.uoc.mecm.eda.utils; synchronized class Queue$ListIterator implements java.util.Iterator { private Queue$Node current; public void Queue$ListIterator(Queue, Queue$Node); public boolean hasNext(); public void remove(); public Object next(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Bag$Node.class
package edu.uoc.mecm.eda.utils; synchronized class Bag$Node { private Object item; private Bag$Node next; private void Bag$Node(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/BellmanFordSP.class
package edu.uoc.mecm.eda.utils; public synchronized class BellmanFordSP { private double[] distTo; private DirectedEdge[] edgeTo; private boolean[] onQueue; private Queue queue; private int cost; private Iterable cycle; static void <clinit>(); public void BellmanFordSP(EdgeWeightedDigraph, int); private void relax(EdgeWeightedDigraph, int); public boolean hasNegativeCycle(); public Iterable negativeCycle(); private void findNegativeCycle(); public double distTo(int); public boolean hasPathTo(int); public Iterable pathTo(int); private boolean check(EdgeWeightedDigraph, int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Cycle.class
package edu.uoc.mecm.eda.utils; public synchronized class Cycle { private boolean[] marked; private int[] edgeTo; private Stack cycle; public void Cycle(Graph); private boolean hasSelfLoop(Graph); private boolean hasParallelEdges(Graph); public boolean hasCycle(); public Iterable cycle(); private void dfs(Graph, int, int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/FloydWarshall.class
package edu.uoc.mecm.eda.utils; public synchronized class FloydWarshall { private boolean hasNegativeCycle; private double[][] distTo; private DirectedEdge[][] edgeTo; static void <clinit>(); public void FloydWarshall(AdjMatrixEdgeWeightedDigraph); public boolean hasNegativeCycle(); public Iterable negativeCycle(); public boolean hasPath(int, int); public double dist(int, int); public Iterable path(int, int); private boolean check(EdgeWeightedDigraph, int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Graph.class
package edu.uoc.mecm.eda.utils; public synchronized class Graph { private final int V; private int E; private Bag[] adj; public void Graph(int); public void Graph(In); public void Graph(Graph); public int V(); public int E(); private void validateVertex(int); public void addEdge(int, int); public Iterable adj(int); public int degree(int); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/AdjMatrixEdgeWeightedDigraph$AdjIterator.class
package edu.uoc.mecm.eda.utils; synchronized class AdjMatrixEdgeWeightedDigraph$AdjIterator implements java.util.Iterator, Iterable { private int v; private int w; public void AdjMatrixEdgeWeightedDigraph$AdjIterator(AdjMatrixEdgeWeightedDigraph, int); public java.util.Iterator iterator(); public boolean hasNext(); public DirectedEdge next(); public void remove(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Bag.class
package edu.uoc.mecm.eda.utils; public synchronized class Bag implements Iterable { private int N; private Bag$Node first; public void Bag(); public boolean isEmpty(); public int size(); public void add(Object); public java.util.Iterator iterator(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Bag$ListIterator.class
package edu.uoc.mecm.eda.utils; synchronized class Bag$ListIterator implements java.util.Iterator { private Bag$Node current; public void Bag$ListIterator(Bag, Bag$Node); public boolean hasNext(); public void remove(); public Object next(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Queue.class
package edu.uoc.mecm.eda.utils; public synchronized class Queue implements Iterable { private int N; private Queue$Node first; private Queue$Node last; public void Queue(); public boolean isEmpty(); public int size(); public Object peek(); public void enqueue(Object); public Object dequeue(); public String toString(); public java.util.Iterator iterator(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Digraph.class
package edu.uoc.mecm.eda.utils; public synchronized class Digraph { private final int V; private int E; private Bag[] adj; public void Digraph(int); public void Digraph(In); public void Digraph(Digraph); public int V(); public int E(); private void validateVertex(int); public void addEdge(int, int); public Iterable adj(int); public int outdegree(int); public Digraph reverse(); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/TransitiveClosure.class
package edu.uoc.mecm.eda.utils; public synchronized class TransitiveClosure { private DirectedDFS[] tc; public void TransitiveClosure(Digraph); public boolean reachable(int, int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DirectedCycle.class
package edu.uoc.mecm.eda.utils; public synchronized class DirectedCycle { private boolean[] marked; private int[] edgeTo; private boolean[] onStack; private Stack cycle; public void DirectedCycle(Digraph); private void dfs(Digraph, int); public boolean hasCycle(); public Iterable cycle(); private boolean check(Digraph); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/BreadthFirstDirectedPaths.class
package edu.uoc.mecm.eda.utils; public synchronized class BreadthFirstDirectedPaths { private static final int INFINITY = 2147483647; private boolean[] marked; private int[] edgeTo; private int[] distTo; public void BreadthFirstDirectedPaths(Digraph, int); public void BreadthFirstDirectedPaths(Digraph, Iterable); private void bfs(Digraph, int); private void bfs(Digraph, Iterable); public boolean hasPathTo(int); public int distTo(int); public Iterable pathTo(int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DijkstraSP.class
package edu.uoc.mecm.eda.utils; public synchronized class DijkstraSP { private double[] distTo; private DirectedEdge[] edgeTo; private IndexMinPQ pq; static void <clinit>(); public void DijkstraSP(EdgeWeightedDigraph, int); private void relax(DirectedEdge); public double distTo(int); public boolean hasPathTo(int); public Iterable pathTo(int); private boolean check(EdgeWeightedDigraph, int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/AdjMatrixEdgeWeightedDigraph.class
package edu.uoc.mecm.eda.utils; public synchronized class AdjMatrixEdgeWeightedDigraph { private int V; private int E; private DirectedEdge[][] adj; public void AdjMatrixEdgeWeightedDigraph(int); public void AdjMatrixEdgeWeightedDigraph(int, int); public int V(); public int E(); public void addEdge(DirectedEdge); public Iterable adj(int); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/In.class
package edu.uoc.mecm.eda.utils; public final synchronized class In { private java.util.Scanner scanner; private static final String CHARSET_NAME = UTF-8; private static final java.util.Locale LOCALE; private static final java.util.regex.Pattern WHITESPACE_PATTERN; private static final java.util.regex.Pattern EMPTY_PATTERN; private static final java.util.regex.Pattern EVERYTHING_PATTERN; static void <clinit>(); public void In(); public void In(java.net.Socket); public void In(java.net.URL); public void In(java.io.File); public void In(String); public void In(java.util.Scanner); public boolean exists(); public boolean isEmpty(); public boolean hasNextLine(); public boolean hasNextChar(); public String readLine(); public char readChar(); public String readAll(); public String readString(); public int readInt(); public double readDouble(); public float readFloat(); public long readLong(); public short readShort(); public byte readByte(); public boolean readBoolean(); public String[] readAllStrings(); public String[] readAllLines(); public int[] readAllInts(); public double[] readAllDoubles(); public void close(); public static int[] readInts(String); public static double[] readDoubles(String); public static String[] readStrings(String); public static int[] readInts(); public static double[] readDoubles(); public static String[] readStrings(); public static void main(String[]); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/EdgeWeightedGraph.class
package edu.uoc.mecm.eda.utils; public synchronized class EdgeWeightedGraph { private final int V; private int E; private Bag[] adj; public void EdgeWeightedGraph(int); public void EdgeWeightedGraph(int, int); public void EdgeWeightedGraph(In); public void EdgeWeightedGraph(EdgeWeightedGraph); public int V(); public int E(); private void validateVertex(int); public void addEdge(Edge); public Iterable adj(int); public int degree(int); public Iterable edges(); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Topological.class
package edu.uoc.mecm.eda.utils; public synchronized class Topological { private Iterable order; public void Topological(Digraph); public void Topological(EdgeWeightedDigraph); public Iterable order(); public boolean hasOrder(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/EdgeWeightedDirectedCycle.class
package edu.uoc.mecm.eda.utils; public synchronized class EdgeWeightedDirectedCycle { private boolean[] marked; private DirectedEdge[] edgeTo; private boolean[] onStack; private Stack cycle; static void <clinit>(); public void EdgeWeightedDirectedCycle(EdgeWeightedDigraph); private void dfs(EdgeWeightedDigraph, int); public boolean hasCycle(); public Iterable cycle(); private boolean check(EdgeWeightedDigraph); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DirectedEdge.class
package edu.uoc.mecm.eda.utils; public synchronized class DirectedEdge { private final int v; private final int w; private final double weight; public void DirectedEdge(int, int, double); public int from(); public int to(); public double weight(); public String toString(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Bipartite.class
package edu.uoc.mecm.eda.utils; public synchronized class Bipartite { private boolean isBipartite; private boolean[] color; private boolean[] marked; private int[] edgeTo; private Stack cycle; static void <clinit>(); public void Bipartite(Graph); private void dfs(Graph, int); public boolean isBipartite(); public boolean color(int); public Iterable oddCycle(); private boolean check(Graph); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DepthFirstPaths.class
package edu.uoc.mecm.eda.utils; public synchronized class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private final int s; public void DepthFirstPaths(Graph, int); private void dfs(Graph, int); public boolean hasPathTo(int); public Iterable pathTo(int); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/Stack$Node.class
package edu.uoc.mecm.eda.utils; synchronized class Stack$Node { private Object item; private Stack$Node next; private void Stack$Node(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/IndexMinPQ.class
package edu.uoc.mecm.eda.utils; public synchronized class IndexMinPQ implements Iterable { private int NMAX; private int N; private int[] pq; private int[] qp; private Comparable[] keys; public void IndexMinPQ(int); public boolean isEmpty(); public boolean contains(int); public int size(); public void insert(int, Comparable); public int minIndex(); public Comparable minKey(); public int delMin(); public Comparable keyOf(int); public void change(int, Comparable); public void changeKey(int, Comparable); public void decreaseKey(int, Comparable); public void increaseKey(int, Comparable); public void delete(int); private boolean greater(int, int); private void exch(int, int); private void swim(int); private void sink(int); public java.util.Iterator iterator(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/utils/DepthFirstOrder.class
package edu.uoc.mecm.eda.utils; public synchronized class DepthFirstOrder { private boolean[] marked; private int[] pre; private int[] post; private Queue preorder; private Queue postorder; private int preCounter; private int postCounter; public void DepthFirstOrder(Digraph); public void DepthFirstOrder(EdgeWeightedDigraph); private void dfs(Digraph, int); private void dfs(EdgeWeightedDigraph, int); public int pre(int); public int post(int); public Iterable post(); public Iterable pre(); public Iterable reversePost(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/game/map/Movement.class
package edu.uoc.mecm.eda.game.map; public final synchronized enum Movement { public static final Movement LEFT; public static final Movement RIGHT; public static final Movement UP; public static final Movement DOWN; static void <clinit>(); private void Movement(String, int); public static Movement[] values(); public static Movement valueOf(String); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/game/map/Dungeon.class
package edu.uoc.mecm.eda.game.map; public synchronized class Dungeon { private int width; private int height; private java.util.Set listTreasures; private java.util.Set listMonsters; private java.util.Set listNonWalkable; private int exit; private int start; public int from2Dto1D(int, int) throws IllegalArgumentException; public int[] from1Dto2D(int); public boolean canMove(int, Movement); public boolean canMove(int, int, Movement); public int move(int, Movement) throws IllegalArgumentException; public int[] move(int, int, Movement) throws IllegalArgumentException; public Movement getMovement(int, int) throws IllegalArgumentException; public Movement getMovement(int, int, int, int) throws IllegalArgumentException; private java.util.List getAdjacentTiles(int); private java.util.List getAdjacentTiles2D(int, int); private java.util.List getAdjacentDiagonalTiles(int); private java.util.List getAdjacentDiagonalTiles2D(int, int); public java.util.List getWatchArea(int); public java.util.List getWatchArea2D(int, int); public java.util.List getMovableArea(int); public java.util.List getMovableArea(int, int); public int getWidth(); public int getHeight(); public boolean isWalkable(int, int) throws IllegalArgumentException; public boolean isWalkable(int); public boolean hasEnemy(int, int); public boolean hasEnemy(int) throws IllegalArgumentException; public boolean hasTreasure(int, int) throws IllegalArgumentException; public boolean hasTreasure(int); public boolean hasExit(int, int) throws IllegalArgumentException; public boolean hasExit(int); public boolean isStartingPoint(int, int) throws IllegalArgumentException; public boolean isStartingPoint(int); public boolean isValidPlan(java.util.List); public void Dungeon(String) throws IllegalArgumentException; public static void main(String[]); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/search/AnEvenNumber.class
package edu.uoc.mecm.eda.search; public synchronized class AnEvenNumber { protected edu.uoc.mecm.eda.utils.Graph sourceGraph; public void AnEvenNumber(edu.uoc.mecm.eda.utils.Graph); public Integer getAnEvenNumber(int, int) throws IllegalArgumentException; public static void main(String[]); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/search/ClosestPrimeNumber.class
package edu.uoc.mecm.eda.search; public synchronized class ClosestPrimeNumber { protected edu.uoc.mecm.eda.utils.Graph sourceGraph; public void ClosestPrimeNumber(edu.uoc.mecm.eda.utils.Graph); private boolean isPrimeNumber(int); public Integer getClosestFrom(int) throws IllegalArgumentException; public static void main(String[]); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/player/Thief.class
package edu.uoc.mecm.eda.player; public synchronized class Thief { edu.uoc.mecm.eda.game.map.Dungeon dungeonMap; public void Thief(edu.uoc.mecm.eda.game.map.Dungeon); public java.util.List getPlan(); }
M0.506_PEC4/bin/edu/uoc/mecm/eda/player/RestrictedBreadthFirstPaths.class
package edu.uoc.mecm.eda.player; public synchronized class RestrictedBreadthFirstPaths { private static final int INFINITY = 2147483647; java.util.Set marked; private int[] edgeTo; private int[] distTo; public void RestrictedBreadthFirstPaths(edu.uoc.mecm.eda.utils.Graph, int, java.util.Set); private void bfs(edu.uoc.mecm.eda.utils.Graph, int, java.util.Set); public boolean hasPathTo(int); public int distTo(int); public java.util.List pathTo(int, boolean); public java.util.List pathFrom(int, boolean); }
M0.506_PEC4/resources/ejercicio3/grafo2.txt
14 15 0 1 1 5 3 5 5 7 2 7 4 7 2 4 6 8 8 10 9 10 9 11 10 12 11 12 11 13 12 13
M0.506_PEC4/resources/ejercicio3/grafo1.txt
14 12 0 1 1 4 2 4 3 4 5 6 5 7 7 11 8 13 11 13 9 12 9 10 10 12
M0.506_PEC4/resources/ejercicio4/dungeon4.txt
20 20 ---------E---------X ---------------XXX-- ---------------XTX-- XXXXXXXX---------X-- XXXTX--X---------X-- -------X---------X-- -------X---------X-- -------XXXXXXXXXXX-- -------------------- -------------------- --MMMMMMMMMMMMMMMM-- -------------------- ----------XXXXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX-T--XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX-S--XXXXXXXX
M0.506_PEC4/resources/ejercicio4/dungeon5.txt
20 20 -------M-E-M-------X -M-------------XXX-- -----------M---XTX-- XXXXXXXX---------X-- XXXTX--X---------X-- -------X---------X-- -------X---------X-- ---M---XXXXXXXXXXX-- -------------------- -------------------- --MMMMMMMMMMMMMMMM-- ---------X---------- ----------XXXXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX-T--XXXXXXXX XXXXXXXX----XXXXXXXX XXXXXXXX-S--XXXXXXXX
M0.506_PEC4/resources/ejercicio4/dungeon6.txt
20 20 T------------------T -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- XX---------------XXX XX---------------XXX XX---------------XXX S-----------------ET
M0.506_PEC4/resources/ejercicio4/dungeon2.txt
7 7 E-----S -----T- ------- ------- ------- ------- T--M--T
M0.506_PEC4/resources/ejercicio4/dungeon3.txt
7 7 E-----S X----TX X-----X ------X ------X ------- T--M--T
M0.506_PEC4/resources/ejercicio4/dungeon1.txt
7 7 E------ ------- --T---- ------- ------- ---S--- T-----T
M0.506_PEC4/.classpath
M0.506_PEC4/.settings/org.eclipse.jdt.core.prefs
eclipse.preferences.version=1 org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.7 org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve org.eclipse.jdt.core.compiler.compliance=1.7 org.eclipse.jdt.core.compiler.debug.lineNumber=generate org.eclipse.jdt.core.compiler.debug.localVariable=generate org.eclipse.jdt.core.compiler.debug.sourceFile=generate org.eclipse.jdt.core.compiler.problem.assertIdentifier=error org.eclipse.jdt.core.compiler.problem.enumIdentifier=error org.eclipse.jdt.core.compiler.source=1.7
M0.506_PEC4/.project
M0.506_PEC4 org.eclipse.jdt.core.javabuilder org.eclipse.jdt.core.javanature
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DepthFirstDirectedPaths.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
No usage of edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DepthFirstOrder.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DepthFirstOrder
No usage of edu.uoc.mecm.eda.utils.DepthFirstOrder Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Digraph.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Digraph
-
Packages that use Digraph
Package Description edu.uoc.mecm.eda.utils -
-
Uses of Digraph in edu.uoc.mecm.eda.utils
Methods in edu.uoc.mecm.eda.utils that return Digraph
Constructors in edu.uoc.mecm.eda.utils with parameters of type DigraphModifier and Type Method and Description Digraph Digraph.reverse() Returns the reverse of the digraph. Constructor and Description BreadthFirstDirectedPaths(Digraph G, int s) Computes the shortest path from s and every other vertex in graph G. BreadthFirstDirectedPaths(Digraph G, java.lang.Iterable<java.lang.Integer> sources) Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G. DepthFirstDirectedPaths(Digraph G, int s) Computes a directed path from s to every other vertex in digraph G. DepthFirstOrder(Digraph G) Determines a depth-first order for the digraph G. Digraph(Digraph G) Initializes a new digraph that is a deep copy of G. DirectedCycle(Digraph G) Determines whether the digraph G has a directed cycle and, if so, finds such a cycle. DirectedDFS(Digraph G, int s) Computes the vertices in digraph G that are reachable from the source vertex s. DirectedDFS(Digraph G, java.lang.Iterable<java.lang.Integer> sources) Computes the vertices in digraph G that are connected to any of the source vertices sources. KosarajuSharirSCC(Digraph G) Computes the strong components of the digraph G. Topological(Digraph G) Determines whether the digraph G has a topological order and, if so, finds such a topological order. TransitiveClosure(Digraph G) Computes the transitive closure of the digraph G.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/FloydWarshall.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.FloydWarshall
No usage of edu.uoc.mecm.eda.utils.FloydWarshall Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/AcyclicSP.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.AcyclicSP
No usage of edu.uoc.mecm.eda.utils.AcyclicSP Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/EdgeWeightedDirectedCycle.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
No usage of edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DirectedDFS.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DirectedDFS
No usage of edu.uoc.mecm.eda.utils.DirectedDFS Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DirectedCycle.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DirectedCycle
No usage of edu.uoc.mecm.eda.utils.DirectedCycle Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Graph.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Graph
-
Packages that use Graph
Package Description edu.uoc.mecm.eda.player edu.uoc.mecm.eda.search edu.uoc.mecm.eda.utils -
-
Uses of Graph in edu.uoc.mecm.eda.player
Constructors in edu.uoc.mecm.eda.player with parameters of type GraphConstructor and Description RestrictedBreadthFirstPaths(Graph G, int s, java.util.Set<java.lang.Integer> interestVertex) Calcula el camino más corto entre el vértice origen y los puntos de interés -
Uses of Graph in edu.uoc.mecm.eda.search
Constructors in edu.uoc.mecm.eda.search with parameters of type GraphConstructor and Description AnEvenNumber(Graph g) Constructor de la clase ClosestPrimeNumber(Graph g) Constructor de la clase -
Uses of Graph in edu.uoc.mecm.eda.utils
Constructors in edu.uoc.mecm.eda.utils with parameters of type GraphConstructor and Description Bipartite(Graph G) Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle. BreadthFirstPaths(Graph G, int s) Computes the shortest path between the source vertex s and every other vertex in the graph G. BreadthFirstPaths(Graph G, java.lang.Iterable<java.lang.Integer> sources) Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G. CC(Graph G) Computes the connected components of the undirected graph G. Cycle(Graph G) Determines whether the undirected graph G has a cycle and, if so, finds such a cycle. DepthFirstPaths(Graph G, int s) Computes a path between s and every other vertex in graph G. DepthFirstSearch(Graph G, int s) Computes the vertices in graph G that are connected to the source vertex s. Graph(Graph G) Initializes a new graph that is a deep copy of G.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DepthFirstSearch.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DepthFirstSearch
No usage of edu.uoc.mecm.eda.utils.DepthFirstSearch Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Queue.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Queue
No usage of edu.uoc.mecm.eda.utils.Queue Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/In.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.In
-
Packages that use In
Package Description edu.uoc.mecm.eda.utils -
-
Uses of In in edu.uoc.mecm.eda.utils
Constructors in edu.uoc.mecm.eda.utils with parameters of type InConstructor and Description Digraph(In in) Initializes a digraph from an input stream. EdgeWeightedDigraph(In in) Initializes an edge-weighted digraph from an input stream. EdgeWeightedGraph(In in) Initializes an edge-weighted graph from an input stream. Graph(In in) Initializes a graph from an input stream.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DepthFirstPaths.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DepthFirstPaths
No usage of edu.uoc.mecm.eda.utils.DepthFirstPaths Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/BreadthFirstDirectedPaths.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
No usage of edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Bag.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Bag
No usage of edu.uoc.mecm.eda.utils.Bag Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/TransitiveClosure.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.TransitiveClosure
No usage of edu.uoc.mecm.eda.utils.TransitiveClosure Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Cycle.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Cycle
No usage of edu.uoc.mecm.eda.utils.Cycle Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DijkstraSP.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DijkstraSP
No usage of edu.uoc.mecm.eda.utils.DijkstraSP Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/BreadthFirstPaths.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.BreadthFirstPaths
No usage of edu.uoc.mecm.eda.utils.BreadthFirstPaths Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/KosarajuSharirSCC.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.KosarajuSharirSCC
No usage of edu.uoc.mecm.eda.utils.KosarajuSharirSCC Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/CC.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.CC
No usage of edu.uoc.mecm.eda.utils.CC Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Topological.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Topological
No usage of edu.uoc.mecm.eda.utils.Topological Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Bipartite.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Bipartite
No usage of edu.uoc.mecm.eda.utils.Bipartite Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/EdgeWeightedDigraph.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
-
Packages that use EdgeWeightedDigraph
Package Description edu.uoc.mecm.eda.utils -
-
Uses of EdgeWeightedDigraph in edu.uoc.mecm.eda.utils
Constructors in edu.uoc.mecm.eda.utils with parameters of type EdgeWeightedDigraphConstructor and Description AcyclicSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G. BellmanFordSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G. DepthFirstOrder(EdgeWeightedDigraph G) Determines a depth-first order for the edge-weighted digraph G. DijkstraSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G. EdgeWeightedDigraph(EdgeWeightedDigraph G) Initializes a new edge-weighted digraph that is a deep copy of G. EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) Determines whether the edge-weighted digraph G has a directed cycle and, if so, finds such a cycle. Topological(EdgeWeightedDigraph G) Determines whether the edge-weighted digraph G has a topological order and, if so, finds such an order.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/EdgeWeightedGraph.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
-
Packages that use EdgeWeightedGraph
Package Description edu.uoc.mecm.eda.utils -
-
Uses of EdgeWeightedGraph in edu.uoc.mecm.eda.utils
Constructors in edu.uoc.mecm.eda.utils with parameters of type EdgeWeightedGraphConstructor and Description EdgeWeightedGraph(EdgeWeightedGraph G) Initializes a new edge-weighted graph that is a deep copy of G.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/DirectedEdge.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.DirectedEdge
-
Packages that use DirectedEdge
Package Description edu.uoc.mecm.eda.utils -
-
Uses of DirectedEdge in edu.uoc.mecm.eda.utils
Methods in edu.uoc.mecm.eda.utils that return types with arguments of type DirectedEdge
Methods in edu.uoc.mecm.eda.utils with parameters of type DirectedEdgeModifier and Type Method and Description java.lang.Iterable<DirectedEdge> AdjMatrixEdgeWeightedDigraph.adj(int v) Returns the directed edges incident from vertex v. java.lang.Iterable<DirectedEdge> EdgeWeightedDigraph.adj(int v) Returns the directed edges incident from vertex v. java.lang.Iterable<DirectedEdge> EdgeWeightedDirectedCycle.cycle() Returns a directed cycle if the edge-weighted digraph has a directed cycle, and null otherwise. java.lang.Iterable<DirectedEdge> EdgeWeightedDigraph.edges() Returns all directed edges in the edge-weighted digraph. java.lang.Iterable<DirectedEdge> BellmanFordSP.negativeCycle() Returns a negative cycle reachable from the source vertex s, or null if there is no such cycle. java.lang.Iterable<DirectedEdge> FloydWarshall.negativeCycle() Returns a negative cycle, or null if there is no such cycle. java.lang.Iterable<DirectedEdge> FloydWarshall.path(int s, int t) Returns a shortest path from vertex s to vertex t. java.lang.Iterable<DirectedEdge> BellmanFordSP.pathTo(int v) Returns a shortest path from the source s to vertex v. java.lang.Iterable<DirectedEdge> DijkstraSP.pathTo(int v) Returns a shortest path from the source vertex s to vertex v. java.lang.Iterable<DirectedEdge> AcyclicSP.pathTo(int v) Returns a shortest path from the source vertex s to vertex v. Modifier and Type Method and Description void AdjMatrixEdgeWeightedDigraph.addEdge(DirectedEdge e) Adds the directed edge e to the edge-weighted digraph (if there is not already an edge with the same endpoints). void EdgeWeightedDigraph.addEdge(DirectedEdge e) Adds the directed edge e to the edge-weighted digraph.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/AdjMatrixEdgeWeightedDigraph.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
-
Packages that use AdjMatrixEdgeWeightedDigraph
Package Description edu.uoc.mecm.eda.utils -
-
Uses of AdjMatrixEdgeWeightedDigraph in edu.uoc.mecm.eda.utils
Constructors in edu.uoc.mecm.eda.utils with parameters of type AdjMatrixEdgeWeightedDigraphConstructor and Description FloydWarshall(AdjMatrixEdgeWeightedDigraph G) Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Edge.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Edge
-
Packages that use Edge
Package Description edu.uoc.mecm.eda.utils -
-
Uses of Edge in edu.uoc.mecm.eda.utils
Methods in edu.uoc.mecm.eda.utils that return types with arguments of type Edge
Methods in edu.uoc.mecm.eda.utils with parameters of type EdgeModifier and Type Method and Description java.lang.Iterable<Edge> EdgeWeightedGraph.adj(int v) Returns the edges incident on vertex v. java.lang.Iterable<Edge> EdgeWeightedGraph.edges() Returns all edges in the edge-weighted graph. Modifier and Type Method and Description void EdgeWeightedGraph.addEdge(Edge e) Adds the undirected edge e to the edge-weighted graph. int Edge.compareTo(Edge that) Compares two edges by weight.
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/IndexMinPQ.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.IndexMinPQ
No usage of edu.uoc.mecm.eda.utils.IndexMinPQ Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/BellmanFordSP.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.BellmanFordSP
No usage of edu.uoc.mecm.eda.utils.BellmanFordSP Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/class-use/Stack.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.utils.Stack
No usage of edu.uoc.mecm.eda.utils.Stack Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DepthFirstDirectedPaths.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DepthFirstDirectedPaths
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
-
public class DepthFirstDirectedPaths extends java.lang.Object
The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph.This implementation uses depth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DepthFirstDirectedPaths(Digraph G, int s) Computes a directed path from s to every other vertex in digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean hasPathTo(int v) Is there a directed path from the source vertex s to vertex v? java.lang.Iterable<java.lang.Integer> pathTo(int v) Returns a directed path from the source vertex s to vertex v, or null if no such path.
-
-
-
Constructor Detail
-
DepthFirstDirectedPaths
public DepthFirstDirectedPaths(Digraph G, int s)
Computes a directed path from s to every other vertex in digraph G.- Parameters:
- G - the digraph
- s - the source vertex
-
-
Method Detail
-
hasPathTo
public boolean hasPathTo(int v)
Is there a directed path from the source vertex s to vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a directed path from the source vertex s to vertex v, false otherwise
-
pathTo
public java.lang.Iterable<java.lang.Integer> pathTo(int v)
Returns a directed path from the source vertex s to vertex v, or null if no such path.- Parameters:
- v - the vertex
- Returns:
- the sequence of vertices on a directed path from the source vertex s to vertex v, as an Iterable
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DepthFirstOrder.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DepthFirstOrder
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DepthFirstOrder
-
public class DepthFirstOrder extends java.lang.Object
The DepthFirstOrder class represents a data type for determining depth-first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the preorder, postorder, and reverse postorder operation takes take time proportional to V.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DepthFirstOrder(Digraph G) Determines a depth-first order for the digraph G. DepthFirstOrder(EdgeWeightedDigraph G) Determines a depth-first order for the edge-weighted digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.lang.Iterable<java.lang.Integer> post() Returns the vertices in postorder. int post(int v) Returns the postorder number of vertex v. java.lang.Iterable<java.lang.Integer> pre() Returns the vertices in preorder. int pre(int v) Returns the preorder number of vertex v. java.lang.Iterable<java.lang.Integer> reversePost() Returns the vertices in reverse postorder.
-
-
-
Constructor Detail
-
DepthFirstOrder
public DepthFirstOrder(Digraph G)
Determines a depth-first order for the digraph G.- Parameters:
- G - the digraph
-
DepthFirstOrder
public DepthFirstOrder(EdgeWeightedDigraph G)
Determines a depth-first order for the edge-weighted digraph G.- Parameters:
- G - the edge-weighted digraph
-
-
Method Detail
-
pre
public int pre(int v)
Returns the preorder number of vertex v.- Parameters:
- v - the vertex
- Returns:
- the preorder number of vertex v
-
post
public int post(int v)
Returns the postorder number of vertex v.- Parameters:
- v - the vertex
- Returns:
- the postorder number of vertex v
-
post
public java.lang.Iterable<java.lang.Integer> post()
Returns the vertices in postorder.- Returns:
- the vertices in postorder, as an iterable of vertices
-
pre
public java.lang.Iterable<java.lang.Integer> pre()
Returns the vertices in preorder.- Returns:
- the vertices in preorder, as an iterable of vertices
-
reversePost
public java.lang.Iterable<java.lang.Integer> reversePost()
Returns the vertices in reverse postorder.- Returns:
- the vertices in reverse postorder, as an iterable of vertices
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Digraph.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Digraph
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Digraph
-
public class Digraph extends java.lang.Object
The Digraph class represents a directed graph of vertices named 0 through V - 1. It supports the following two primary operations: add an edge to the digraph, iterate over all of the vertices adjacent from a given vertex. Parallel edges and self-loops are permitted.This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent from a given vertex, which takes time proportional to the number of such vertices.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Digraph(Digraph G) Initializes a new digraph that is a deep copy of G. Digraph(In in) Initializes a digraph from an input stream. Digraph(int V) Initializes an empty digraph with V vertices.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description void addEdge(int v, int w) Adds the directed edge v->w to the digraph. java.lang.Iterable<java.lang.Integer> adj(int v) Returns the vertices adjacent from vertex v in the digraph. int E() Returns the number of edges in the digraph. int outdegree(int v) Returns the number of directed edges incident from vertex v. Digraph reverse() Returns the reverse of the digraph. java.lang.String toString() Returns a string representation of the graph. int V() Returns the number of vertices in the digraph.
-
-
-
Constructor Detail
-
Digraph
public Digraph(int V)
Initializes an empty digraph with V vertices.- Parameters:
- V - the number of vertices
- Throws:
- java.lang.IllegalArgumentException - if V < 0
-
Digraph
public Digraph(In in)
Initializes a digraph from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, with each entry separated by whitespace.- Parameters:
- in - the input stream
- Throws:
- java.lang.IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range
- java.lang.IllegalArgumentException - if the number of vertices or edges is negative
-
Digraph
public Digraph(Digraph G)
Initializes a new digraph that is a deep copy of G.- Parameters:
- G - the digraph to copy
-
-
Method Detail
-
V
public int V()
Returns the number of vertices in the digraph.- Returns:
- the number of vertices in the digraph
-
E
public int E()
Returns the number of edges in the digraph.- Returns:
- the number of edges in the digraph
-
addEdge
public void addEdge(int v, int w)Adds the directed edge v->w to the digraph.- Parameters:
- v - the tail vertex
- w - the head vertex
- Throws:
- java.lang.IndexOutOfBoundsException - unless both 0
-
adj
public java.lang.Iterable<java.lang.Integer> adj(int v)
Returns the vertices adjacent from vertex v in the digraph.- Parameters:
- v - the vertex
- Returns:
- the vertices adjacent from vertex v in the digraph, as an Iterable
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
outdegree
public int outdegree(int v)
Returns the number of directed edges incident from vertex v. This is known as the outdegree of vertex v.- Parameters:
- v - the vertex
- Returns:
- the outdegree of vertex v
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
reverse
public Digraph reverse()
Returns the reverse of the digraph.- Returns:
- the reverse of the digraph
-
toString
public java.lang.String toString()
Returns a string representation of the graph. This method takes time proportional to E + V.- Overrides:
- toString in class java.lang.Object
- Returns:
- the number of vertices V, followed by the number of edges E, followed by the V adjacency lists
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/FloydWarshall.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass FloydWarshall
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.FloydWarshall
-
public class FloydWarshall extends java.lang.Object
The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path between every pair of vertices or a negative cycle.This implementation uses the Floyd-Warshall algorithm. The constructor takes time proportional to V3 in the worst case, where V is the number of vertices. Afterwards, the dist(), hasPath(), and hasNegativeCycle() methods take constant time; the path() and negativeCycle() method takes time proportional to the number of edges returned.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description FloydWarshall(AdjMatrixEdgeWeightedDigraph G) Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description double dist(int s, int t) Returns the length of a shortest path from vertex s to vertex t. boolean hasNegativeCycle() Is there a negative cycle? boolean hasPath(int s, int t) Is there a path from the vertex s to vertex t? java.lang.Iterable<DirectedEdge> negativeCycle() Returns a negative cycle, or null if there is no such cycle. java.lang.Iterable<DirectedEdge> path(int s, int t) Returns a shortest path from vertex s to vertex t.
-
-
-
Constructor Detail
-
FloydWarshall
public FloydWarshall(AdjMatrixEdgeWeightedDigraph G)
Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G. If no such shortest path exists for some pair of vertices, it computes a negative cycle.- Parameters:
- G - the edge-weighted digraph
-
-
Method Detail
-
hasNegativeCycle
public boolean hasNegativeCycle()
Is there a negative cycle?- Returns:
- true if there is a negative cycle, and false otherwise
-
negativeCycle
public java.lang.Iterable<DirectedEdge> negativeCycle()
Returns a negative cycle, or null if there is no such cycle.- Returns:
- a negative cycle as an iterable of edges, or null if there is no such cycle
-
hasPath
public boolean hasPath(int s, int t)Is there a path from the vertex s to vertex t?- Parameters:
- s - the source vertex
- t - the destination vertex
- Returns:
- true if there is a path from vertex s to vertex t, and false otherwise
-
dist
public double dist(int s, int t)Returns the length of a shortest path from vertex s to vertex t.- Parameters:
- s - the source vertex
- t - the destination vertex
- Returns:
- the length of a shortest path from vertex s to vertex t; Double.POSITIVE_INFINITY if no such path
- Throws:
- java.lang.UnsupportedOperationException - if there is a negative cost cycle
-
path
public java.lang.Iterable<DirectedEdge> path(int s, int t)
Returns a shortest path from vertex s to vertex t.- Parameters:
- s - the source vertex
- t - the destination vertex
- Returns:
- a shortest path from vertex s to vertex t as an iterable of edges, and null if no such path
- Throws:
- java.lang.UnsupportedOperationException - if there is a negative cost cycle
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/package-use.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Package edu.uoc.mecm.eda.utils
-
Packages that use edu.uoc.mecm.eda.utils
Package Description edu.uoc.mecm.eda.player edu.uoc.mecm.eda.search edu.uoc.mecm.eda.utils -
Classes in edu.uoc.mecm.eda.utils used by edu.uoc.mecm.eda.player
Class and Description Graph The Graph class represents an undirected graph of vertices named 0 through V - 1. -
Classes in edu.uoc.mecm.eda.utils used by edu.uoc.mecm.eda.search
Class and Description Graph The Graph class represents an undirected graph of vertices named 0 through V - 1. -
Classes in edu.uoc.mecm.eda.utils used by edu.uoc.mecm.eda.utils
Class and Description AdjMatrixEdgeWeightedDigraph The AdjMatrixEdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. Digraph The Digraph class represents a directed graph of vertices named 0 through V - 1. DirectedEdge The DirectedEdge class represents a weighted edge in an EdgeWeightedDigraph. Edge The Edge class represents a weighted edge in an EdgeWeightedGraph. EdgeWeightedDigraph The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. EdgeWeightedGraph The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V - 1, where each undirected edge is of type Edge and has a real-valued weight. Graph The Graph class represents an undirected graph of vertices named 0 through V - 1. In Input.
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/AcyclicSP.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class AcyclicSP
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.AcyclicSP
-
public class AcyclicSP extends java.lang.Object
The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Afterwards, the distTo() and hasPathTo() methods take constant time and the pathTo() method takes time proportional to the number of edges in the shortest path returned.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description AcyclicSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description double distTo(int v) Returns the length of a shortest path from the source vertex s to vertex v. boolean hasPathTo(int v) Is there a path from the source vertex s to vertex v? java.lang.Iterable<DirectedEdge> pathTo(int v) Returns a shortest path from the source vertex s to vertex v.
-
-
-
Constructor Detail
-
AcyclicSP
public AcyclicSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G.- Parameters:
- G - the acyclic digraph
- s - the source vertex
- Throws:
- java.lang.IllegalArgumentException - if the digraph is not acyclic
- java.lang.IllegalArgumentException - unless 0 ≤ s ≤ V - 1
-
-
Method Detail
-
distTo
public double distTo(int v)
Returns the length of a shortest path from the source vertex s to vertex v.- Parameters:
- v - the destination vertex
- Returns:
- the length of a shortest path from the source vertex s to vertex v; Double.POSITIVE_INFINITY if no such path
-
hasPathTo
public boolean hasPathTo(int v)
Is there a path from the source vertex s to vertex v?- Parameters:
- v - the destination vertex
- Returns:
- true if there is a path from the source vertex s to vertex v, and false otherwise
-
pathTo
public java.lang.Iterable<DirectedEdge> pathTo(int v)
Returns a shortest path from the source vertex s to vertex v.- Parameters:
- v - the destination vertex
- Returns:
- a shortest path from the source vertex s to vertex v as an iterable of edges, and null if no such path
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/EdgeWeightedDirectedCycle.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass EdgeWeightedDirectedCycle
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
-
public class EdgeWeightedDirectedCycle extends java.lang.Object
The EdgeWeightedDirectedCycle class represents a data type for determining whether an edge-weighted digraph has a directed cycle. The hasCycle operation determines whether the edge-weighted digraph has a directed cycle and, if so, the cycle operation returns one.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.
See Topological to compute a topological order if the edge-weighted digraph is acyclic.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) Determines whether the edge-weighted digraph G has a directed cycle and, if so, finds such a cycle.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.lang.Iterable<DirectedEdge> cycle() Returns a directed cycle if the edge-weighted digraph has a directed cycle, and null otherwise. boolean hasCycle() Does the edge-weighted digraph have a directed cycle?
-
-
-
Constructor Detail
-
EdgeWeightedDirectedCycle
public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G)
Determines whether the edge-weighted digraph G has a directed cycle and, if so, finds such a cycle.- Parameters:
- G - the edge-weighted digraph
-
-
Method Detail
-
hasCycle
public boolean hasCycle()
Does the edge-weighted digraph have a directed cycle?- Returns:
- true if the edge-weighted digraph has a directed cycle, false otherwise
-
cycle
public java.lang.Iterable<DirectedEdge> cycle()
Returns a directed cycle if the edge-weighted digraph has a directed cycle, and null otherwise.- Returns:
- a directed cycle (as an iterable) if the edge-weighted digraph has a directed cycle, and null otherwise
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DirectedDFS.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DirectedDFS
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DirectedDFS
-
public class DirectedDFS extends java.lang.Object
The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex s (or set of source vertices) in a digraph. For versions that find the paths, see DepthFirstDirectedPaths and BreadthFirstDirectedPaths.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DirectedDFS(Digraph G, int s) Computes the vertices in digraph G that are reachable from the source vertex s. DirectedDFS(Digraph G, java.lang.Iterable<java.lang.Integer> sources) Computes the vertices in digraph G that are connected to any of the source vertices sources.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int count() Returns the number of vertices reachable from the source vertex (or source vertices). boolean marked(int v) Is there a directed path from the source vertex (or any of the source vertices) and vertex v?
-
-
-
Constructor Detail
-
DirectedDFS
public DirectedDFS(Digraph G, int s)
Computes the vertices in digraph G that are reachable from the source vertex s.- Parameters:
- G - the digraph
- s - the source vertex
-
DirectedDFS
public DirectedDFS(Digraph G, java.lang.Iterable<java.lang.Integer> sources)
Computes the vertices in digraph G that are connected to any of the source vertices sources.- Parameters:
- G - the graph
- sources - the source vertices
-
-
Method Detail
-
marked
public boolean marked(int v)
Is there a directed path from the source vertex (or any of the source vertices) and vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a directed path, false otherwise
-
count
public int count()
Returns the number of vertices reachable from the source vertex (or source vertices).- Returns:
- the number of vertices reachable from the source vertex (or source vertices)
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DirectedCycle.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DirectedCycle
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DirectedCycle
-
public class DirectedCycle extends java.lang.Object
The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle. The hasCycle operation determines whether the digraph has a directed cycle and, and of so, the cycle operation returns one.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.
See Topological to compute a topological order if the digraph is acyclic.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DirectedCycle(Digraph G) Determines whether the digraph G has a directed cycle and, if so, finds such a cycle.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.lang.Iterable<java.lang.Integer> cycle() Returns a directed cycle if the digraph has a directed cycle, and null otherwise. boolean hasCycle() Does the digraph have a directed cycle?
-
-
-
Constructor Detail
-
DirectedCycle
public DirectedCycle(Digraph G)
Determines whether the digraph G has a directed cycle and, if so, finds such a cycle.- Parameters:
- G - the digraph
-
-
Method Detail
-
hasCycle
public boolean hasCycle()
Does the digraph have a directed cycle?- Returns:
- true if the digraph has a directed cycle, false otherwise
-
cycle
public java.lang.Iterable<java.lang.Integer> cycle()
Returns a directed cycle if the digraph has a directed cycle, and null otherwise.- Returns:
- a directed cycle (as an iterable) if the digraph has a directed cycle, and null otherwise
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Graph.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Graph
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Graph
-
public class Graph extends java.lang.Object
The Graph class represents an undirected graph of vertices named 0 through V - 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Graph(Graph G) Initializes a new graph that is a deep copy of G. Graph(In in) Initializes a graph from an input stream. Graph(int V) Initializes an empty graph with V vertices and 0 edges.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description void addEdge(int v, int w) Adds the undirected edge v-w to the graph. java.lang.Iterable<java.lang.Integer> adj(int v) Returns the vertices adjacent to vertex v. int degree(int v) Returns the degree of vertex v. int E() Returns the number of edges in the graph. java.lang.String toString() Returns a string representation of the graph. int V() Returns the number of vertices in the graph.
-
-
-
Constructor Detail
-
Graph
public Graph(int V)
Initializes an empty graph with V vertices and 0 edges. param V the number of vertices- Throws:
- java.lang.IllegalArgumentException - if V < 0
-
Graph
public Graph(In in)
Initializes a graph from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, with each entry separated by whitespace.- Parameters:
- in - the input stream
- Throws:
- java.lang.IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range
- java.lang.IllegalArgumentException - if the number of vertices or edges is negative
-
Graph
public Graph(Graph G)
Initializes a new graph that is a deep copy of G.- Parameters:
- G - the graph to copy
-
-
Method Detail
-
V
public int V()
Returns the number of vertices in the graph.- Returns:
- the number of vertices in the graph
-
E
public int E()
Returns the number of edges in the graph.- Returns:
- the number of edges in the graph
-
addEdge
public void addEdge(int v, int w)Adds the undirected edge v-w to the graph.- Parameters:
- v - one vertex in the edge
- w - the other vertex in the edge
- Throws:
- java.lang.IndexOutOfBoundsException - unless both 0
-
adj
public java.lang.Iterable<java.lang.Integer> adj(int v)
Returns the vertices adjacent to vertex v.- Parameters:
- v - the vertex
- Returns:
- the vertices adjacent to vertex v as an Iterable
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
degree
public int degree(int v)
Returns the degree of vertex v.- Parameters:
- v - the vertex
- Returns:
- the degree of vertex v
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
toString
public java.lang.String toString()
Returns a string representation of the graph. This method takes time proportional to E + V.- Overrides:
- toString in class java.lang.Object
- Returns:
- the number of vertices V, followed by the number of edges E, followed by the V adjacency lists
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DepthFirstSearch.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DepthFirstSearch
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DepthFirstSearch
-
public class DepthFirstSearch extends java.lang.Object
The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph. For versions that find the paths, see DepthFirstPaths and BreadthFirstPaths.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DepthFirstSearch(Graph G, int s) Computes the vertices in graph G that are connected to the source vertex s.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int count() Returns the number of vertices connected to the source vertex s. boolean marked(int v) Is there a path between the source vertex s and vertex v?
-
-
-
Constructor Detail
-
DepthFirstSearch
public DepthFirstSearch(Graph G, int s)
Computes the vertices in graph G that are connected to the source vertex s.- Parameters:
- G - the graph
- s - the source vertex
-
-
Method Detail
-
marked
public boolean marked(int v)
Is there a path between the source vertex s and vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a path, false otherwise
-
count
public int count()
Returns the number of vertices connected to the source vertex s.- Returns:
- the number of vertices connected to the source vertex s
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Queue.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Queue<Item>
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Queue<Item>
-
- All Implemented Interfaces:
- java.lang.Iterable<Item>
public class Queue<Item> extends java.lang.Object implements java.lang.Iterable<Item>
The Queue class represents a first-in-first-out (FIFO) queue of generic items. It supports the usual enqueue and dequeue operations, along with methods for peeking at the first item, testing if the queue is empty, and iterating through the items in FIFO order.This implementation uses a singly-linked list with a static nested class for linked-list nodes. See LinkedQueue for the version from the textbook that uses a non-static nested class. The enqueue, dequeue, peek, size, and is-empty operations all take constant time in the worst case.
For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Queue() Initializes an empty queue.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description Item dequeue() Removes and returns the item on this queue that was least recently added. void enqueue(Item item) Adds the item to this queue. boolean isEmpty() Is this queue empty? java.util.Iterator<Item> iterator() Returns an iterator that iterates over the items in this queue in FIFO order. Item peek() Returns the item least recently added to this queue. int size() Returns the number of items in this queue. java.lang.String toString() Returns a string representation of this queue.
-
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Is this queue empty?- Returns:
- true if this queue is empty; false otherwise
-
size
public int size()
Returns the number of items in this queue.- Returns:
- the number of items in this queue
-
peek
public Item peek()
Returns the item least recently added to this queue.- Returns:
- the item least recently added to this queue
- Throws:
- java.util.NoSuchElementException - if this queue is empty
-
enqueue
public void enqueue(Item item)
Adds the item to this queue.- Parameters:
- item - the item to add
-
dequeue
public Item dequeue()
Removes and returns the item on this queue that was least recently added.- Returns:
- the item on this queue that was least recently added
- Throws:
- java.util.NoSuchElementException - if this queue is empty
-
toString
public java.lang.String toString()
Returns a string representation of this queue.- Overrides:
- toString in class java.lang.Object
- Returns:
- the sequence of items in FIFO order, separated by spaces
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/In.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass In
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.In
-
public final class In extends java.lang.Object
Input. This class provides methods for reading strings and numbers from standard input, file input, URLs, and sockets.The Locale used is: language = English, country = US. This is consistent with the formatting conventions with Java floating-point literals, command-line arguments (via Double.parseDouble(String)) and standard output.
For additional documentation, see Section 3.1 of Introduction to Programming in Java: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne.
Like Scanner, reading a token also consumes preceding Java whitespace, reading a full line consumes the following end-of-line delimeter, while reading a character consumes nothing extra.
Whitespace is defined in Character.isWhitespace(char). Newlines consist of \n, \r, \r\n, and Unicode hex code points 0x2028, 0x2029, 0x0085; see Scanner.java (NB: Java 6u23 and earlier uses only \r, \r, \r\n).
- Author:
- David Pritchard, Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description In() Create an input stream from standard input. In(java.io.File file) Create an input stream from a file. In(java.util.Scanner scanner) Create an input stream from a given Scanner source; use with new Scanner(String) to read from a string. In(java.net.Socket socket) Create an input stream from a socket. In(java.lang.String s) Create an input stream from a filename or web page name. In(java.net.URL url) Create an input stream from a URL.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Deprecated MethodsModifier and Type Method and Description void close() Close the input stream. boolean exists() Does the input stream exist? boolean hasNextChar() Is the input empty (including whitespace)? boolean hasNextLine() Does the input have a next line? boolean isEmpty() Is the input empty (except possibly for whitespace)? static void main(java.lang.String[] args) Test client. java.lang.String readAll() Read and return the remainder of the input as a string. double[] readAllDoubles() Read all doubles until the end of input is reached, and return them. int[] readAllInts() Read all ints until the end of input is reached, and return them. java.lang.String[] readAllLines() Reads all remaining lines from input stream and returns them as an array of strings. java.lang.String[] readAllStrings() Read all strings until the end of input is reached, and return them. boolean readBoolean() Read and return the next boolean, allowing case-insensitive "true" or "1" for true, and "false" or "0" for false. byte readByte() Read and return the next byte. char readChar() Read and return the next character. double readDouble() Read and return the next double. static double[] readDoubles() Deprecated. Clearer to use StdIn#readAllDoubles() static double[] readDoubles(java.lang.String filename) Deprecated. Clearer to use new In(filename).readAllDoubles() float readFloat() Read and return the next float. int readInt() Read and return the next int. static int[] readInts() Deprecated. Clearer to use StdIn#readAllInts() static int[] readInts(java.lang.String filename) Deprecated. Clearer to use new In(filename).readAllInts() java.lang.String readLine() Read and return the next line. long readLong() Read and return the next long. short readShort() Read and return the next short. java.lang.String readString() Read and return the next string. static java.lang.String[] readStrings() Deprecated. Clearer to use StdIn#readAllStrings() static java.lang.String[] readStrings(java.lang.String filename) Deprecated. Clearer to use new In(filename).readAllStrings()
-
-
-
Constructor Detail
-
In
public In()
Create an input stream from standard input.
-
In
public In(java.net.Socket socket)
Create an input stream from a socket.
-
In
public In(java.net.URL url)
Create an input stream from a URL.
-
In
public In(java.io.File file)
Create an input stream from a file.
-
In
public In(java.lang.String s)
Create an input stream from a filename or web page name.
-
In
public In(java.util.Scanner scanner)
Create an input stream from a given Scanner source; use with new Scanner(String) to read from a string.Note that this does not create a defensive copy, so the scanner will be mutated as you read on.
-
-
Method Detail
-
exists
public boolean exists()
Does the input stream exist?
-
isEmpty
public boolean isEmpty()
Is the input empty (except possibly for whitespace)? Use this to know whether the next call to readString(), readDouble(), etc will succeed.
-
hasNextLine
public boolean hasNextLine()
Does the input have a next line? Use this to know whether the next call to readLine() will succeed.Functionally equivalent to hasNextChar().
-
hasNextChar
public boolean hasNextChar()
Is the input empty (including whitespace)? Use this to know whether the next call to readChar() will succeed.Functionally equivalent to hasNextLine().
-
readLine
public java.lang.String readLine()
Read and return the next line.
-
readChar
public char readChar()
Read and return the next character.
-
readAll
public java.lang.String readAll()
Read and return the remainder of the input as a string.
-
readString
public java.lang.String readString()
Read and return the next string.
-
readInt
public int readInt()
Read and return the next int.
-
readDouble
public double readDouble()
Read and return the next double.
-
readFloat
public float readFloat()
Read and return the next float.
-
readLong
public long readLong()
Read and return the next long.
-
readShort
public short readShort()
Read and return the next short.
-
readByte
public byte readByte()
Read and return the next byte.
-
readBoolean
public boolean readBoolean()
Read and return the next boolean, allowing case-insensitive "true" or "1" for true, and "false" or "0" for false.
-
readAllStrings
public java.lang.String[] readAllStrings()
Read all strings until the end of input is reached, and return them.
-
readAllLines
public java.lang.String[] readAllLines()
Reads all remaining lines from input stream and returns them as an array of strings.- Returns:
- all remaining lines on input stream, as an array of strings
-
readAllInts
public int[] readAllInts()
Read all ints until the end of input is reached, and return them.
-
readAllDoubles
public double[] readAllDoubles()
Read all doubles until the end of input is reached, and return them.
-
close
public void close()
Close the input stream.
-
readInts
public static int[] readInts(java.lang.String filename)
Deprecated. Clearer to use new In(filename).readAllInts() Reads all ints from a file
-
readDoubles
public static double[] readDoubles(java.lang.String filename)
Deprecated. Clearer to use new In(filename).readAllDoubles() Reads all doubles from a file
-
readStrings
public static java.lang.String[] readStrings(java.lang.String filename)
Deprecated. Clearer to use new In(filename).readAllStrings() Reads all strings from a file
-
readInts
public static int[] readInts()
Deprecated. Clearer to use StdIn#readAllInts() Reads all ints from stdin
-
readDoubles
public static double[] readDoubles()
Deprecated. Clearer to use StdIn#readAllDoubles() Reads all doubles from stdin
-
readStrings
public static java.lang.String[] readStrings()
Deprecated. Clearer to use StdIn#readAllStrings() Reads all strings from stdin
-
main
public static void main(java.lang.String[] args)
Test client.
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DepthFirstPaths.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DepthFirstPaths
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DepthFirstPaths
-
public class DepthFirstPaths extends java.lang.Object
The DepthFirstPaths class represents a data type for finding paths from a source vertex s to every other vertex in an undirected graph.This implementation uses depth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DepthFirstPaths(Graph G, int s) Computes a path between s and every other vertex in graph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean hasPathTo(int v) Is there a path between the source vertex s and vertex v? java.lang.Iterable<java.lang.Integer> pathTo(int v) Returns a path between the source vertex s and vertex v, or null if no such path.
-
-
-
Constructor Detail
-
DepthFirstPaths
public DepthFirstPaths(Graph G, int s)
Computes a path between s and every other vertex in graph G.- Parameters:
- G - the graph
- s - the source vertex
-
-
Method Detail
-
hasPathTo
public boolean hasPathTo(int v)
Is there a path between the source vertex s and vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a path, false otherwise
-
pathTo
public java.lang.Iterable<java.lang.Integer> pathTo(int v)
Returns a path between the source vertex s and vertex v, or null if no such path.- Parameters:
- v - the vertex
- Returns:
- the sequence of vertices on a path between the source vertex s and vertex v, as an Iterable
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/BreadthFirstDirectedPaths.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass BreadthFirstDirectedPaths
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
-
public class BreadthFirstDirectedPaths extends java.lang.Object
The BreadthDirectedFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or set of source vertices) to every other vertex in the digraph.This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the digraph) proportional to V.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description BreadthFirstDirectedPaths(Digraph G, int s) Computes the shortest path from s and every other vertex in graph G. BreadthFirstDirectedPaths(Digraph G, java.lang.Iterable<java.lang.Integer> sources) Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int distTo(int v) Returns the number of edges in a shortest path from the source s (or sources) to vertex v? boolean hasPathTo(int v) Is there a directed path from the source s (or sources) to vertex v? java.lang.Iterable<java.lang.Integer> pathTo(int v) Returns a shortest path from s (or sources) to v, or null if no such path.
-
-
-
Constructor Detail
-
BreadthFirstDirectedPaths
public BreadthFirstDirectedPaths(Digraph G, int s)
Computes the shortest path from s and every other vertex in graph G.- Parameters:
- G - the digraph
- s - the source vertex
-
BreadthFirstDirectedPaths
public BreadthFirstDirectedPaths(Digraph G, java.lang.Iterable<java.lang.Integer> sources)
Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G.- Parameters:
- G - the digraph
- sources - the source vertices
-
-
Method Detail
-
hasPathTo
public boolean hasPathTo(int v)
Is there a directed path from the source s (or sources) to vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a directed path, false otherwise
-
distTo
public int distTo(int v)
Returns the number of edges in a shortest path from the source s (or sources) to vertex v?- Parameters:
- v - the vertex
- Returns:
- the number of edges in a shortest path
-
pathTo
public java.lang.Iterable<java.lang.Integer> pathTo(int v)
Returns a shortest path from s (or sources) to v, or null if no such path.- Parameters:
- v - the vertex
- Returns:
- the sequence of vertices on a shortest path, as an Iterable
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Bag.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Bag<Item>
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Bag<Item>
-
- All Implemented Interfaces:
- java.lang.Iterable<Item>
public class Bag<Item> extends java.lang.Object implements java.lang.Iterable<Item>
The Bag class represents a bag (or multiset) of generic items. It supports insertion and iterating over the items in arbitrary order.This implementation uses a singly-linked list with a static nested class Node. See LinkedBag for the version from the textbook that uses a non-static nested class. The add, isEmpty, and size operations take constant time. Iteration takes time proportional to the number of items.
For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Bag() Initializes an empty bag.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description void add(Item item) Adds the item to this bag. boolean isEmpty() Is this bag empty? java.util.Iterator<Item> iterator() Returns an iterator that iterates over the items in the bag in arbitrary order. int size() Returns the number of items in this bag.
-
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Is this bag empty?- Returns:
- true if this bag is empty; false otherwise
-
size
public int size()
Returns the number of items in this bag.- Returns:
- the number of items in this bag
-
add
public void add(Item item)
Adds the item to this bag.- Parameters:
- item - the item to add to this bag
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/TransitiveClosure.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class TransitiveClosure
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.TransitiveClosure
-
public class TransitiveClosure extends java.lang.Object
The TransitiveClosure class represents a data type for computing the transitive closure of a digraph.This implementation runs depth-first search from each vertex. The constructor takes time proportional to V(V + E) (in the worst case) and uses space proportional to V2, where V is the number of vertices and E is the number of edges.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description TransitiveClosure(Digraph G) Computes the transitive closure of the digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean reachable(int v, int w) Is there a directed path from vertex v to vertex w in the digraph?
-
-
-
Constructor Detail
-
TransitiveClosure
public TransitiveClosure(Digraph G)
Computes the transitive closure of the digraph G.- Parameters:
- G - the digraph
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Cycle.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Cycle
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Cycle
-
public class Cycle extends java.lang.Object
The Cycle class represents a data type for determining whether an undirected graph has a cycle. The hasCycle operation determines whether the graph has a cycle and, if so, the cycle operation returns one.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Cycle(Graph G) Determines whether the undirected graph G has a cycle and, if so, finds such a cycle.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.lang.Iterable<java.lang.Integer> cycle() Returns a cycle if the graph has a cycle, and null otherwise. boolean hasCycle() Does the graph have a cycle?
-
-
-
Constructor Detail
-
Cycle
public Cycle(Graph G)
Determines whether the undirected graph G has a cycle and, if so, finds such a cycle.- Parameters:
- G - the graph
-
-
Method Detail
-
hasCycle
public boolean hasCycle()
Does the graph have a cycle?- Returns:
- true if the graph has a cycle, false otherwise
-
cycle
public java.lang.Iterable<java.lang.Integer> cycle()
Returns a cycle if the graph has a cycle, and null otherwise.- Returns:
- a cycle (as an iterable) if the graph has a cycle, and null otherwise
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DijkstraSP.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DijkstraSP
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DijkstraSP
-
public class DijkstraSP extends java.lang.Object
The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Afterwards, the distTo() and hasPathTo() methods take constant time and the pathTo() method takes time proportional to the number of edges in the shortest path returned.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DijkstraSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description double distTo(int v) Returns the length of a shortest path from the source vertex s to vertex v. boolean hasPathTo(int v) Is there a path from the source vertex s to vertex v? java.lang.Iterable<DirectedEdge> pathTo(int v) Returns a shortest path from the source vertex s to vertex v.
-
-
-
Constructor Detail
-
DijkstraSP
public DijkstraSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.- Parameters:
- G - the edge-weighted digraph
- s - the source vertex
- Throws:
- java.lang.IllegalArgumentException - if an edge weight is negative
- java.lang.IllegalArgumentException - unless 0 ≤ s ≤ V - 1
-
-
Method Detail
-
distTo
public double distTo(int v)
Returns the length of a shortest path from the source vertex s to vertex v.- Parameters:
- v - the destination vertex
- Returns:
- the length of a shortest path from the source vertex s to vertex v; Double.POSITIVE_INFINITY if no such path
-
hasPathTo
public boolean hasPathTo(int v)
Is there a path from the source vertex s to vertex v?- Parameters:
- v - the destination vertex
- Returns:
- true if there is a path from the source vertex s to vertex v, and false otherwise
-
pathTo
public java.lang.Iterable<DirectedEdge> pathTo(int v)
Returns a shortest path from the source vertex s to vertex v.- Parameters:
- v - the destination vertex
- Returns:
- a shortest path from the source vertex s to vertex v as an iterable of edges, and null if no such path
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/BreadthFirstPaths.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass BreadthFirstPaths
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.BreadthFirstPaths
-
public class BreadthFirstPaths extends java.lang.Object
The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or a set of source vertices) to every other vertex in an undirected graph.This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description BreadthFirstPaths(Graph G, int s) Computes the shortest path between the source vertex s and every other vertex in the graph G. BreadthFirstPaths(Graph G, java.lang.Iterable<java.lang.Integer> sources) Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int distTo(int v) Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v? boolean hasPathTo(int v) Is there a path between the source vertex s (or sources) and vertex v? java.lang.Iterable<java.lang.Integer> pathTo(int v) Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.
-
-
-
Constructor Detail
-
BreadthFirstPaths
public BreadthFirstPaths(Graph G, int s)
Computes the shortest path between the source vertex s and every other vertex in the graph G.- Parameters:
- G - the graph
- s - the source vertex
-
BreadthFirstPaths
public BreadthFirstPaths(Graph G, java.lang.Iterable<java.lang.Integer> sources)
Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G.- Parameters:
- G - the graph
- sources - the source vertices
-
-
Method Detail
-
hasPathTo
public boolean hasPathTo(int v)
Is there a path between the source vertex s (or sources) and vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a path, and false otherwise
-
distTo
public int distTo(int v)
Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?- Parameters:
- v - the vertex
- Returns:
- the number of edges in a shortest path
-
pathTo
public java.lang.Iterable<java.lang.Integer> pathTo(int v)
Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.- Parameters:
- v - the vertex
- Returns:
- the sequence of vertices on a shortest path, as an Iterable
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/package-frame.html
edu.uoc.mecm.eda.utils
Classes
- AcyclicSP
- AdjMatrixEdgeWeightedDigraph
- Bag
- BellmanFordSP
- Bipartite
- BreadthFirstDirectedPaths
- BreadthFirstPaths
- CC
- Cycle
- DepthFirstDirectedPaths
- DepthFirstOrder
- DepthFirstPaths
- DepthFirstSearch
- Digraph
- DijkstraSP
- DirectedCycle
- DirectedDFS
- DirectedEdge
- Edge
- EdgeWeightedDigraph
- EdgeWeightedDirectedCycle
- EdgeWeightedGraph
- FloydWarshall
- Graph
- In
- IndexMinPQ
- KosarajuSharirSCC
- Queue
- Stack
- Topological
- TransitiveClosure
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/KosarajuSharirSCC.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass KosarajuSharirSCC
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.KosarajuSharirSCC
-
public class KosarajuSharirSCC extends java.lang.Object
The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph. The id operation determines in which strong component a given vertex lies; the areStronglyConnected operation determines whether two vertices are in the same strong component; and the count operation determines the number of strong components. The component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.This implementation uses the Kosaraju-Sharir algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the id, count, and areStronglyConnected operations take constant time. For alternate implementations of the same API, see TarjanSCC and GabowSCC.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description KosarajuSharirSCC(Digraph G) Computes the strong components of the digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int count() Returns the number of strong components. int id(int v) Returns the component id of the strong component containing vertex v. boolean stronglyConnected(int v, int w) Are vertices v and w in the same strong component?
-
-
-
Constructor Detail
-
KosarajuSharirSCC
public KosarajuSharirSCC(Digraph G)
Computes the strong components of the digraph G.- Parameters:
- G - the digraph
-
-
Method Detail
-
count
public int count()
Returns the number of strong components.- Returns:
- the number of strong components
-
stronglyConnected
public boolean stronglyConnected(int v, int w)Are vertices v and w in the same strong component?- Parameters:
- v - one vertex
- w - the other vertex
- Returns:
- true if vertices v and w are in the same strong component, and false otherwise
-
id
public int id(int v)
Returns the component id of the strong component containing vertex v.- Parameters:
- v - the vertex
- Returns:
- the component id of the strong component containing vertex v
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/CC.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass CC
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.CC
-
public class CC extends java.lang.Object
The CC class represents a data type for determining the connected components in an undirected graph. The id operation determines in which connected component a given vertex lies; the connected operation determines whether two vertices are in the same connected component; the count operation determines the number of connected components; and the size operation determines the number of vertices in the connect component containing a given vertex. The component identifier of a connected component is one of the vertices in the connected component: two vertices have the same component identifier if and only if they are in the same connected component.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the id, count, connected, and size operations take constant time.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description CC(Graph G) Computes the connected components of the undirected graph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean connected(int v, int w) Are vertices v and w in the same connected component? int count() Returns the number of connected components. int id(int v) Returns the component id of the connected component containing vertex v. int size(int v) Returns the number of vertices in the connected component containing vertex v.
-
-
-
Constructor Detail
-
CC
public CC(Graph G)
Computes the connected components of the undirected graph G.- Parameters:
- G - the graph
-
-
Method Detail
-
id
public int id(int v)
Returns the component id of the connected component containing vertex v.- Parameters:
- v - the vertex
- Returns:
- the component id of the connected component containing vertex v
-
size
public int size(int v)
Returns the number of vertices in the connected component containing vertex v.- Parameters:
- v - the vertex
- Returns:
- the number of vertices in the connected component containing vertex v
-
count
public int count()
Returns the number of connected components.- Returns:
- the number of connected components
-
connected
public boolean connected(int v, int w)Are vertices v and w in the same connected component?- Parameters:
- v - one vertex
- w - the other vertex
- Returns:
- true if vertices v and w are in the same connected component, and false otherwise
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/package-summary.html
JavaScript is disabled on your browser. Skip navigation links- Prev Package
- Next Package
Package edu.uoc.mecm.eda.utils
-
Class Summary
Class Description AcyclicSP The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs). AdjMatrixEdgeWeightedDigraph The AdjMatrixEdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. Bag<Item> The Bag class represents a bag (or multiset) of generic items. BellmanFordSP The BellmanFordSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs with no negative cycles. Bipartite The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. BreadthFirstDirectedPaths The BreadthDirectedFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or set of source vertices) to every other vertex in the digraph. BreadthFirstPaths The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or a set of source vertices) to every other vertex in an undirected graph. CC The CC class represents a data type for determining the connected components in an undirected graph. Cycle The Cycle class represents a data type for determining whether an undirected graph has a cycle. DepthFirstDirectedPaths The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph. DepthFirstOrder The DepthFirstOrder class represents a data type for determining depth-first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder. DepthFirstPaths The DepthFirstPaths class represents a data type for finding paths from a source vertex s to every other vertex in an undirected graph. DepthFirstSearch The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph. Digraph The Digraph class represents a directed graph of vertices named 0 through V - 1. DijkstraSP The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative. DirectedCycle The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle. DirectedDFS The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex s (or set of source vertices) in a digraph. DirectedEdge The DirectedEdge class represents a weighted edge in an EdgeWeightedDigraph. Edge The Edge class represents a weighted edge in an EdgeWeightedGraph. EdgeWeightedDigraph The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. EdgeWeightedDirectedCycle The EdgeWeightedDirectedCycle class represents a data type for determining whether an edge-weighted digraph has a directed cycle. EdgeWeightedGraph The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V - 1, where each undirected edge is of type Edge and has a real-valued weight. FloydWarshall The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles. Graph The Graph class represents an undirected graph of vertices named 0 through V - 1. In Input. IndexMinPQ<Key extends java.lang.Comparable<Key>> The IndexMinPQ class represents an indexed priority queue of generic keys. KosarajuSharirSCC The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph. Queue<Item> The Queue class represents a first-in-first-out (FIFO) queue of generic items. Stack<Item> The Stack class represents a last-in-first-out (LIFO) stack of generic items. Topological The Topological class represents a data type for determining a topological order of a directed acyclic graph (DAG). TransitiveClosure The TransitiveClosure class represents a data type for computing the transitive closure of a digraph.
- Prev Package
- Next Package
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Topological.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Topological
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Topological
-
public class Topological extends java.lang.Object
The Topological class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The hasOrder operation determines whether the digraph has a topological order, and if so, the order operation returns one.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasOrder operation takes constant time; the order operation takes time proportional to V.
See DirectedCycle and EdgeWeightedDirectedCycle to compute a directed cycle if the digraph is not a DAG.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Topological(Digraph G) Determines whether the digraph G has a topological order and, if so, finds such a topological order. Topological(EdgeWeightedDigraph G) Determines whether the edge-weighted digraph G has a topological order and, if so, finds such an order.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean hasOrder() Does the digraph have a topological order? java.lang.Iterable<java.lang.Integer> order() Returns a topological order if the digraph has a topologial order, and null otherwise.
-
-
-
Constructor Detail
-
Topological
public Topological(Digraph G)
Determines whether the digraph G has a topological order and, if so, finds such a topological order.- Parameters:
- G - the digraph
-
Topological
public Topological(EdgeWeightedDigraph G)
Determines whether the edge-weighted digraph G has a topological order and, if so, finds such an order.- Parameters:
- G - the edge-weighted digraph
-
-
Method Detail
-
order
public java.lang.Iterable<java.lang.Integer> order()
Returns a topological order if the digraph has a topologial order, and null otherwise.- Returns:
- a topological order of the vertices (as an interable) if the digraph has a topological order (or equivalently, if the digraph is a DAG), and null otherwise
-
hasOrder
public boolean hasOrder()
Does the digraph have a topological order?- Returns:
- true if the digraph has a topological order (or equivalently, if the digraph is a DAG), and false otherwise
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Bipartite.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Bipartite
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Bipartite
-
public class Bipartite extends java.lang.Object
The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The isBipartite operation determines whether the graph is bipartite. If so, the color operation determines a bipartition; if not, the oddCycle operation determines a cycle with an odd number of edges.This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the isBipartite and color operations take constant time; the oddCycle operation takes time proportional to the length of the cycle.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Bipartite(Graph G) Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean color(int v) Returns the side of the bipartite that vertex v is on. boolean isBipartite() Is the graph bipartite? java.lang.Iterable<java.lang.Integer> oddCycle() Returns an odd-length cycle if the graph is not bipartite, and null otherwise.
-
-
-
Constructor Detail
-
Bipartite
public Bipartite(Graph G)
Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.- Parameters:
- G - the graph
-
-
Method Detail
-
isBipartite
public boolean isBipartite()
Is the graph bipartite?- Returns:
- true if the graph is bipartite, false otherwise
-
color
public boolean color(int v)
Returns the side of the bipartite that vertex v is on. param v the vertex- Returns:
- the side of the bipartition that vertex v is on; two vertices are in the same side of the bipartition if and only if they have the same color
- Throws:
- java.lang.UnsupportedOperationException - if this method is called when the graph is not bipartite
-
oddCycle
public java.lang.Iterable<java.lang.Integer> oddCycle()
Returns an odd-length cycle if the graph is not bipartite, and null otherwise.- Returns:
- an odd-length cycle (as an iterable) if the graph is not bipartite (and hence has an odd-length cycle), and null otherwise
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/package-tree.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
Hierarchy For Package edu.uoc.mecm.eda.utils
Package Hierarchies:Class Hierarchy
- java.lang.Object
- edu.uoc.mecm.eda.utils.AcyclicSP
- edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- edu.uoc.mecm.eda.utils.Bag<Item> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.utils.BellmanFordSP
- edu.uoc.mecm.eda.utils.Bipartite
- edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- edu.uoc.mecm.eda.utils.BreadthFirstPaths
- edu.uoc.mecm.eda.utils.CC
- edu.uoc.mecm.eda.utils.Cycle
- edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
- edu.uoc.mecm.eda.utils.DepthFirstOrder
- edu.uoc.mecm.eda.utils.DepthFirstPaths
- edu.uoc.mecm.eda.utils.DepthFirstSearch
- edu.uoc.mecm.eda.utils.Digraph
- edu.uoc.mecm.eda.utils.DijkstraSP
- edu.uoc.mecm.eda.utils.DirectedCycle
- edu.uoc.mecm.eda.utils.DirectedDFS
- edu.uoc.mecm.eda.utils.DirectedEdge
- edu.uoc.mecm.eda.utils.Edge (implements java.lang.Comparable<T>)
- edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
- edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- edu.uoc.mecm.eda.utils.FloydWarshall
- edu.uoc.mecm.eda.utils.Graph
- edu.uoc.mecm.eda.utils.In
- edu.uoc.mecm.eda.utils.IndexMinPQ<Key> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.utils.KosarajuSharirSCC
- edu.uoc.mecm.eda.utils.Queue<Item> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.utils.Stack<Item> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.utils.Topological
- edu.uoc.mecm.eda.utils.TransitiveClosure
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/EdgeWeightedDigraph.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass EdgeWeightedDigraph
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
-
public class EdgeWeightedDigraph extends java.lang.Object
The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all of edges incident from a given vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.This implementation uses an adjacency-lists representation, which is a vertex-indexed array of @link{Bag} objects. All operations take constant time (in the worst case) except iterating over the edges incident from a given vertex, which takes time proportional to the number of such edges.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description EdgeWeightedDigraph(EdgeWeightedDigraph G) Initializes a new edge-weighted digraph that is a deep copy of G. EdgeWeightedDigraph(In in) Initializes an edge-weighted digraph from an input stream. EdgeWeightedDigraph(int V) Initializes an empty edge-weighted digraph with V vertices and 0 edges. EdgeWeightedDigraph(int V, int E) Initializes a random edge-weighted digraph with V vertices and E edges.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description void addEdge(DirectedEdge e) Adds the directed edge e to the edge-weighted digraph. java.lang.Iterable<DirectedEdge> adj(int v) Returns the directed edges incident from vertex v. int E() Returns the number of edges in the edge-weighted digraph. java.lang.Iterable<DirectedEdge> edges() Returns all directed edges in the edge-weighted digraph. int outdegree(int v) Returns the number of directed edges incident from vertex v. java.lang.String toString() Returns a string representation of the edge-weighted digraph. int V() Returns the number of vertices in the edge-weighted digraph.
-
-
-
Constructor Detail
-
EdgeWeightedDigraph
public EdgeWeightedDigraph(int V)
Initializes an empty edge-weighted digraph with V vertices and 0 edges. param V the number of vertices- Throws:
- java.lang.IllegalArgumentException - if V < 0
-
EdgeWeightedDigraph
public EdgeWeightedDigraph(int V, int E)Initializes a random edge-weighted digraph with V vertices and E edges. param V the number of vertices param E the number of edges- Throws:
- java.lang.IllegalArgumentException - if V < 0
- java.lang.IllegalArgumentException - if E < 0
-
EdgeWeightedDigraph
public EdgeWeightedDigraph(In in)
Initializes an edge-weighted digraph from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge weights, with each entry separated by whitespace.- Parameters:
- in - the input stream
- Throws:
- java.lang.IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range
- java.lang.IllegalArgumentException - if the number of vertices or edges is negative
-
EdgeWeightedDigraph
public EdgeWeightedDigraph(EdgeWeightedDigraph G)
Initializes a new edge-weighted digraph that is a deep copy of G.- Parameters:
- G - the edge-weighted graph to copy
-
-
Method Detail
-
V
public int V()
Returns the number of vertices in the edge-weighted digraph.- Returns:
- the number of vertices in the edge-weighted digraph
-
E
public int E()
Returns the number of edges in the edge-weighted digraph.- Returns:
- the number of edges in the edge-weighted digraph
-
addEdge
public void addEdge(DirectedEdge e)
Adds the directed edge e to the edge-weighted digraph.- Parameters:
- e - the edge
- Throws:
- java.lang.IndexOutOfBoundsException - unless endpoints of edge are between 0 and V-1
-
adj
public java.lang.Iterable<DirectedEdge> adj(int v)
Returns the directed edges incident from vertex v.- Parameters:
- v - the vertex
- Returns:
- the directed edges incident from vertex v as an Iterable
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
outdegree
public int outdegree(int v)
Returns the number of directed edges incident from vertex v. This is known as the outdegree of vertex v.- Parameters:
- v - the vertex
- Returns:
- the outdegree of vertex v
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
edges
public java.lang.Iterable<DirectedEdge> edges()
Returns all directed edges in the edge-weighted digraph. To iterate over the edges in the edge-weighted graph, use foreach notation: for (DirectedEdge e : G.edges()).- Returns:
- all edges in the edge-weighted graph as an Iterable.
-
toString
public java.lang.String toString()
Returns a string representation of the edge-weighted digraph. This method takes time proportional to E + V.- Overrides:
- toString in class java.lang.Object
- Returns:
- the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/EdgeWeightedGraph.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass EdgeWeightedGraph
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.EdgeWeightedGraph
-
public class EdgeWeightedGraph extends java.lang.Object
The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V - 1, where each undirected edge is of type Edge and has a real-valued weight. It supports the following two primary operations: add an edge to the graph, iterate over all of the edges incident to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.This implementation uses an adjacency-lists representation, which is a vertex-indexed array of @link{Bag} objects. All operations take constant time (in the worst case) except iterating over the edges incident to a given vertex, which takes time proportional to the number of such edges.
For additional documentation, see Section 4.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description EdgeWeightedGraph(EdgeWeightedGraph G) Initializes a new edge-weighted graph that is a deep copy of G. EdgeWeightedGraph(In in) Initializes an edge-weighted graph from an input stream. EdgeWeightedGraph(int V) Initializes an empty edge-weighted graph with V vertices and 0 edges. EdgeWeightedGraph(int V, int E) Initializes a random edge-weighted graph with V vertices and E edges.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description void addEdge(Edge e) Adds the undirected edge e to the edge-weighted graph. java.lang.Iterable<Edge> adj(int v) Returns the edges incident on vertex v. int degree(int v) Returns the degree of vertex v. int E() Returns the number of edges in the edge-weighted graph. java.lang.Iterable<Edge> edges() Returns all edges in the edge-weighted graph. java.lang.String toString() Returns a string representation of the edge-weighted graph. int V() Returns the number of vertices in the edge-weighted graph.
-
-
-
Constructor Detail
-
EdgeWeightedGraph
public EdgeWeightedGraph(int V)
Initializes an empty edge-weighted graph with V vertices and 0 edges. param V the number of vertices- Throws:
- java.lang.IllegalArgumentException - if V < 0
-
EdgeWeightedGraph
public EdgeWeightedGraph(int V, int E)Initializes a random edge-weighted graph with V vertices and E edges. param V the number of vertices param E the number of edges- Throws:
- java.lang.IllegalArgumentException - if V < 0
- java.lang.IllegalArgumentException - if E < 0
-
EdgeWeightedGraph
public EdgeWeightedGraph(In in)
Initializes an edge-weighted graph from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge weights, with each entry separated by whitespace.- Parameters:
- in - the input stream
- Throws:
- java.lang.IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range
- java.lang.IllegalArgumentException - if the number of vertices or edges is negative
-
EdgeWeightedGraph
public EdgeWeightedGraph(EdgeWeightedGraph G)
Initializes a new edge-weighted graph that is a deep copy of G.- Parameters:
- G - the edge-weighted graph to copy
-
-
Method Detail
-
V
public int V()
Returns the number of vertices in the edge-weighted graph.- Returns:
- the number of vertices in the edge-weighted graph
-
E
public int E()
Returns the number of edges in the edge-weighted graph.- Returns:
- the number of edges in the edge-weighted graph
-
addEdge
public void addEdge(Edge e)
Adds the undirected edge e to the edge-weighted graph.- Parameters:
- e - the edge
- Throws:
- java.lang.IndexOutOfBoundsException - unless both endpoints are between 0 and V-1
-
adj
public java.lang.Iterable<Edge> adj(int v)
Returns the edges incident on vertex v.- Parameters:
- v - the vertex
- Returns:
- the edges incident on vertex v as an Iterable
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
degree
public int degree(int v)
Returns the degree of vertex v.- Parameters:
- v - the vertex
- Returns:
- the degree of vertex v
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
edges
public java.lang.Iterable<Edge> edges()
Returns all edges in the edge-weighted graph. To iterate over the edges in the edge-weighted graph, use foreach notation: for (Edge e : G.edges()).- Returns:
- all edges in the edge-weighted graph as an Iterable.
-
toString
public java.lang.String toString()
Returns a string representation of the edge-weighted graph. This method takes time proportional to E + V.- Overrides:
- toString in class java.lang.Object
- Returns:
- the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/DirectedEdge.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass DirectedEdge
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.DirectedEdge
-
public class DirectedEdge extends java.lang.Object
The DirectedEdge class represents a weighted edge in an EdgeWeightedDigraph. Each edge consists of two integers (naming the two vertices) and a real-value weight. The data type provides methods for accessing the two endpoints of the directed edge and the weight.For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description DirectedEdge(int v, int w, double weight) Initializes a directed edge from vertex v to vertex w with the given weight.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int from() Returns the tail vertex of the directed edge. int to() Returns the head vertex of the directed edge. java.lang.String toString() Returns a string representation of the directed edge. double weight() Returns the weight of the directed edge.
-
-
-
Constructor Detail
-
DirectedEdge
public DirectedEdge(int v, int w, double weight)Initializes a directed edge from vertex v to vertex w with the given weight.- Parameters:
- v - the tail vertex
- w - the head vertex
- weight - the weight of the directed edge
- Throws:
- java.lang.IndexOutOfBoundsException - if either v or w is a negative integer
- java.lang.IllegalArgumentException - if weight is NaN
-
-
Method Detail
-
from
public int from()
Returns the tail vertex of the directed edge.- Returns:
- the tail vertex of the directed edge
-
to
public int to()
Returns the head vertex of the directed edge.- Returns:
- the head vertex of the directed edge
-
weight
public double weight()
Returns the weight of the directed edge.- Returns:
- the weight of the directed edge
-
toString
public java.lang.String toString()
Returns a string representation of the directed edge.- Overrides:
- toString in class java.lang.Object
- Returns:
- a string representation of the directed edge
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/AdjMatrixEdgeWeightedDigraph.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass AdjMatrixEdgeWeightedDigraph
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
-
public class AdjMatrixEdgeWeightedDigraph extends java.lang.Object
The AdjMatrixEdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all of edges incident from a given vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges are disallowed; self-loops are permitted.This implementation uses an adjacency-matrix representation. All operations take constant time (in the worst case) except iterating over the edges incident from a given vertex, which takes time proportional to V.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description AdjMatrixEdgeWeightedDigraph(int V) Initializes an empty edge-weighted digraph with V vertices and 0 edges. AdjMatrixEdgeWeightedDigraph(int V, int E) Initializes a random edge-weighted digraph with V vertices and E edges.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description void addEdge(DirectedEdge e) Adds the directed edge e to the edge-weighted digraph (if there is not already an edge with the same endpoints). java.lang.Iterable<DirectedEdge> adj(int v) Returns the directed edges incident from vertex v. int E() Returns the number of edges in the edge-weighted digraph. java.lang.String toString() Returns a string representation of the edge-weighted digraph. int V() Returns the number of vertices in the edge-weighted digraph.
-
-
-
Constructor Detail
-
AdjMatrixEdgeWeightedDigraph
public AdjMatrixEdgeWeightedDigraph(int V)
Initializes an empty edge-weighted digraph with V vertices and 0 edges. param V the number of vertices- Throws:
- java.lang.IllegalArgumentException - if V < 0
-
AdjMatrixEdgeWeightedDigraph
public AdjMatrixEdgeWeightedDigraph(int V, int E)Initializes a random edge-weighted digraph with V vertices and E edges. param V the number of vertices param E the number of edges- Throws:
- java.lang.IllegalArgumentException - if V < 0
- java.lang.IllegalArgumentException - if E < 0
-
-
Method Detail
-
V
public int V()
Returns the number of vertices in the edge-weighted digraph.- Returns:
- the number of vertices in the edge-weighted digraph
-
E
public int E()
Returns the number of edges in the edge-weighted digraph.- Returns:
- the number of edges in the edge-weighted digraph
-
addEdge
public void addEdge(DirectedEdge e)
Adds the directed edge e to the edge-weighted digraph (if there is not already an edge with the same endpoints).- Parameters:
- e - the edge
-
adj
public java.lang.Iterable<DirectedEdge> adj(int v)
Returns the directed edges incident from vertex v.- Parameters:
- v - the vertex
- Returns:
- the directed edges incident from vertex v as an Iterable
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0
-
toString
public java.lang.String toString()
Returns a string representation of the edge-weighted digraph. This method takes time proportional to V2.- Overrides:
- toString in class java.lang.Object
- Returns:
- the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Edge.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Edge
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Edge
-
- All Implemented Interfaces:
- java.lang.Comparable<Edge>
public class Edge extends java.lang.Object implements java.lang.Comparable<Edge>
The Edge class represents a weighted edge in an EdgeWeightedGraph. Each edge consists of two integers (naming the two vertices) and a real-value weight. The data type provides methods for accessing the two endpoints of the edge and the weight. The natural order for this data type is by ascending order of weight.For additional documentation, see Section 4.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Edge(int v, int w, double weight) Initializes an edge between vertices v/tt> and w of the given weight.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int compareTo(Edge that) Compares two edges by weight. int either() Returns either endpoint of the edge. int other(int vertex) Returns the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex). java.lang.String toString() Returns a string representation of the edge. double weight() Returns the weight of the edge.
-
-
-
Constructor Detail
-
Edge
public Edge(int v, int w, double weight)Initializes an edge between vertices v/tt> and w of the given weight. param v one vertex param w the other vertex param weight the weight of the edge- Throws:
- java.lang.IndexOutOfBoundsException - if either v or w is a negative integer
- java.lang.IllegalArgumentException - if weight is NaN
-
-
Method Detail
-
weight
public double weight()
Returns the weight of the edge.- Returns:
- the weight of the edge
-
either
public int either()
Returns either endpoint of the edge.- Returns:
- either endpoint of the edge
-
other
public int other(int vertex)
Returns the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex).- Parameters:
- vertex - one endpoint of the edge
- Returns:
- the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex)
- Throws:
- java.lang.IllegalArgumentException - if the vertex is not one of the endpoints of the edge
-
compareTo
public int compareTo(Edge that)
Compares two edges by weight.- Specified by:
- compareTo in interface java.lang.Comparable<Edge>
- Parameters:
- that - the other edge
- Returns:
- a negative integer, zero, or positive integer depending on whether this edge is less than, equal to, or greater than that edge
-
toString
public java.lang.String toString()
Returns a string representation of the edge.- Overrides:
- toString in class java.lang.Object
- Returns:
- a string representation of the edge
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/IndexMinPQ.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass IndexMinPQ<Key extends java.lang.Comparable<Key>>
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.IndexMinPQ<Key>
-
- All Implemented Interfaces:
- java.lang.Iterable<java.lang.Integer>
public class IndexMinPQ<Key extends java.lang.Comparable<Key>> extends java.lang.Object implements java.lang.Iterable<java.lang.Integer>
The IndexMinPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with delete and change-the-key methods. In order to let the client refer to keys on the priority queue, an integer between 0 and NMAX-1 is associated with each key—the client uses this integer to specify which key to delete or change. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys.This implementation uses a binary heap along with an array to associate keys with integers in the given range. The insert, delete-the-minimum, delete, change-key, decrease-key, and increase-key operations take logarithmic time. The is-empty, size, min-index, min-key, and key-of operations take constant time. Construction takes time proportional to the specified capacity.
For additional documentation, see Section 2.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description IndexMinPQ(int NMAX) Initializes an empty indexed priority queue with indices between 0 and NMAX-1.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated MethodsModifier and Type Method and Description void change(int i, Key key) Deprecated. Replaced by changeKey() void changeKey(int i, Key key) Change the key associated with index i to the specified value. boolean contains(int i) Is i an index on the priority queue? void decreaseKey(int i, Key key) Decrease the key associated with index i to the specified value. void delete(int i) Remove the key associated with index i. int delMin() Removes a minimum key and returns its associated index. void increaseKey(int i, Key key) Increase the key associated with index i to the specified value. void insert(int i, Key key) Associates key with index i. boolean isEmpty() Is the priority queue empty? java.util.Iterator<java.lang.Integer> iterator() Returns an iterator that iterates over the keys on the priority queue in ascending order. Key keyOf(int i) Returns the key associated with index i. int minIndex() Returns an index associated with a minimum key. Key minKey() Returns a minimum key. int size() Returns the number of keys on the priority queue.
-
-
-
Constructor Detail
-
IndexMinPQ
public IndexMinPQ(int NMAX)
Initializes an empty indexed priority queue with indices between 0 and NMAX-1.- Parameters:
- NMAX - the keys on the priority queue are index from 0 to NMAX-1
- Throws:
- java.lang.IllegalArgumentException - if NMAX < 0
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Is the priority queue empty?- Returns:
- true if the priority queue is empty; false otherwise
-
contains
public boolean contains(int i)
Is i an index on the priority queue?- Parameters:
- i - an index
- Throws:
- java.lang.IndexOutOfBoundsException - unless (0 ≤ i < NMAX)
-
size
public int size()
Returns the number of keys on the priority queue.- Returns:
- the number of keys on the priority queue
-
insert
public void insert(int i, Key key)Associates key with index i.- Parameters:
- i - an index
- key - the key to associate with index i
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
- java.util.IllegalArgumentException - if there already is an item associated with index i
-
minIndex
public int minIndex()
Returns an index associated with a minimum key.- Returns:
- an index associated with a minimum key
- Throws:
- java.util.NoSuchElementException - if priority queue is empty
-
minKey
public Key minKey()
Returns a minimum key.- Returns:
- a minimum key
- Throws:
- java.util.NoSuchElementException - if priority queue is empty
-
delMin
public int delMin()
Removes a minimum key and returns its associated index.- Returns:
- an index associated with a minimum key
- Throws:
- java.util.NoSuchElementException - if priority queue is empty
-
keyOf
public Key keyOf(int i)
Returns the key associated with index i.- Parameters:
- i - the index of the key to return
- Returns:
- the key associated with index i
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
- java.util.NoSuchElementException - no key is associated with index i
-
change
@Deprecated public void change(int i, Key key)Deprecated. Replaced by changeKey() Change the key associated with index i to the specified value.- Parameters:
- i - the index of the key to change
- key - change the key assocated with index i to this key
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
-
changeKey
public void changeKey(int i, Key key)Change the key associated with index i to the specified value.- Parameters:
- i - the index of the key to change
- key - change the key assocated with index i to this key
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
- java.util.NoSuchElementException - no key is associated with index i
-
decreaseKey
public void decreaseKey(int i, Key key)Decrease the key associated with index i to the specified value.- Parameters:
- i - the index of the key to decrease
- key - decrease the key assocated with index i to this key
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
- java.lang.IllegalArgumentException - if key ≥ key associated with index i
- java.util.NoSuchElementException - no key is associated with index i
-
increaseKey
public void increaseKey(int i, Key key)Increase the key associated with index i to the specified value.- Parameters:
- i - the index of the key to increase
- key - increase the key assocated with index i to this key
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
- java.lang.IllegalArgumentException - if key ≤ key associated with index i
- java.util.NoSuchElementException - no key is associated with index i
-
delete
public void delete(int i)
Remove the key associated with index i.- Parameters:
- i - the index of the key to remove
- Throws:
- java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX
- java.util.NoSuchElementException - no key is associated with index i
-
iterator
public java.util.Iterator<java.lang.Integer> iterator()
Returns an iterator that iterates over the keys on the priority queue in ascending order. The iterator doesn't implement remove() since it's optional.- Specified by:
- iterator in interface java.lang.Iterable<java.lang.Integer>
- Returns:
- an iterator that iterates over the keys in ascending order
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/BellmanFordSP.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass BellmanFordSP
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.BellmanFordSP
-
public class BellmanFordSP extends java.lang.Object
The BellmanFordSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path from the source vertex s to every other vertex or a negative cycle reachable from the source vertex.This implementation uses the Bellman-Ford-Moore algorithm. The constructor takes time proportional to V (V + E) in the worst case, where V is the number of vertices and E is the number of edges. Afterwards, the distTo(), hasPathTo(), and hasNegativeCycle() methods take constant time; the pathTo() and negativeCycle() method takes time proportional to the number of edges returned.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description BellmanFordSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description double distTo(int v) Returns the length of a shortest path from the source vertex s to vertex v. boolean hasNegativeCycle() Is there a negative cycle reachable from the source vertex s? boolean hasPathTo(int v) Is there a path from the source s to vertex v? java.lang.Iterable<DirectedEdge> negativeCycle() Returns a negative cycle reachable from the source vertex s, or null if there is no such cycle. java.lang.Iterable<DirectedEdge> pathTo(int v) Returns a shortest path from the source s to vertex v.
-
-
-
Constructor Detail
-
BellmanFordSP
public BellmanFordSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.- Parameters:
- G - the acyclic digraph
- s - the source vertex
- Throws:
- java.lang.IllegalArgumentException - unless 0 ≤ s ≤ V - 1
-
-
Method Detail
-
hasNegativeCycle
public boolean hasNegativeCycle()
Is there a negative cycle reachable from the source vertex s?- Returns:
- true if there is a negative cycle reachable from the source vertex s, and false otherwise
-
negativeCycle
public java.lang.Iterable<DirectedEdge> negativeCycle()
Returns a negative cycle reachable from the source vertex s, or null if there is no such cycle.- Returns:
- a negative cycle reachable from the soruce vertex s as an iterable of edges, and null if there is no such cycle
-
distTo
public double distTo(int v)
Returns the length of a shortest path from the source vertex s to vertex v.- Parameters:
- v - the destination vertex
- Returns:
- the length of a shortest path from the source vertex s to vertex v; Double.POSITIVE_INFINITY if no such path
- Throws:
- java.lang.UnsupportedOperationException - if there is a negative cost cycle reachable from the source vertex s
-
hasPathTo
public boolean hasPathTo(int v)
Is there a path from the source s to vertex v?- Parameters:
- v - the destination vertex
- Returns:
- true if there is a path from the source vertex s to vertex v, and false otherwise
-
pathTo
public java.lang.Iterable<DirectedEdge> pathTo(int v)
Returns a shortest path from the source s to vertex v.- Parameters:
- v - the destination vertex
- Returns:
- a shortest path from the source s to vertex v as an iterable of edges, and null if no such path
- Throws:
- java.lang.UnsupportedOperationException - if there is a negative cost cycle reachable from the source vertex s
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/utils/Stack.html
JavaScript is disabled on your browser. Skip navigation links edu.uoc.mecm.eda.utilsClass Stack<Item>
- java.lang.Object
-
- edu.uoc.mecm.eda.utils.Stack<Item>
-
- All Implemented Interfaces:
- java.lang.Iterable<Item>
public class Stack<Item> extends java.lang.Object implements java.lang.Iterable<Item>
The Stack class represents a last-in-first-out (LIFO) stack of generic items. It supports the usual push and pop operations, along with methods for peeking at the top item, testing if the stack is empty, and iterating through the items in LIFO order.This implementation uses a singly-linked list with a static nested class for linked-list nodes. See LinkedStack for the version from the textbook that uses a non-static nested class. The push, pop, peek, size, and is-empty operations all take constant time in the worst case.
For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
ConstructorsConstructor and Description Stack() Initializes an empty stack.
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean isEmpty() Is this stack empty? java.util.Iterator<Item> iterator() Returns an iterator to this stack that iterates through the items in LIFO order. Item peek() Returns (but does not remove) the item most recently added to this stack. Item pop() Removes and returns the item most recently added to this stack. void push(Item item) Adds the item to this stack. int size() Returns the number of items in the stack. java.lang.String toString() Returns a string representation of this stack.
-
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Is this stack empty?- Returns:
- true if this stack is empty; false otherwise
-
size
public int size()
Returns the number of items in the stack.- Returns:
- the number of items in the stack
-
push
public void push(Item item)
Adds the item to this stack.- Parameters:
- item - the item to add
-
pop
public Item pop()
Removes and returns the item most recently added to this stack.- Returns:
- the item most recently added
- Throws:
- java.util.NoSuchElementException - if this stack is empty
-
peek
public Item peek()
Returns (but does not remove) the item most recently added to this stack.- Returns:
- the item most recently added to this stack
- Throws:
- java.util.NoSuchElementException - if this stack is empty
-
toString
public java.lang.String toString()
Returns a string representation of this stack.- Overrides:
- toString in class java.lang.Object
- Returns:
- the sequence of items in the stack in LIFO order, separated by spaces
-
-
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/Dungeon.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class Dungeon
- java.lang.Object
-
- edu.uoc.mecm.eda.game.map.Dungeon
-
public class Dungeon extends java.lang.Object
-
-
Constructor Summary
ConstructorsConstructor and Description Dungeon(java.lang.String path) Construye una dungeon a partir de un fichero
-
Method Summary
All Methods Static Methods Instance Methods Concrete MethodsModifier and Type Method and Description boolean canMove(int x, int y, Movement m) Determina si se puede mover desde el punto indicado con el movimiento indicado boolean canMove(int point, Movement m) Determina si se puede mover desde el punto indicado con el movimiento indicado int[] from1Dto2D(int c) Pasa de una dimensión a dos int from2Dto1D(int x, int y) Pasa de 2 dimensiones a coordenadas en una dimensión int getHeight() Devuelve la altura del mapa java.util.List<java.lang.Integer> getMovableArea(int point) Devuelve una lista de casillas en coordenadas unidimensionales que constituyen las casillas dentro del mapa a las que se puede mover el ladrón java.util.List<int[]> getMovableArea(int x, int y) Devuelve una lista de casillas en coordenadas 2d que constituyen las casillas dentro del mapa a las que se puede mover el ladrón Movement getMovement(int source, int dest) Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino Movement getMovement(int x1, int y1, int x2, int y2) Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino java.util.List<java.lang.Integer> getWatchArea(int point) Devuelve una lista de casillas en coordenadas unidimensionales que constituyen el contorno de radio 1 de una casilla dada Se usa para determinar el área de vigilancia de un monstruo java.util.List<int[]> getWatchArea2D(int x, int y) Devuelve una lista de casillas en coordenadas 2D que constituyen el contorno de radio 1 de una casilla dada Se usa para determinar el área de vigilancia de un monstruo int getWidth() Devuelve la anchura del mapa boolean hasEnemy(int point) Determina si la casilla del mapa contiene un enemigo o no boolean hasEnemy(int x, int y) Determina si la casilla del mapa contiene un enemigo o no boolean hasExit(int point) Determina si la coordenada en una dimensión es válida o no boolean hasExit(int x, int y) Determina si la casilla contiene una salida o no boolean hasTreasure(int point) Determina si la casilla del mapa contiene un tesoro o no boolean hasTreasure(int x, int y) Determina si la casilla del mapa contiene un tesoro o no boolean isStartingPoint(int point) Determina si la casilla es el punto de inicio del ladrón boolean isStartingPoint(int x, int y) Determina si la casilla es el punto de inicio del ladrón boolean isValidPlan(java.util.List<Movement> plan) Dado un plan, determina si éste es válido para acabar el nivel boolean isWalkable(int point) Determina si la casilla del mapa es pisable o no boolean isWalkable(int x, int y) Determina si la casilla del mapa es pisable o no static void main(java.lang.String[] args) int[] move(int x, int y, Movement m) Dado un punto de origen, realiza un movimiento int move(int point, Movement m) Dado un punto de origen, realiza un movimiento
-
-
-
Constructor Detail
-
Dungeon
public Dungeon(java.lang.String path) throws java.lang.IllegalArgumentExceptionConstruye una dungeon a partir de un fichero- Parameters:
- path - el fichero que contiene la dungeon a leer
- Throws:
- java.lang.IllegalArgumentException
-
-
Method Detail
-
from2Dto1D
public int from2Dto1D(int x, int y) throws java.lang.IllegalArgumentExceptionPasa de 2 dimensiones a coordenadas en una dimensión- Parameters:
- x -
- y -
- Returns:
- la coordenada en una dimension
- Throws:
- java.lang.IllegalArgumentException - si las coordenadas no son válidas
-
from1Dto2D
public int[] from1Dto2D(int c)
Pasa de una dimensión a dos- Parameters:
- c - la coordenada en una dimensión
- Returns:
- un vector de dos dimensions con las coordenadas x e y
-
canMove
public boolean canMove(int point, Movement m)Determina si se puede mover desde el punto indicado con el movimiento indicado- Parameters:
- point - el punto indicado
- m - el movimiento
- Returns:
- true si se puede mover, false en caso contrario
-
canMove
public boolean canMove(int x, int y, Movement m)Determina si se puede mover desde el punto indicado con el movimiento indicado- Parameters:
- x - la coordenada x
- y - la coordenada y
- m - el movimiento
- Returns:
- true si se puede mover, false en caso contrario
-
move
public int move(int point, Movement m) throws java.lang.IllegalArgumentExceptionDado un punto de origen, realiza un movimiento- Parameters:
- point - el punto de origen
- m - el movimiento a realizar
- Returns:
- el nuevo punto tras haberse movido
- Throws:
- java.lang.IllegalArgumentException - si se realiza un movimiento incorrecto
-
move
public int[] move(int x, int y, Movement m) throws java.lang.IllegalArgumentExceptionDado un punto de origen, realiza un movimiento- Parameters:
- x - la coordenada x
- y - la coordenada y
- m - el movimiento a realizar
- Returns:
- el nuevo punto tras haberse movido
- Throws:
- java.lang.IllegalArgumentException - si se realiza un movimiento incorrecto
-
getMovement
public Movement getMovement(int source, int dest) throws java.lang.IllegalArgumentException
Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino- Parameters:
- source - casilla de origen
- dest - casilla de destino
- Returns:
- el movimiento atómico a realizar (up, down, left, right)
- Throws:
- java.lang.IllegalArgumentException
-
getMovement
public Movement getMovement(int x1, int y1, int x2, int y2) throws java.lang.IllegalArgumentException
Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino- Parameters:
- x1 - la coordenada x del origen
- y1 - la coodenada y del origen
- x2 - la coordenada x del destino
- y2 - la coordenada y del destino
- Returns:
- el movimiento atómico a realizar (up, down, left, right)
- Throws:
- java.lang.IllegalArgumentException
-
getWatchArea
public java.util.List<java.lang.Integer> getWatchArea(int point)
Devuelve una lista de casillas en coordenadas unidimensionales que constituyen el contorno de radio 1 de una casilla dada Se usa para determinar el área de vigilancia de un monstruo- Parameters:
- point - la casilla
- Returns:
- una lista de casillas en coordenadas unidimensioanales
-
getWatchArea2D
public java.util.List<int[]> getWatchArea2D(int x, int y)Devuelve una lista de casillas en coordenadas 2D que constituyen el contorno de radio 1 de una casilla dada Se usa para determinar el área de vigilancia de un monstruo- Parameters:
- x - la coordenada x
- y - la coordenada y
- Returns:
- una lista de casillas en coordenadas unidimensioanales
-
getMovableArea
public java.util.List<java.lang.Integer> getMovableArea(int point)
Devuelve una lista de casillas en coordenadas unidimensionales que constituyen las casillas dentro del mapa a las que se puede mover el ladrón- Parameters:
- point - la casilla
- Returns:
- una lista de casillas en coordenadas unidimensioanales
-
getMovableArea
public java.util.List<int[]> getMovableArea(int x, int y)Devuelve una lista de casillas en coordenadas 2d que constituyen las casillas dentro del mapa a las que se puede mover el ladrón- Parameters:
- x - la coordenada x
- y - la coordenada y
- Returns:
- una lista de casillas en coordenadas unidimensioanales
-
getWidth
public int getWidth()
Devuelve la anchura del mapa- Returns:
- la anchura del mapa
-
getHeight
public int getHeight()
Devuelve la altura del mapa- Returns:
- la altura del mapa
-
isWalkable
public boolean isWalkable(int x, int y) throws java.lang.IllegalArgumentExceptionDetermina si la casilla del mapa es pisable o no- Parameters:
- x -
- y -
- Returns:
- true si la casilla es pisable, false en otro caso
- Throws:
- java.lang.IllegalArgumentException
-
isWalkable
public boolean isWalkable(int point)
Determina si la casilla del mapa es pisable o no- Parameters:
- point - es la casilla representada en espacion 1-dimensional
- Returns:
- true si la casilla es pisable, false en otro caso
- Throws:
- java.lang.IllegalArgumentException
-
hasEnemy
public boolean hasEnemy(int x, int y)Determina si la casilla del mapa contiene un enemigo o no- Parameters:
- x -
- y -
- Returns:
- true si la casilla contiene un monstruo, false en otro caso
- Throws:
- java.lang.IllegalArgumentException
-
hasEnemy
public boolean hasEnemy(int point) throws java.lang.IllegalArgumentExceptionDetermina si la casilla del mapa contiene un enemigo o no- Parameters:
- point - es la casilla en espacio 1-dimensional
- Returns:
- true si la casilla contiene un monstruo, false en otro caso
- Throws:
- java.lang.IllegalArgumentException
-
hasTreasure
public boolean hasTreasure(int x, int y) throws java.lang.IllegalArgumentExceptionDetermina si la casilla del mapa contiene un tesoro o no- Parameters:
- x -
- y -
- Returns:
- true si la casilla tiene un tesoro, false en caso contrario
- Throws:
- java.lang.IllegalArgumentException
-
hasTreasure
public boolean hasTreasure(int point)
Determina si la casilla del mapa contiene un tesoro o no- Parameters:
- point - es la casilla en espacion 1-dimensional
- Returns:
- true si la casilla tiene un tesoro, false en caso contrario
- Throws:
- java.lang.IllegalArgumentException
-
hasExit
public boolean hasExit(int x, int y) throws java.lang.IllegalArgumentExceptionDetermina si la casilla contiene una salida o no- Parameters:
- x -
- y -
- Returns:
- true si la casilla tiene una salida, false en caso contrario
- Throws:
- java.lang.IllegalArgumentException
-
hasExit
public boolean hasExit(int point)
Determina si la coordenada en una dimensión es válida o no- Parameters:
- point - la coordenada en una dimensión
- Returns:
- true si la casilla tiene salida, false en caso constrario
-
isStartingPoint
public boolean isStartingPoint(int x, int y) throws java.lang.IllegalArgumentExceptionDetermina si la casilla es el punto de inicio del ladrón- Parameters:
- x -
- y -
- Returns:
- true si la casilla es de salida, false en caso contrario
- Throws:
- java.lang.IllegalArgumentException
-
isStartingPoint
public boolean isStartingPoint(int point)
Determina si la casilla es el punto de inicio del ladrón- Parameters:
- point - es la casilla en coordenadas 1-dimensionales
- Returns:
- true si la casilla es de salida, false en caso contrario
- Throws:
- java.lang.IllegalArgumentException
-
isValidPlan
public boolean isValidPlan(java.util.List<Movement> plan)
Dado un plan, determina si éste es válido para acabar el nivel- Parameters:
- plan - compuesto por una lista ordenada de movimientos
- Returns:
- true si es válido para acabar el nivel, false en caso contrario
-
main
public static void main(java.lang.String[] args)
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/class-use/Dungeon.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.game.map.Dungeon
-
Packages that use Dungeon
Package Description edu.uoc.mecm.eda.player -
-
Uses of Dungeon in edu.uoc.mecm.eda.player
Constructors in edu.uoc.mecm.eda.player with parameters of type DungeonConstructor and Description Thief(Dungeon m) Constructor de la clase
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/class-use/Movement.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.game.map.Movement
-
Packages that use Movement
Package Description edu.uoc.mecm.eda.game.map edu.uoc.mecm.eda.player -
-
Uses of Movement in edu.uoc.mecm.eda.game.map
Methods in edu.uoc.mecm.eda.game.map that return Movement
Methods in edu.uoc.mecm.eda.game.map with parameters of type MovementModifier and Type Method and Description Movement Dungeon.getMovement(int source, int dest) Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino Movement Dungeon.getMovement(int x1, int y1, int x2, int y2) Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino static Movement Movement.valueOf(java.lang.String name) Returns the enum constant of this type with the specified name. static Movement[] Movement.values() Returns an array containing the constants of this enum type, in the order they are declared.
Method parameters in edu.uoc.mecm.eda.game.map with type arguments of type MovementModifier and Type Method and Description boolean Dungeon.canMove(int x, int y, Movement m) Determina si se puede mover desde el punto indicado con el movimiento indicado boolean Dungeon.canMove(int point, Movement m) Determina si se puede mover desde el punto indicado con el movimiento indicado int[] Dungeon.move(int x, int y, Movement m) Dado un punto de origen, realiza un movimiento int Dungeon.move(int point, Movement m) Dado un punto de origen, realiza un movimiento Modifier and Type Method and Description boolean Dungeon.isValidPlan(java.util.List<Movement> plan) Dado un plan, determina si éste es válido para acabar el nivel -
Uses of Movement in edu.uoc.mecm.eda.player
Methods in edu.uoc.mecm.eda.player that return types with arguments of type MovementModifier and Type Method and Description java.util.List<Movement> Thief.getPlan()
-
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/package-use.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Package edu.uoc.mecm.eda.game.map
-
Packages that use edu.uoc.mecm.eda.game.map
Package Description edu.uoc.mecm.eda.game.map edu.uoc.mecm.eda.player -
Classes in edu.uoc.mecm.eda.game.map used by edu.uoc.mecm.eda.game.map
Class and Description Movement Clase de tipo enumeración par los posibles movimientos del ladrón -
Classes in edu.uoc.mecm.eda.game.map used by edu.uoc.mecm.eda.player
Class and Description Dungeon Movement Clase de tipo enumeración par los posibles movimientos del ladrón
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/Movement.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
- Summary:
- Nested |
- Enum Constants |
- Field |
- Method
- Detail:
- Enum Constants |
- Field |
- Method
Enum Movement
- java.lang.Object
-
- java.lang.Enum<Movement>
-
- edu.uoc.mecm.eda.game.map.Movement
-
- All Implemented Interfaces:
- java.io.Serializable, java.lang.Comparable<Movement>
public enum Movement extends java.lang.Enum<Movement>
Clase de tipo enumeración par los posibles movimientos del ladrón
-
-
Method Summary
All Methods Static Methods Concrete MethodsModifier and Type Method and Description static Movement valueOf(java.lang.String name) Returns the enum constant of this type with the specified name. static Movement[] values() Returns an array containing the constants of this enum type, in the order they are declared.
-
-
-
Enum Constant Detail
-
LEFT
public static final Movement LEFT
-
RIGHT
public static final Movement RIGHT
-
UP
public static final Movement UP
-
DOWN
public static final Movement DOWN
-
-
Method Detail
-
values
public static Movement[] values()
Returns an array containing the constants of this enum type, in the order they are declared. This method may be used to iterate over the constants as follows:for (Movement c : Movement.values()) System.out.println(c);
- Returns:
- an array containing the constants of this enum type, in the order they are declared
-
valueOf
public static Movement valueOf(java.lang.String name)
Returns the enum constant of this type with the specified name. The string must match exactly an identifier used to declare an enum constant in this type. (Extraneous whitespace characters are not permitted.)- Parameters:
- name - the name of the enum constant to be returned.
- Returns:
- the enum constant with the specified name
- Throws:
- java.lang.IllegalArgumentException - if this enum type has no constant with the specified name
- java.lang.NullPointerException - if the argument is null
-
-
- Prev Class
- Next Class
- Summary:
- Nested |
- Enum Constants |
- Field |
- Method
- Detail:
- Enum Constants |
- Field |
- Method
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/package-frame.html
edu.uoc.mecm.eda.game.map
Classes
Enums
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/package-summary.html
JavaScript is disabled on your browser. Skip navigation links- Prev Package
- Next Package
Package edu.uoc.mecm.eda.game.map
-
Class Summary
Class Description Dungeon -
Enum Summary
Enum Description Movement Clase de tipo enumeración par los posibles movimientos del ladrón
- Prev Package
- Next Package
M0.506_PEC4/doc/edu/uoc/mecm/eda/game/map/package-tree.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
Hierarchy For Package edu.uoc.mecm.eda.game.map
Package Hierarchies:Class Hierarchy
- java.lang.Object
- edu.uoc.mecm.eda.game.map.Dungeon
Enum Hierarchy
- java.lang.Object
- java.lang.Enum<E> (implements java.lang.Comparable<T>, java.io.Serializable)
- edu.uoc.mecm.eda.game.map.Movement
- java.lang.Enum<E> (implements java.lang.Comparable<T>, java.io.Serializable)
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/class-use/AnEvenNumber.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.search.AnEvenNumber
No usage of edu.uoc.mecm.eda.search.AnEvenNumber Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/class-use/ClosestPrimeNumber.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.search.ClosestPrimeNumber
No usage of edu.uoc.mecm.eda.search.ClosestPrimeNumber Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/AnEvenNumber.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class AnEvenNumber
- java.lang.Object
-
- edu.uoc.mecm.eda.search.AnEvenNumber
-
public class AnEvenNumber extends java.lang.Object
-
-
Constructor Summary
ConstructorsConstructor and Description AnEvenNumber(Graph g) Constructor de la clase
-
Method Summary
All Methods Static Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.lang.Integer getAnEvenNumber(int v, int distance) Obtiene un vértice par a una distancia menor a la especificada por parámetro del vértice inicial static void main(java.lang.String[] args)
-
-
-
Constructor Detail
-
AnEvenNumber
public AnEvenNumber(Graph g)
Constructor de la clase- Parameters:
- g - el grafo sobre el que realizar las busquedas
-
-
Method Detail
-
getAnEvenNumber
public java.lang.Integer getAnEvenNumber(int v, int distance) throws java.lang.IllegalArgumentExceptionObtiene un vértice par a una distancia menor a la especificada por parámetro del vértice inicial- Parameters:
- v - el vértice inicial sobre el que realizar la búsqueda
- distance - la distancia máxima a la que puede estar el vértice par
- Returns:
- un vértice par a una distancia menor que la especificada, null si no hay ninguno que cumpla la condición
- Throws:
- java.lang.IllegalArgumentException
-
main
public static void main(java.lang.String[] args)
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/ClosestPrimeNumber.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class ClosestPrimeNumber
- java.lang.Object
-
- edu.uoc.mecm.eda.search.ClosestPrimeNumber
-
public class ClosestPrimeNumber extends java.lang.Object
Clase encargada de encontrar el vértice primo (considerar que los vértices representan enteros) más cercano
-
-
Constructor Summary
ConstructorsConstructor and Description ClosestPrimeNumber(Graph g) Constructor de la clase
-
Method Summary
All Methods Static Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.lang.Integer getClosestFrom(int v) Obtiene el vértice primo más cercano al vértice pasado por parámetro static void main(java.lang.String[] args)
-
-
-
Constructor Detail
-
ClosestPrimeNumber
public ClosestPrimeNumber(Graph g)
Constructor de la clase- Parameters:
- g - el grafo base sobre el que realizar busquedas
-
-
Method Detail
-
getClosestFrom
public java.lang.Integer getClosestFrom(int v) throws java.lang.IllegalArgumentExceptionObtiene el vértice primo más cercano al vértice pasado por parámetro- Parameters:
- v - el vértice sobre el que iniciar la busqueda
- Returns:
- el primo más cercano al vértice de origen, null si no hay ninguno o no está conectado con v
- Throws:
- java.lang.IllegalArgumentException - en caso de que el vértice no exista en el grafo
-
main
public static void main(java.lang.String[] args)
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/package-use.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Package edu.uoc.mecm.eda.search
No usage of edu.uoc.mecm.eda.search Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/package-summary.html
JavaScript is disabled on your browser. Skip navigation linksPackage edu.uoc.mecm.eda.search
-
Class Summary
Class Description AnEvenNumber ClosestPrimeNumber Clase encargada de encontrar el vértice primo (considerar que los vértices representan enteros) más cercano
M0.506_PEC4/doc/edu/uoc/mecm/eda/search/package-tree.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
Hierarchy For Package edu.uoc.mecm.eda.search
Package Hierarchies:Class Hierarchy
- java.lang.Object
- edu.uoc.mecm.eda.search.AnEvenNumber
- edu.uoc.mecm.eda.search.ClosestPrimeNumber
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/RestrictedBreadthFirstPaths.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class RestrictedBreadthFirstPaths
- java.lang.Object
-
- edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
-
public class RestrictedBreadthFirstPaths extends java.lang.Object
Clase modificada que realiza un bfs sobre el grafo para encontrar el camino más corto desde un vértice de origen a un conjunto de vértices de interés No usamos Dijkstra ya que no sería necesario (todos los enlaces tienen el mismo coste) y no es necesario calcular la distancia a todas las casillas, tan sólo a las que contienen tesoros y salidas
-
-
Constructor Summary
ConstructorsConstructor and Description RestrictedBreadthFirstPaths(Graph G, int s, java.util.Set<java.lang.Integer> interestVertex) Calcula el camino más corto entre el vértice origen y los puntos de interés
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description int distTo(int v) Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v? boolean hasPathTo(int v) Is there a path between the source vertex s (or sources) and vertex v? java.util.List<java.lang.Integer> pathFrom(int v, boolean addSource) Returns a shortest path between the source vertex s (or sources) and v, or null if no such path. java.util.List<java.lang.Integer> pathTo(int v, boolean addSource) Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.
-
-
-
Constructor Detail
-
RestrictedBreadthFirstPaths
public RestrictedBreadthFirstPaths(Graph G, int s, java.util.Set<java.lang.Integer> interestVertex)
Calcula el camino más corto entre el vértice origen y los puntos de interés- Parameters:
- G - el grafo
- s - el vértice de origen
- interestVertex - el conjunto de vértices de interés
-
-
Method Detail
-
hasPathTo
public boolean hasPathTo(int v)
Is there a path between the source vertex s (or sources) and vertex v?- Parameters:
- v - the vertex
- Returns:
- true if there is a path, and false otherwise
-
distTo
public int distTo(int v)
Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?- Parameters:
- v - the vertex
- Returns:
- the number of edges in a shortest path
-
pathTo
public java.util.List<java.lang.Integer> pathTo(int v, boolean addSource)Returns a shortest path between the source vertex s (or sources) and v, or null if no such path. This path goes from s to v.- Parameters:
- v - the vertex
- Returns:
- the sequence of vertices on a shortest path, as an Iterable
-
pathFrom
public java.util.List<java.lang.Integer> pathFrom(int v, boolean addSource)Returns a shortest path between the source vertex s (or sources) and v, or null if no such path. This path goes from v to s.- Parameters:
- v - the vertex
- Returns:
- the sequence of vertices on a shortest path, as an Iterable
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/class-use/RestrictedBreadthFirstPaths.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
No usage of edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/class-use/Thief.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Class edu.uoc.mecm.eda.player.Thief
No usage of edu.uoc.mecm.eda.player.Thief Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/package-use.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Uses of Package edu.uoc.mecm.eda.player
No usage of edu.uoc.mecm.eda.player Skip navigation links- Prev
- Next
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/package-summary.html
JavaScript is disabled on your browser. Skip navigation linksPackage edu.uoc.mecm.eda.player
-
Class Summary
Class Description RestrictedBreadthFirstPaths Clase modificada que realiza un bfs sobre el grafo para encontrar el camino más corto desde un vértice de origen a un conjunto de vértices de interés No usamos Dijkstra ya que no sería necesario (todos los enlaces tienen el mismo coste) y no es necesario calcular la distancia a todas las casillas, tan sólo a las que contienen tesoros y salidas Thief
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/package-tree.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
Hierarchy For Package edu.uoc.mecm.eda.player
Package Hierarchies:Class Hierarchy
- java.lang.Object
- edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- edu.uoc.mecm.eda.player.Thief
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/edu/uoc/mecm/eda/player/Thief.html
JavaScript is disabled on your browser. Skip navigation links- Prev Class
- Next Class
Class Thief
- java.lang.Object
-
- edu.uoc.mecm.eda.player.Thief
-
public class Thief extends java.lang.Object
-
-
Constructor Summary
ConstructorsConstructor and Description Thief(Dungeon m) Constructor de la clase
-
Method Summary
All Methods Instance Methods Concrete MethodsModifier and Type Method and Description java.util.List<Movement> getPlan()
-
-
-
Constructor Detail
-
Thief
public Thief(Dungeon m)
Constructor de la clase- Parameters:
- m - el nivel a resolver
-
-
Method Detail
-
getPlan
public java.util.List<Movement> getPlan()
-
-
- Prev Class
- Next Class
M0.506_PEC4/doc/constant-values.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
Constant Field Values
Contents
Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
M0.506_PEC4/doc/overview-tree.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
Hierarchy For All Packages
Package Hierarchies:Class Hierarchy
- java.lang.Object
- edu.uoc.mecm.eda.utils.AcyclicSP
- edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- edu.uoc.mecm.eda.search.AnEvenNumber
- edu.uoc.mecm.eda.utils.Bag<Item> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.utils.BellmanFordSP
- edu.uoc.mecm.eda.utils.Bipartite
- edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- edu.uoc.mecm.eda.utils.BreadthFirstPaths
- edu.uoc.mecm.eda.utils.CC
- edu.uoc.mecm.eda.search.ClosestPrimeNumber
- edu.uoc.mecm.eda.utils.Cycle
- edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
- edu.uoc.mecm.eda.utils.DepthFirstOrder
- edu.uoc.mecm.eda.utils.DepthFirstPaths
- edu.uoc.mecm.eda.utils.DepthFirstSearch
- edu.uoc.mecm.eda.utils.Digraph
- edu.uoc.mecm.eda.utils.DijkstraSP
- edu.uoc.mecm.eda.utils.DirectedCycle
- edu.uoc.mecm.eda.utils.DirectedDFS
- edu.uoc.mecm.eda.utils.DirectedEdge
- edu.uoc.mecm.eda.game.map.Dungeon
- edu.uoc.mecm.eda.utils.Edge (implements java.lang.Comparable<T>)
- edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
- edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- edu.uoc.mecm.eda.utils.FloydWarshall
- edu.uoc.mecm.eda.utils.Graph
- edu.uoc.mecm.eda.utils.In
- edu.uoc.mecm.eda.utils.IndexMinPQ<Key> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.utils.KosarajuSharirSCC
- edu.uoc.mecm.eda.utils.Queue<Item> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- edu.uoc.mecm.eda.utils.Stack<Item> (implements java.lang.Iterable<T>)
- edu.uoc.mecm.eda.player.Thief
- edu.uoc.mecm.eda.utils.Topological
- edu.uoc.mecm.eda.utils.TransitiveClosure
Enum Hierarchy
- java.lang.Object
- java.lang.Enum<E> (implements java.lang.Comparable<T>, java.io.Serializable)
- edu.uoc.mecm.eda.game.map.Movement
- java.lang.Enum<E> (implements java.lang.Comparable<T>, java.io.Serializable)
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
M0.506_PEC4/doc/index.html
M0.506_PEC4/doc/allclasses-noframe.html
All Classes
- AcyclicSP
- AdjMatrixEdgeWeightedDigraph
- AnEvenNumber
- Bag
- BellmanFordSP
- Bipartite
- BreadthFirstDirectedPaths
- BreadthFirstPaths
- CC
- ClosestPrimeNumber
- Cycle
- DepthFirstDirectedPaths
- DepthFirstOrder
- DepthFirstPaths
- DepthFirstSearch
- Digraph
- DijkstraSP
- DirectedCycle
- DirectedDFS
- DirectedEdge
- Dungeon
- Edge
- EdgeWeightedDigraph
- EdgeWeightedDirectedCycle
- EdgeWeightedGraph
- FloydWarshall
- Graph
- In
- IndexMinPQ
- KosarajuSharirSCC
- Movement
- Queue
- RestrictedBreadthFirstPaths
- Stack
- Thief
- Topological
- TransitiveClosure
M0.506_PEC4/doc/deprecated-list.html
JavaScript is disabled on your browser. Skip navigation links- Prev
- Next
Deprecated API
Contents
-
Deprecated Methods
Method and Description edu.uoc.mecm.eda.utils.IndexMinPQ.change(int, Key) Replaced by changeKey() edu.uoc.mecm.eda.utils.In.readDoubles() Clearer to use StdIn#readAllDoubles() edu.uoc.mecm.eda.utils.In.readDoubles(String) Clearer to use new In(filename).In.readAllDoubles() edu.uoc.mecm.eda.utils.In.readInts() Clearer to use StdIn#readAllInts() edu.uoc.mecm.eda.utils.In.readInts(String) Clearer to use new In(filename).In.readAllInts() edu.uoc.mecm.eda.utils.In.readStrings() Clearer to use StdIn#readAllStrings() edu.uoc.mecm.eda.utils.In.readStrings(String) Clearer to use new In(filename).In.readAllStrings()
- Prev
- Next
M0.506_PEC4/doc/script.js
function show(type) { count = 0; for (var key in methods) { var row = document.getElementById(key); if ((methods[key] & type) != 0) { row.style.display = ''; row.className = (count++ % 2) ? rowColor : altColor; } else row.style.display = 'none'; } updateTabs(type); } function updateTabs(type) { for (var value in tabs) { var sNode = document.getElementById(tabs[value][0]); var spanNode = sNode.firstChild; if (value == type) { sNode.className = activeTableTab; spanNode.innerHTML = tabs[value][1]; } else { sNode.className = tableTab; spanNode.innerHTML = "<a href=\"javascript:show("+ value + ");\">" + tabs[value][1] + "</a>"; } } }
M0.506_PEC4/doc/stylesheet.css
/* Javadoc style sheet */ /* Overall document style */ @import url('resources/fonts/dejavu.css'); body { background-color:#ffffff; color:#353833; font-family:'DejaVu Sans', Arial, Helvetica, sans-serif; font-size:14px; margin:0; } a:link, a:visited { text-decoration:none; color:#4A6782; } a:hover, a:focus { text-decoration:none; color:#bb7a2a; } a:active { text-decoration:none; color:#4A6782; } a[name] { color:#353833; } a[name]:hover { text-decoration:none; color:#353833; } pre { font-family:'DejaVu Sans Mono', monospace; font-size:14px; } h1 { font-size:20px; } h2 { font-size:18px; } h3 { font-size:16px; font-style:italic; } h4 { font-size:13px; } h5 { font-size:12px; } h6 { font-size:11px; } ul { list-style-type:disc; } code, tt { font-family:'DejaVu Sans Mono', monospace; font-size:14px; padding-top:4px; margin-top:8px; line-height:1.4em; } dt code { font-family:'DejaVu Sans Mono', monospace; font-size:14px; padding-top:4px; } table tr td dt code { font-family:'DejaVu Sans Mono', monospace; font-size:14px; vertical-align:top; padding-top:4px; } sup { font-size:8px; } /* Document title and Copyright styles */ .clear { clear:both; height:0px; overflow:hidden; } .aboutLanguage { float:right; padding:0px 21px; font-size:11px; z-index:200; margin-top:-9px; } .legalCopy { margin-left:.5em; } .bar a, .bar a:link, .bar a:visited, .bar a:active { color:#FFFFFF; text-decoration:none; } .bar a:hover, .bar a:focus { color:#bb7a2a; } .tab { background-color:#0066FF; color:#ffffff; padding:8px; width:5em; font-weight:bold; } /* Navigation bar styles */ .bar { background-color:#4D7A97; color:#FFFFFF; padding:.8em .5em .4em .8em; height:auto;/*height:1.8em;*/ font-size:11px; margin:0; } .topNav { background-color:#4D7A97; color:#FFFFFF; float:left; padding:0; width:100%; clear:right; height:2.8em; padding-top:10px; overflow:hidden; font-size:12px; } .bottomNav { margin-top:10px; background-color:#4D7A97; color:#FFFFFF; float:left; padding:0; width:100%; clear:right; height:2.8em; padding-top:10px; overflow:hidden; font-size:12px; } .subNav { background-color:#dee3e9; float:left; width:100%; overflow:hidden; font-size:12px; } .subNav div { clear:left; float:left; padding:0 0 5px 6px; text-transform:uppercase; } ul.navList, ul.subNavList { float:left; margin:0 25px 0 0; padding:0; } ul.navList li{ list-style:none; float:left; padding: 5px 6px; text-transform:uppercase; } ul.subNavList li{ list-style:none; float:left; } .topNav a:link, .topNav a:active, .topNav a:visited, .bottomNav a:link, .bottomNav a:active, .bottomNav a:visited { color:#FFFFFF; text-decoration:none; text-transform:uppercase; } .topNav a:hover, .bottomNav a:hover { text-decoration:none; color:#bb7a2a; text-transform:uppercase; } .navBarCell1Rev { background-color:#F8981D; color:#253441; margin: auto 5px; } .skipNav { position:absolute; top:auto; left:-9999px; overflow:hidden; } /* Page header and footer styles */ .header, .footer { clear:both; margin:0 20px; padding:5px 0 0 0; } .indexHeader { margin:10px; position:relative; } .indexHeader span{ margin-right:15px; } .indexHeader h1 { font-size:13px; } .title { color:#2c4557; margin:10px 0; } .subTitle { margin:5px 0 0 0; } .header ul { margin:0 0 15px 0; padding:0; } .footer ul { margin:20px 0 5px 0; } .header ul li, .footer ul li { list-style:none; font-size:13px; } /* Heading styles */ div.details ul.blockList ul.blockList ul.blockList li.blockList h4, div.details ul.blockList ul.blockList ul.blockListLast li.blockList h4 { background-color:#dee3e9; border:1px solid #d0d9e0; margin:0 0 6px -8px; padding:7px 5px; } ul.blockList ul.blockList ul.blockList li.blockList h3 { background-color:#dee3e9; border:1px solid #d0d9e0; margin:0 0 6px -8px; padding:7px 5px; } ul.blockList ul.blockList li.blockList h3 { padding:0; margin:15px 0; } ul.blockList li.blockList h2 { padding:0px 0 20px 0; } /* Page layout container styles */ .contentContainer, .sourceContainer, .classUseContainer, .serializedFormContainer, .constantValuesContainer { clear:both; padding:10px 20px; position:relative; } .indexContainer { margin:10px; position:relative; font-size:12px; } .indexContainer h2 { font-size:13px; padding:0 0 3px 0; } .indexContainer ul { margin:0; padding:0; } .indexContainer ul li { list-style:none; padding-top:2px; } .contentContainer .description dl dt, .contentContainer .details dl dt, .serializedFormContainer dl dt { font-size:12px; font-weight:bold; margin:10px 0 0 0; color:#4E4E4E; } .contentContainer .description dl dd, .contentContainer .details dl dd, .serializedFormContainer dl dd { margin:5px 0 10px 0px; font-size:14px; font-family:'DejaVu Sans Mono',monospace; } .serializedFormContainer dl.nameValue dt { margin-left:1px; font-size:1.1em; display:inline; font-weight:bold; } .serializedFormContainer dl.nameValue dd { margin:0 0 0 1px; font-size:1.1em; display:inline; } /* List styles */ ul.horizontal li { display:inline; font-size:0.9em; } ul.inheritance { margin:0; padding:0; } ul.inheritance li { display:inline; list-style:none; } ul.inheritance li ul.inheritance { margin-left:15px; padding-left:15px; padding-top:1px; } ul.blockList, ul.blockListLast { margin:10px 0 10px 0; padding:0; } ul.blockList li.blockList, ul.blockListLast li.blockList { list-style:none; margin-bottom:15px; line-height:1.4; } ul.blockList ul.blockList li.blockList, ul.blockList ul.blockListLast li.blockList { padding:0px 20px 5px 10px; border:1px solid #ededed; background-color:#f8f8f8; } ul.blockList ul.blockList ul.blockList li.blockList, ul.blockList ul.blockList ul.blockListLast li.blockList { padding:0 0 5px 8px; background-color:#ffffff; border:none; } ul.blockList ul.blockList ul.blockList ul.blockList li.blockList { margin-left:0; padding-left:0; padding-bottom:15px; border:none; } ul.blockList ul.blockList ul.blockList ul.blockList li.blockListLast { list-style:none; border-bottom:none; padding-bottom:0; } table tr td dl, table tr td dl dt, table tr td dl dd { margin-top:0; margin-bottom:1px; } /* Table styles */ .overviewSummary, .memberSummary, .typeSummary, .useSummary, .constantsSummary, .deprecatedSummary { width:100%; border-left:1px solid #EEE; border-right:1px solid #EEE; border-bottom:1px solid #EEE; } .overviewSummary, .memberSummary { padding:0px; } .overviewSummary caption, .memberSummary caption, .typeSummary caption, .useSummary caption, .constantsSummary caption, .deprecatedSummary caption { position:relative; text-align:left; background-repeat:no-repeat; color:#253441; font-weight:bold; clear:none; overflow:hidden; padding:0px; padding-top:10px; padding-left:1px; margin:0px; white-space:pre; } .overviewSummary caption a:link, .memberSummary caption a:link, .typeSummary caption a:link, .useSummary caption a:link, .constantsSummary caption a:link, .deprecatedSummary caption a:link, .overviewSummary caption a:hover, .memberSummary caption a:hover, .typeSummary caption a:hover, .useSummary caption a:hover, .constantsSummary caption a:hover, .deprecatedSummary caption a:hover, .overviewSummary caption a:active, .memberSummary caption a:active, .typeSummary caption a:active, .useSummary caption a:active, .constantsSummary caption a:active, .deprecatedSummary caption a:active, .overviewSummary caption a:visited, .memberSummary caption a:visited, .typeSummary caption a:visited, .useSummary caption a:visited, .constantsSummary caption a:visited, .deprecatedSummary caption a:visited { color:#FFFFFF; } .overviewSummary caption span, .memberSummary caption span, .typeSummary caption span, .useSummary caption span, .constantsSummary caption span, .deprecatedSummary caption span { white-space:nowrap; padding-top:5px; padding-left:12px; padding-right:12px; padding-bottom:7px; display:inline-block; float:left; background-color:#F8981D; border: none; height:16px; } .memberSummary caption span.activeTableTab span { white-space:nowrap; padding-top:5px; padding-left:12px; padding-right:12px; margin-right:3px; display:inline-block; float:left; background-color:#F8981D; height:16px; } .memberSummary caption span.tableTab span { white-space:nowrap; padding-top:5px; padding-left:12px; padding-right:12px; margin-right:3px; display:inline-block; float:left; background-color:#4D7A97; height:16px; } .memberSummary caption span.tableTab, .memberSummary caption span.activeTableTab { padding-top:0px; padding-left:0px; padding-right:0px; background-image:none; float:none; display:inline; } .overviewSummary .tabEnd, .memberSummary .tabEnd, .typeSummary .tabEnd, .useSummary .tabEnd, .constantsSummary .tabEnd, .deprecatedSummary .tabEnd { display:none; width:5px; position:relative; float:left; background-color:#F8981D; } .memberSummary .activeTableTab .tabEnd { display:none; width:5px; margin-right:3px; position:relative; float:left; background-color:#F8981D; } .memberSummary .tableTab .tabEnd { display:none; width:5px; margin-right:3px; position:relative; background-color:#4D7A97; float:left; } .overviewSummary td, .memberSummary td, .typeSummary td, .useSummary td, .constantsSummary td, .deprecatedSummary td { text-align:left; padding:0px 0px 12px 10px; } th.colOne, th.colFirst, th.colLast, .useSummary th, .constantsSummary th, td.colOne, td.colFirst, td.colLast, .useSummary td, .constantsSummary td{ vertical-align:top; padding-right:0px; padding-top:8px; padding-bottom:3px; } th.colFirst, th.colLast, th.colOne, .constantsSummary th { background:#dee3e9; text-align:left; padding:8px 3px 3px 7px; } td.colFirst, th.colFirst { white-space:nowrap; font-size:13px; } td.colLast, th.colLast { font-size:13px; } td.colOne, th.colOne { font-size:13px; } .overviewSummary td.colFirst, .overviewSummary th.colFirst, .useSummary td.colFirst, .useSummary th.colFirst, .overviewSummary td.colOne, .overviewSummary th.colOne, .memberSummary td.colFirst, .memberSummary th.colFirst, .memberSummary td.colOne, .memberSummary th.colOne, .typeSummary td.colFirst{ width:25%; vertical-align:top; } td.colOne a:link, td.colOne a:active, td.colOne a:visited, td.colOne a:hover, td.colFirst a:link, td.colFirst a:active, td.colFirst a:visited, td.colFirst a:hover, td.colLast a:link, td.colLast a:active, td.colLast a:visited, td.colLast a:hover, .constantValuesContainer td a:link, .constantValuesContainer td a:active, .constantValuesContainer td a:visited, .constantValuesContainer td a:hover { font-weight:bold; } .tableSubHeadingColor { background-color:#EEEEFF; } .altColor { background-color:#FFFFFF; } .rowColor { background-color:#EEEEEF; } /* Content styles */ .description pre { margin-top:0; } .deprecatedContent { margin:0; padding:10px 0; } .docSummary { padding:0; } ul.blockList ul.blockList ul.blockList li.blockList h3 { font-style:normal; } div.block { font-size:14px; font-family:'DejaVu Serif', Georgia, "Times New Roman", Times, serif; } td.colLast div { padding-top:0px; } td.colLast a { padding-bottom:3px; } /* Formatting effect styles */ .sourceLineNo { color:green; padding:0 30px 0 0; } h1.hidden { visibility:hidden; overflow:hidden; font-size:10px; } .block { display:block; margin:3px 10px 2px 0px; color:#474747; } .deprecatedLabel, .descfrmTypeLabel, .memberNameLabel, .memberNameLink, .overrideSpecifyLabel, .packageHierarchyLabel, .paramLabel, .returnLabel, .seeLabel, .simpleTagLabel, .throwsLabel, .typeNameLabel, .typeNameLink { font-weight:bold; } .deprecationComment, .emphasizedPhrase, .interfaceName { font-style:italic; } div.block div.block span.deprecationComment, div.block div.block span.emphasizedPhrase, div.block div.block span.interfaceName { font-style:normal; } div.contentContainer ul.blockList li.blockList h2{ padding-bottom:0px; }
M0.506_PEC4/doc/overview-summary.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
| Package | Description |
|---|---|
| edu.uoc.mecm.eda.game.map | |
| edu.uoc.mecm.eda.player | |
| edu.uoc.mecm.eda.search | |
| edu.uoc.mecm.eda.utils |
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
M0.506_PEC4/doc/help-doc.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
How This API Document Is Organized
This API (Application Programming Interface) document has pages corresponding to the items in the navigation bar, described as follows.-
Overview
The Overview page is the front page of this API document and provides a list of all packages with a summary for each. This page can also contain an overall description of the set of packages.
-
Package
Each package has a page that contains a list of its classes and interfaces, with a summary for each. This page can contain six categories:
- Interfaces (italic)
- Classes
- Enums
- Exceptions
- Errors
- Annotation Types
-
Class/Interface
Each class, interface, nested class and nested interface has its own separate page. Each of these pages has three sections consisting of a class/interface description, summary tables, and detailed member descriptions:
- Class inheritance diagram
- Direct Subclasses
- All Known Subinterfaces
- All Known Implementing Classes
- Class/interface declaration
- Class/interface description
- Nested Class Summary
- Field Summary
- Constructor Summary
- Method Summary
- Field Detail
- Constructor Detail
- Method Detail
Each summary entry contains the first sentence from the detailed description for that item. The summary entries are alphabetical, while the detailed descriptions are in the order they appear in the source code. This preserves the logical groupings established by the programmer.
-
Annotation Type
Each annotation type has its own separate page with the following sections:
- Annotation Type declaration
- Annotation Type description
- Required Element Summary
- Optional Element Summary
- Element Detail
-
Enum
Each enum has its own separate page with the following sections:
- Enum declaration
- Enum description
- Enum Constant Summary
- Enum Constant Detail
-
Use
Each documented package, class and interface has its own Use page. This page describes what packages, classes, methods, constructors and fields use any part of the given class or package. Given a class or interface A, its Use page includes subclasses of A, fields declared as A, methods that return A, and methods and constructors with parameters of type A. You can access this page by first going to the package, class or interface, then clicking on the "Use" link in the navigation bar.
-
Tree (Class Hierarchy)
There is a Class Hierarchy page for all packages, plus a hierarchy for each package. Each hierarchy page contains a list of classes and a list of interfaces. The classes are organized by inheritance structure starting with java.lang.Object. The interfaces do not inherit from java.lang.Object.
- When viewing the Overview page, clicking on "Tree" displays the hierarchy for all packages.
- When viewing a particular package, class or interface page, clicking "Tree" displays the hierarchy for only that package.
-
Deprecated API
The Deprecated API page lists all of the API that have been deprecated. A deprecated API is not recommended for use, generally due to improvements, and a replacement API is usually given. Deprecated APIs may be removed in future implementations.
-
Index
The Index contains an alphabetic list of all classes, interfaces, constructors, methods, and fields.
-
Prev/Next
These links take you to the next or previous class, interface, package, or related page.
-
Frames/No Frames
These links show and hide the HTML frames. All pages are available with or without frames.
-
All Classes
The All Classes link shows all classes and interfaces except non-static nested types.
-
Serialized Form
Each serializable or externalizable class has a description of its serialization fields and methods. This information is of interest to re-implementors, not to developers using the API. While there is no link in the navigation bar, you can get to this information by going to any serialized class and clicking "Serialized Form" in the "See also" section of the class description.
-
Constant Field Values
The Constant Field Values page lists the static final fields and their values.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev
- Next
M0.506_PEC4/doc/allclasses-frame.html
All Classes
- AcyclicSP
- AdjMatrixEdgeWeightedDigraph
- AnEvenNumber
- Bag
- BellmanFordSP
- Bipartite
- BreadthFirstDirectedPaths
- BreadthFirstPaths
- CC
- ClosestPrimeNumber
- Cycle
- DepthFirstDirectedPaths
- DepthFirstOrder
- DepthFirstPaths
- DepthFirstSearch
- Digraph
- DijkstraSP
- DirectedCycle
- DirectedDFS
- DirectedEdge
- Dungeon
- Edge
- EdgeWeightedDigraph
- EdgeWeightedDirectedCycle
- EdgeWeightedGraph
- FloydWarshall
- Graph
- In
- IndexMinPQ
- KosarajuSharirSCC
- Movement
- Queue
- RestrictedBreadthFirstPaths
- Stack
- Thief
- Topological
- TransitiveClosure
M0.506_PEC4/doc/package-list
edu.uoc.mecm.eda.game.map edu.uoc.mecm.eda.player edu.uoc.mecm.eda.search edu.uoc.mecm.eda.utils
M0.506_PEC4/doc/index-files/index-2.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
B
- Bag<Item> - Class in edu.uoc.mecm.eda.utils
- The Bag class represents a bag (or multiset) of generic items.
- Bag() - Constructor for class edu.uoc.mecm.eda.utils.Bag
- Initializes an empty bag.
- BellmanFordSP - Class in edu.uoc.mecm.eda.utils
- The BellmanFordSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs with no negative cycles.
- BellmanFordSP(EdgeWeightedDigraph, int) - Constructor for class edu.uoc.mecm.eda.utils.BellmanFordSP
- Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.
- Bipartite - Class in edu.uoc.mecm.eda.utils
- The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle.
- Bipartite(Graph) - Constructor for class edu.uoc.mecm.eda.utils.Bipartite
- Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
- BreadthFirstDirectedPaths - Class in edu.uoc.mecm.eda.utils
- The BreadthDirectedFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or set of source vertices) to every other vertex in the digraph.
- BreadthFirstDirectedPaths(Digraph, int) - Constructor for class edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- Computes the shortest path from s and every other vertex in graph G.
- BreadthFirstDirectedPaths(Digraph, Iterable<Integer>) - Constructor for class edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G.
- BreadthFirstPaths - Class in edu.uoc.mecm.eda.utils
- The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or a set of source vertices) to every other vertex in an undirected graph.
- BreadthFirstPaths(Graph, int) - Constructor for class edu.uoc.mecm.eda.utils.BreadthFirstPaths
- Computes the shortest path between the source vertex s and every other vertex in the graph G.
- BreadthFirstPaths(Graph, Iterable<Integer>) - Constructor for class edu.uoc.mecm.eda.utils.BreadthFirstPaths
- Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-15.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
Q
- Queue<Item> - Class in edu.uoc.mecm.eda.utils
- The Queue class represents a first-in-first-out (FIFO) queue of generic items.
- Queue() - Constructor for class edu.uoc.mecm.eda.utils.Queue
- Initializes an empty queue.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-19.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
V
- V() - Method in class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Returns the number of vertices in the edge-weighted digraph.
- V() - Method in class edu.uoc.mecm.eda.utils.Digraph
- Returns the number of vertices in the digraph.
- V() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Returns the number of vertices in the edge-weighted digraph.
- V() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Returns the number of vertices in the edge-weighted graph.
- V() - Method in class edu.uoc.mecm.eda.utils.Graph
- Returns the number of vertices in the graph.
- valueOf(String) - Static method in enum edu.uoc.mecm.eda.game.map.Movement
- Returns the enum constant of this type with the specified name.
- values() - Static method in enum edu.uoc.mecm.eda.game.map.Movement
- Returns an array containing the constants of this enum type, in the order they are declared.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-18.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
T
- Thief - Class in edu.uoc.mecm.eda.player
- Thief(Dungeon) - Constructor for class edu.uoc.mecm.eda.player.Thief
- Constructor de la clase
- to() - Method in class edu.uoc.mecm.eda.utils.DirectedEdge
- Returns the head vertex of the directed edge.
- Topological - Class in edu.uoc.mecm.eda.utils
- The Topological class represents a data type for determining a topological order of a directed acyclic graph (DAG).
- Topological(Digraph) - Constructor for class edu.uoc.mecm.eda.utils.Topological
- Determines whether the digraph G has a topological order and, if so, finds such a topological order.
- Topological(EdgeWeightedDigraph) - Constructor for class edu.uoc.mecm.eda.utils.Topological
- Determines whether the edge-weighted digraph G has a topological order and, if so, finds such an order.
- toString() - Method in class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Returns a string representation of the edge-weighted digraph.
- toString() - Method in class edu.uoc.mecm.eda.utils.Digraph
- Returns a string representation of the graph.
- toString() - Method in class edu.uoc.mecm.eda.utils.DirectedEdge
- Returns a string representation of the directed edge.
- toString() - Method in class edu.uoc.mecm.eda.utils.Edge
- Returns a string representation of the edge.
- toString() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Returns a string representation of the edge-weighted digraph.
- toString() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Returns a string representation of the edge-weighted graph.
- toString() - Method in class edu.uoc.mecm.eda.utils.Graph
- Returns a string representation of the graph.
- toString() - Method in class edu.uoc.mecm.eda.utils.Queue
- Returns a string representation of this queue.
- toString() - Method in class edu.uoc.mecm.eda.utils.Stack
- Returns a string representation of this stack.
- TransitiveClosure - Class in edu.uoc.mecm.eda.utils
- The TransitiveClosure class represents a data type for computing the transitive closure of a digraph.
- TransitiveClosure(Digraph) - Constructor for class edu.uoc.mecm.eda.utils.TransitiveClosure
- Computes the transitive closure of the digraph G.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-14.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
P
- path(int, int) - Method in class edu.uoc.mecm.eda.utils.FloydWarshall
- Returns a shortest path from vertex s to vertex t.
- pathFrom(int, boolean) - Method in class edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.
- pathTo(int, boolean) - Method in class edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.AcyclicSP
- Returns a shortest path from the source vertex s to vertex v.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.BellmanFordSP
- Returns a shortest path from the source s to vertex v.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- Returns a shortest path from s (or sources) to v, or null if no such path.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.BreadthFirstPaths
- Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
- Returns a directed path from the source vertex s to vertex v, or null if no such path.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstPaths
- Returns a path between the source vertex s and vertex v, or null if no such path.
- pathTo(int) - Method in class edu.uoc.mecm.eda.utils.DijkstraSP
- Returns a shortest path from the source vertex s to vertex v.
- peek() - Method in class edu.uoc.mecm.eda.utils.Queue
- Returns the item least recently added to this queue.
- peek() - Method in class edu.uoc.mecm.eda.utils.Stack
- Returns (but does not remove) the item most recently added to this stack.
- pop() - Method in class edu.uoc.mecm.eda.utils.Stack
- Removes and returns the item most recently added to this stack.
- post(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Returns the postorder number of vertex v.
- post() - Method in class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Returns the vertices in postorder.
- pre(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Returns the preorder number of vertex v.
- pre() - Method in class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Returns the vertices in preorder.
- push(Item) - Method in class edu.uoc.mecm.eda.utils.Stack
- Adds the item to this stack.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-3.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
C
- canMove(int, Movement) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si se puede mover desde el punto indicado con el movimiento indicado
- canMove(int, int, Movement) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si se puede mover desde el punto indicado con el movimiento indicado
- CC - Class in edu.uoc.mecm.eda.utils
- The CC class represents a data type for determining the connected components in an undirected graph.
- CC(Graph) - Constructor for class edu.uoc.mecm.eda.utils.CC
- Computes the connected components of the undirected graph G.
- change(int, Key) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Deprecated. Replaced by changeKey()
- changeKey(int, Key) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Change the key associated with index i to the specified value.
- close() - Method in class edu.uoc.mecm.eda.utils.In
- Close the input stream.
- ClosestPrimeNumber - Class in edu.uoc.mecm.eda.search
- Clase encargada de encontrar el vértice primo (considerar que los vértices representan enteros) más cercano
- ClosestPrimeNumber(Graph) - Constructor for class edu.uoc.mecm.eda.search.ClosestPrimeNumber
- Constructor de la clase
- color(int) - Method in class edu.uoc.mecm.eda.utils.Bipartite
- Returns the side of the bipartite that vertex v is on.
- compareTo(Edge) - Method in class edu.uoc.mecm.eda.utils.Edge
- Compares two edges by weight.
- connected(int, int) - Method in class edu.uoc.mecm.eda.utils.CC
- Are vertices v and w in the same connected component?
- contains(int) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Is i an index on the priority queue?
- count() - Method in class edu.uoc.mecm.eda.utils.CC
- Returns the number of connected components.
- count() - Method in class edu.uoc.mecm.eda.utils.DepthFirstSearch
- Returns the number of vertices connected to the source vertex s.
- count() - Method in class edu.uoc.mecm.eda.utils.DirectedDFS
- Returns the number of vertices reachable from the source vertex (or source vertices).
- count() - Method in class edu.uoc.mecm.eda.utils.KosarajuSharirSCC
- Returns the number of strong components.
- Cycle - Class in edu.uoc.mecm.eda.utils
- The Cycle class represents a data type for determining whether an undirected graph has a cycle.
- Cycle(Graph) - Constructor for class edu.uoc.mecm.eda.utils.Cycle
- Determines whether the undirected graph G has a cycle and, if so, finds such a cycle.
- cycle() - Method in class edu.uoc.mecm.eda.utils.Cycle
- Returns a cycle if the graph has a cycle, and null otherwise.
- cycle() - Method in class edu.uoc.mecm.eda.utils.DirectedCycle
- Returns a directed cycle if the digraph has a directed cycle, and null otherwise.
- cycle() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
- Returns a directed cycle if the edge-weighted digraph has a directed cycle, and null otherwise.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-8.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
H
- hasCycle() - Method in class edu.uoc.mecm.eda.utils.Cycle
- Does the graph have a cycle?
- hasCycle() - Method in class edu.uoc.mecm.eda.utils.DirectedCycle
- Does the digraph have a directed cycle?
- hasCycle() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
- Does the edge-weighted digraph have a directed cycle?
- hasEnemy(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla del mapa contiene un enemigo o no
- hasEnemy(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla del mapa contiene un enemigo o no
- hasExit(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla contiene una salida o no
- hasExit(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la coordenada en una dimensión es válida o no
- hasNegativeCycle() - Method in class edu.uoc.mecm.eda.utils.BellmanFordSP
- Is there a negative cycle reachable from the source vertex s?
- hasNegativeCycle() - Method in class edu.uoc.mecm.eda.utils.FloydWarshall
- Is there a negative cycle?
- hasNextChar() - Method in class edu.uoc.mecm.eda.utils.In
- Is the input empty (including whitespace)?
- hasNextLine() - Method in class edu.uoc.mecm.eda.utils.In
- Does the input have a next line?
- hasOrder() - Method in class edu.uoc.mecm.eda.utils.Topological
- Does the digraph have a topological order?
- hasPath(int, int) - Method in class edu.uoc.mecm.eda.utils.FloydWarshall
- Is there a path from the vertex s to vertex t?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- Is there a path between the source vertex s (or sources) and vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.AcyclicSP
- Is there a path from the source vertex s to vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.BellmanFordSP
- Is there a path from the source s to vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- Is there a directed path from the source s (or sources) to vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.BreadthFirstPaths
- Is there a path between the source vertex s (or sources) and vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
- Is there a directed path from the source vertex s to vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstPaths
- Is there a path between the source vertex s and vertex v?
- hasPathTo(int) - Method in class edu.uoc.mecm.eda.utils.DijkstraSP
- Is there a path from the source vertex s to vertex v?
- hasTreasure(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla del mapa contiene un tesoro o no
- hasTreasure(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla del mapa contiene un tesoro o no
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-4.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
D
- decreaseKey(int, Key) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Decrease the key associated with index i to the specified value.
- degree(int) - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Returns the degree of vertex v.
- degree(int) - Method in class edu.uoc.mecm.eda.utils.Graph
- Returns the degree of vertex v.
- delete(int) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Remove the key associated with index i.
- delMin() - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Removes a minimum key and returns its associated index.
- DepthFirstDirectedPaths - Class in edu.uoc.mecm.eda.utils
- The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph.
- DepthFirstDirectedPaths(Digraph, int) - Constructor for class edu.uoc.mecm.eda.utils.DepthFirstDirectedPaths
- Computes a directed path from s to every other vertex in digraph G.
- DepthFirstOrder - Class in edu.uoc.mecm.eda.utils
- The DepthFirstOrder class represents a data type for determining depth-first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder.
- DepthFirstOrder(Digraph) - Constructor for class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Determines a depth-first order for the digraph G.
- DepthFirstOrder(EdgeWeightedDigraph) - Constructor for class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Determines a depth-first order for the edge-weighted digraph G.
- DepthFirstPaths - Class in edu.uoc.mecm.eda.utils
- The DepthFirstPaths class represents a data type for finding paths from a source vertex s to every other vertex in an undirected graph.
- DepthFirstPaths(Graph, int) - Constructor for class edu.uoc.mecm.eda.utils.DepthFirstPaths
- Computes a path between s and every other vertex in graph G.
- DepthFirstSearch - Class in edu.uoc.mecm.eda.utils
- The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph.
- DepthFirstSearch(Graph, int) - Constructor for class edu.uoc.mecm.eda.utils.DepthFirstSearch
- Computes the vertices in graph G that are connected to the source vertex s.
- dequeue() - Method in class edu.uoc.mecm.eda.utils.Queue
- Removes and returns the item on this queue that was least recently added.
- Digraph - Class in edu.uoc.mecm.eda.utils
- The Digraph class represents a directed graph of vertices named 0 through V - 1.
- Digraph(int) - Constructor for class edu.uoc.mecm.eda.utils.Digraph
- Initializes an empty digraph with V vertices.
- Digraph(In) - Constructor for class edu.uoc.mecm.eda.utils.Digraph
- Initializes a digraph from an input stream.
- Digraph(Digraph) - Constructor for class edu.uoc.mecm.eda.utils.Digraph
- Initializes a new digraph that is a deep copy of G.
- DijkstraSP - Class in edu.uoc.mecm.eda.utils
- The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.
- DijkstraSP(EdgeWeightedDigraph, int) - Constructor for class edu.uoc.mecm.eda.utils.DijkstraSP
- Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph G.
- DirectedCycle - Class in edu.uoc.mecm.eda.utils
- The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle.
- DirectedCycle(Digraph) - Constructor for class edu.uoc.mecm.eda.utils.DirectedCycle
- Determines whether the digraph G has a directed cycle and, if so, finds such a cycle.
- DirectedDFS - Class in edu.uoc.mecm.eda.utils
- The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex s (or set of source vertices) in a digraph.
- DirectedDFS(Digraph, int) - Constructor for class edu.uoc.mecm.eda.utils.DirectedDFS
- Computes the vertices in digraph G that are reachable from the source vertex s.
- DirectedDFS(Digraph, Iterable<Integer>) - Constructor for class edu.uoc.mecm.eda.utils.DirectedDFS
- Computes the vertices in digraph G that are connected to any of the source vertices sources.
- DirectedEdge - Class in edu.uoc.mecm.eda.utils
- The DirectedEdge class represents a weighted edge in an EdgeWeightedDigraph.
- DirectedEdge(int, int, double) - Constructor for class edu.uoc.mecm.eda.utils.DirectedEdge
- Initializes a directed edge from vertex v to vertex w with the given weight.
- dist(int, int) - Method in class edu.uoc.mecm.eda.utils.FloydWarshall
- Returns the length of a shortest path from vertex s to vertex t.
- distTo(int) - Method in class edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?
- distTo(int) - Method in class edu.uoc.mecm.eda.utils.AcyclicSP
- Returns the length of a shortest path from the source vertex s to vertex v.
- distTo(int) - Method in class edu.uoc.mecm.eda.utils.BellmanFordSP
- Returns the length of a shortest path from the source vertex s to vertex v.
- distTo(int) - Method in class edu.uoc.mecm.eda.utils.BreadthFirstDirectedPaths
- Returns the number of edges in a shortest path from the source s (or sources) to vertex v?
- distTo(int) - Method in class edu.uoc.mecm.eda.utils.BreadthFirstPaths
- Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?
- distTo(int) - Method in class edu.uoc.mecm.eda.utils.DijkstraSP
- Returns the length of a shortest path from the source vertex s to vertex v.
- Dungeon - Class in edu.uoc.mecm.eda.game.map
- Dungeon(String) - Constructor for class edu.uoc.mecm.eda.game.map.Dungeon
- Construye una dungeon a partir de un fichero
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-13.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
O
- oddCycle() - Method in class edu.uoc.mecm.eda.utils.Bipartite
- Returns an odd-length cycle if the graph is not bipartite, and null otherwise.
- order() - Method in class edu.uoc.mecm.eda.utils.Topological
- Returns a topological order if the digraph has a topologial order, and null otherwise.
- other(int) - Method in class edu.uoc.mecm.eda.utils.Edge
- Returns the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex).
- outdegree(int) - Method in class edu.uoc.mecm.eda.utils.Digraph
- Returns the number of directed edges incident from vertex v.
- outdegree(int) - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Returns the number of directed edges incident from vertex v.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-12.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
N
- negativeCycle() - Method in class edu.uoc.mecm.eda.utils.BellmanFordSP
- Returns a negative cycle reachable from the source vertex s, or null if there is no such cycle.
- negativeCycle() - Method in class edu.uoc.mecm.eda.utils.FloydWarshall
- Returns a negative cycle, or null if there is no such cycle.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-5.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
E
- E() - Method in class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Returns the number of edges in the edge-weighted digraph.
- E() - Method in class edu.uoc.mecm.eda.utils.Digraph
- Returns the number of edges in the digraph.
- E() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Returns the number of edges in the edge-weighted digraph.
- E() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Returns the number of edges in the edge-weighted graph.
- E() - Method in class edu.uoc.mecm.eda.utils.Graph
- Returns the number of edges in the graph.
- Edge - Class in edu.uoc.mecm.eda.utils
- The Edge class represents a weighted edge in an EdgeWeightedGraph.
- Edge(int, int, double) - Constructor for class edu.uoc.mecm.eda.utils.Edge
- Initializes an edge between vertices v/tt> and w of the given weight.
- edges() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Returns all directed edges in the edge-weighted digraph.
- edges() - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Returns all edges in the edge-weighted graph.
- EdgeWeightedDigraph - Class in edu.uoc.mecm.eda.utils
- The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight.
- EdgeWeightedDigraph(int) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Initializes an empty edge-weighted digraph with V vertices and 0 edges.
- EdgeWeightedDigraph(int, int) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Initializes a random edge-weighted digraph with V vertices and E edges.
- EdgeWeightedDigraph(In) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Initializes an edge-weighted digraph from an input stream.
- EdgeWeightedDigraph(EdgeWeightedDigraph) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Initializes a new edge-weighted digraph that is a deep copy of G.
- EdgeWeightedDirectedCycle - Class in edu.uoc.mecm.eda.utils
- The EdgeWeightedDirectedCycle class represents a data type for determining whether an edge-weighted digraph has a directed cycle.
- EdgeWeightedDirectedCycle(EdgeWeightedDigraph) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedDirectedCycle
- Determines whether the edge-weighted digraph G has a directed cycle and, if so, finds such a cycle.
- EdgeWeightedGraph - Class in edu.uoc.mecm.eda.utils
- The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V - 1, where each undirected edge is of type Edge and has a real-valued weight.
- EdgeWeightedGraph(int) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Initializes an empty edge-weighted graph with V vertices and 0 edges.
- EdgeWeightedGraph(int, int) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Initializes a random edge-weighted graph with V vertices and E edges.
- EdgeWeightedGraph(In) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Initializes an edge-weighted graph from an input stream.
- EdgeWeightedGraph(EdgeWeightedGraph) - Constructor for class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Initializes a new edge-weighted graph that is a deep copy of G.
- edu.uoc.mecm.eda.game.map - package edu.uoc.mecm.eda.game.map
- edu.uoc.mecm.eda.player - package edu.uoc.mecm.eda.player
- edu.uoc.mecm.eda.search - package edu.uoc.mecm.eda.search
- edu.uoc.mecm.eda.utils - package edu.uoc.mecm.eda.utils
- either() - Method in class edu.uoc.mecm.eda.utils.Edge
- Returns either endpoint of the edge.
- enqueue(Item) - Method in class edu.uoc.mecm.eda.utils.Queue
- Adds the item to this queue.
- exists() - Method in class edu.uoc.mecm.eda.utils.In
- Does the input stream exist?
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-9.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
I
- id(int) - Method in class edu.uoc.mecm.eda.utils.CC
- Returns the component id of the connected component containing vertex v.
- id(int) - Method in class edu.uoc.mecm.eda.utils.KosarajuSharirSCC
- Returns the component id of the strong component containing vertex v.
- In - Class in edu.uoc.mecm.eda.utils
- Input.
- In() - Constructor for class edu.uoc.mecm.eda.utils.In
- Create an input stream from standard input.
- In(Socket) - Constructor for class edu.uoc.mecm.eda.utils.In
- Create an input stream from a socket.
- In(URL) - Constructor for class edu.uoc.mecm.eda.utils.In
- Create an input stream from a URL.
- In(File) - Constructor for class edu.uoc.mecm.eda.utils.In
- Create an input stream from a file.
- In(String) - Constructor for class edu.uoc.mecm.eda.utils.In
- Create an input stream from a filename or web page name.
- In(Scanner) - Constructor for class edu.uoc.mecm.eda.utils.In
- Create an input stream from a given Scanner source; use with new Scanner(String) to read from a string.
- increaseKey(int, Key) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Increase the key associated with index i to the specified value.
- IndexMinPQ<Key extends java.lang.Comparable<Key>> - Class in edu.uoc.mecm.eda.utils
- The IndexMinPQ class represents an indexed priority queue of generic keys.
- IndexMinPQ(int) - Constructor for class edu.uoc.mecm.eda.utils.IndexMinPQ
- Initializes an empty indexed priority queue with indices between 0 and NMAX-1.
- insert(int, Key) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Associates key with index i.
- isBipartite() - Method in class edu.uoc.mecm.eda.utils.Bipartite
- Is the graph bipartite?
- isEmpty() - Method in class edu.uoc.mecm.eda.utils.Bag
- Is this bag empty?
- isEmpty() - Method in class edu.uoc.mecm.eda.utils.In
- Is the input empty (except possibly for whitespace)?
- isEmpty() - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Is the priority queue empty?
- isEmpty() - Method in class edu.uoc.mecm.eda.utils.Queue
- Is this queue empty?
- isEmpty() - Method in class edu.uoc.mecm.eda.utils.Stack
- Is this stack empty?
- isStartingPoint(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla es el punto de inicio del ladrón
- isStartingPoint(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla es el punto de inicio del ladrón
- isValidPlan(List<Movement>) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Dado un plan, determina si éste es válido para acabar el nivel
- isWalkable(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla del mapa es pisable o no
- isWalkable(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Determina si la casilla del mapa es pisable o no
- iterator() - Method in class edu.uoc.mecm.eda.utils.Bag
- Returns an iterator that iterates over the items in the bag in arbitrary order.
- iterator() - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Returns an iterator that iterates over the keys on the priority queue in ascending order.
- iterator() - Method in class edu.uoc.mecm.eda.utils.Queue
- Returns an iterator that iterates over the items in this queue in FIFO order.
- iterator() - Method in class edu.uoc.mecm.eda.utils.Stack
- Returns an iterator to this stack that iterates through the items in LIFO order.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-11.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M
- main(String[]) - Static method in class edu.uoc.mecm.eda.game.map.Dungeon
- main(String[]) - Static method in class edu.uoc.mecm.eda.search.AnEvenNumber
- main(String[]) - Static method in class edu.uoc.mecm.eda.search.ClosestPrimeNumber
- main(String[]) - Static method in class edu.uoc.mecm.eda.utils.In
- Test client.
- marked(int) - Method in class edu.uoc.mecm.eda.utils.DepthFirstSearch
- Is there a path between the source vertex s and vertex v?
- marked(int) - Method in class edu.uoc.mecm.eda.utils.DirectedDFS
- Is there a directed path from the source vertex (or any of the source vertices) and vertex v?
- minIndex() - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Returns an index associated with a minimum key.
- minKey() - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Returns a minimum key.
- move(int, Movement) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Dado un punto de origen, realiza un movimiento
- move(int, int, Movement) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Dado un punto de origen, realiza un movimiento
- Movement - Enum in edu.uoc.mecm.eda.game.map
- Clase de tipo enumeración par los posibles movimientos del ladrón
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-6.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
F
- FloydWarshall - Class in edu.uoc.mecm.eda.utils
- The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles.
- FloydWarshall(AdjMatrixEdgeWeightedDigraph) - Constructor for class edu.uoc.mecm.eda.utils.FloydWarshall
- Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.
- from() - Method in class edu.uoc.mecm.eda.utils.DirectedEdge
- Returns the tail vertex of the directed edge.
- from1Dto2D(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Pasa de una dimensión a dos
- from2Dto1D(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Pasa de 2 dimensiones a coordenadas en una dimensión
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-7.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
G
- getAnEvenNumber(int, int) - Method in class edu.uoc.mecm.eda.search.AnEvenNumber
- Obtiene un vértice par a una distancia menor a la especificada por parámetro del vértice inicial
- getClosestFrom(int) - Method in class edu.uoc.mecm.eda.search.ClosestPrimeNumber
- Obtiene el vértice primo más cercano al vértice pasado por parámetro
- getHeight() - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Devuelve la altura del mapa
- getMovableArea(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Devuelve una lista de casillas en coordenadas unidimensionales que constituyen las casillas dentro del mapa a las que se puede mover el ladrón
- getMovableArea(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Devuelve una lista de casillas en coordenadas 2d que constituyen las casillas dentro del mapa a las que se puede mover el ladrón
- getMovement(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino
- getMovement(int, int, int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Obtener movimiento atómico a realizar para ir de la casilla de origen a la casilla de destino
- getPlan() - Method in class edu.uoc.mecm.eda.player.Thief
- getWatchArea(int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Devuelve una lista de casillas en coordenadas unidimensionales que constituyen el contorno de radio 1 de una casilla dada Se usa para determinar el área de vigilancia de un monstruo
- getWatchArea2D(int, int) - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Devuelve una lista de casillas en coordenadas 2D que constituyen el contorno de radio 1 de una casilla dada Se usa para determinar el área de vigilancia de un monstruo
- getWidth() - Method in class edu.uoc.mecm.eda.game.map.Dungeon
- Devuelve la anchura del mapa
- Graph - Class in edu.uoc.mecm.eda.utils
- The Graph class represents an undirected graph of vertices named 0 through V - 1.
- Graph(int) - Constructor for class edu.uoc.mecm.eda.utils.Graph
- Initializes an empty graph with V vertices and 0 edges.
- Graph(In) - Constructor for class edu.uoc.mecm.eda.utils.Graph
- Initializes a graph from an input stream.
- Graph(Graph) - Constructor for class edu.uoc.mecm.eda.utils.Graph
- Initializes a new graph that is a deep copy of G.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-10.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
K
- keyOf(int) - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Returns the key associated with index i.
- KosarajuSharirSCC - Class in edu.uoc.mecm.eda.utils
- The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph.
- KosarajuSharirSCC(Digraph) - Constructor for class edu.uoc.mecm.eda.utils.KosarajuSharirSCC
- Computes the strong components of the digraph G.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-17.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
S
- size() - Method in class edu.uoc.mecm.eda.utils.Bag
- Returns the number of items in this bag.
- size(int) - Method in class edu.uoc.mecm.eda.utils.CC
- Returns the number of vertices in the connected component containing vertex v.
- size() - Method in class edu.uoc.mecm.eda.utils.IndexMinPQ
- Returns the number of keys on the priority queue.
- size() - Method in class edu.uoc.mecm.eda.utils.Queue
- Returns the number of items in this queue.
- size() - Method in class edu.uoc.mecm.eda.utils.Stack
- Returns the number of items in the stack.
- Stack<Item> - Class in edu.uoc.mecm.eda.utils
- The Stack class represents a last-in-first-out (LIFO) stack of generic items.
- Stack() - Constructor for class edu.uoc.mecm.eda.utils.Stack
- Initializes an empty stack.
- stronglyConnected(int, int) - Method in class edu.uoc.mecm.eda.utils.KosarajuSharirSCC
- Are vertices v and w in the same strong component?
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/doc/index-files/index-20.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev Letter
- Next Letter
W
- weight() - Method in class edu.uoc.mecm.eda.utils.DirectedEdge
- Returns the weight of the directed edge.
- weight() - Method in class edu.uoc.mecm.eda.utils.Edge
- Returns the weight of the edge.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev Letter
- Next Letter
M0.506_PEC4/doc/index-files/index-1.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev Letter
- Next Letter
A
- AcyclicSP - Class in edu.uoc.mecm.eda.utils
- The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs).
- AcyclicSP(EdgeWeightedDigraph, int) - Constructor for class edu.uoc.mecm.eda.utils.AcyclicSP
- Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G.
- add(Item) - Method in class edu.uoc.mecm.eda.utils.Bag
- Adds the item to this bag.
- addEdge(DirectedEdge) - Method in class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Adds the directed edge e to the edge-weighted digraph (if there is not already an edge with the same endpoints).
- addEdge(int, int) - Method in class edu.uoc.mecm.eda.utils.Digraph
- Adds the directed edge v->w to the digraph.
- addEdge(DirectedEdge) - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Adds the directed edge e to the edge-weighted digraph.
- addEdge(Edge) - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Adds the undirected edge e to the edge-weighted graph.
- addEdge(int, int) - Method in class edu.uoc.mecm.eda.utils.Graph
- Adds the undirected edge v-w to the graph.
- adj(int) - Method in class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Returns the directed edges incident from vertex v.
- adj(int) - Method in class edu.uoc.mecm.eda.utils.Digraph
- Returns the vertices adjacent from vertex v in the digraph.
- adj(int) - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedDigraph
- Returns the directed edges incident from vertex v.
- adj(int) - Method in class edu.uoc.mecm.eda.utils.EdgeWeightedGraph
- Returns the edges incident on vertex v.
- adj(int) - Method in class edu.uoc.mecm.eda.utils.Graph
- Returns the vertices adjacent to vertex v.
- AdjMatrixEdgeWeightedDigraph - Class in edu.uoc.mecm.eda.utils
- The AdjMatrixEdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight.
- AdjMatrixEdgeWeightedDigraph(int) - Constructor for class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Initializes an empty edge-weighted digraph with V vertices and 0 edges.
- AdjMatrixEdgeWeightedDigraph(int, int) - Constructor for class edu.uoc.mecm.eda.utils.AdjMatrixEdgeWeightedDigraph
- Initializes a random edge-weighted digraph with V vertices and E edges.
- AnEvenNumber - Class in edu.uoc.mecm.eda.search
- AnEvenNumber(Graph) - Constructor for class edu.uoc.mecm.eda.search.AnEvenNumber
- Constructor de la clase
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
- Prev Letter
- Next Letter
M0.506_PEC4/doc/index-files/index-16.html
JavaScript is disabled on your browser. Skip navigation links- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
R
- reachable(int, int) - Method in class edu.uoc.mecm.eda.utils.TransitiveClosure
- Is there a directed path from vertex v to vertex w in the digraph?
- readAll() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the remainder of the input as a string.
- readAllDoubles() - Method in class edu.uoc.mecm.eda.utils.In
- Read all doubles until the end of input is reached, and return them.
- readAllInts() - Method in class edu.uoc.mecm.eda.utils.In
- Read all ints until the end of input is reached, and return them.
- readAllLines() - Method in class edu.uoc.mecm.eda.utils.In
- Reads all remaining lines from input stream and returns them as an array of strings.
- readAllStrings() - Method in class edu.uoc.mecm.eda.utils.In
- Read all strings until the end of input is reached, and return them.
- readBoolean() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next boolean, allowing case-insensitive "true" or "1" for true, and "false" or "0" for false.
- readByte() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next byte.
- readChar() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next character.
- readDouble() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next double.
- readDoubles(String) - Static method in class edu.uoc.mecm.eda.utils.In
- Deprecated. Clearer to use new In(filename).In.readAllDoubles()
- readDoubles() - Static method in class edu.uoc.mecm.eda.utils.In
- Deprecated. Clearer to use StdIn#readAllDoubles()
- readFloat() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next float.
- readInt() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next int.
- readInts(String) - Static method in class edu.uoc.mecm.eda.utils.In
- Deprecated. Clearer to use new In(filename).In.readAllInts()
- readInts() - Static method in class edu.uoc.mecm.eda.utils.In
- Deprecated. Clearer to use StdIn#readAllInts()
- readLine() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next line.
- readLong() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next long.
- readShort() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next short.
- readString() - Method in class edu.uoc.mecm.eda.utils.In
- Read and return the next string.
- readStrings(String) - Static method in class edu.uoc.mecm.eda.utils.In
- Deprecated. Clearer to use new In(filename).In.readAllStrings()
- readStrings() - Static method in class edu.uoc.mecm.eda.utils.In
- Deprecated. Clearer to use StdIn#readAllStrings()
- RestrictedBreadthFirstPaths - Class in edu.uoc.mecm.eda.player
- Clase modificada que realiza un bfs sobre el grafo para encontrar el camino más corto desde un vértice de origen a un conjunto de vértices de interés No usamos Dijkstra ya que no sería necesario (todos los enlaces tienen el mismo coste) y no es necesario calcular la distancia a todas las casillas, tan sólo a las que contienen tesoros y salidas
- RestrictedBreadthFirstPaths(Graph, int, Set<Integer>) - Constructor for class edu.uoc.mecm.eda.player.RestrictedBreadthFirstPaths
- Calcula el camino más corto entre el vértice origen y los puntos de interés
- reverse() - Method in class edu.uoc.mecm.eda.utils.Digraph
- Returns the reverse of the digraph.
- reversePost() - Method in class edu.uoc.mecm.eda.utils.DepthFirstOrder
- Returns the vertices in reverse postorder.
- Overview
- Package
- Class
- Use
- Tree
- Deprecated
- Index
- Help
M0.506_PEC4/src/edu/uoc/mecm/eda/utils/DepthFirstDirectedPaths.java
M0.506_PEC4/src/edu/uoc/mecm/eda/utils/DepthFirstDirectedPaths.java
package
edu
.
uoc
.
mecm
.
eda
.
utils
;
/*************************************************************************
* Compilation: javac DepthFirstDirectedPaths.java
* Execution: java DepthFirstDirectedPaths G s
* Dependencies: Digraph.java Stack.java
*
* Determine reachability in a digraph from a given vertex using
* depth first search.
* Runs in O(E + V) time.
*
* % tinyDG.txt 3
* 3 to 0: 3-5-4-2-0
* 3 to 1: 3-5-4-2-0-1
* 3 to 2: 3-5-4-2
* 3 to 3: 3
* 3 to 4: 3-5-4
* 3 to 5: 3-5
* 3 to 6: not connected
* 3 to 7: not connected
* 3 to 8: not connected
* 3 to 9: not connected
* 3 to 10: not connected
* 3 to 11: not connected
* 3 to 12: not connected
*
*************************************************************************/
/**
* The <tt>DepthFirstDirectedPaths</tt> class represents a data type for finding
* directed paths from a source vertex <em>s</em> to every
* other vertex in the digraph.
* <p>
* This implementation uses depth-first search.
* The constructor takes time proportional to <em>V</em> + <em>E</em>,
* where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
* It uses extra space (not including the graph) proportional to <em>V</em>.
* <p>
* For additional documentation, see <a href="/algs4/41graph">Section 4.1</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
*
@author
Robert Sedgewick
*
@author
Kevin Wayne
*/
public
class
DepthFirstDirectedPaths
{
private
boolean
[]
marked
;
// marked[v] = true if v is reachable from s
private
int
[]
edgeTo
;
// edgeTo[v] = last edge on path from s to v
private
final
int
s
;
// source vertex
/**
* Computes a directed path from <tt>s</tt> to every other vertex in digraph <tt>G</tt>.
*
@param
G the digraph
*
@param
s the source vertex
*/
public
DepthFirstDirectedPaths
(
Digraph
G
,
int
s
)
{
marked
=
new
boolean
[
G
.
V
()];
edgeTo
=
new
int
[
G
.
V
()];
this
.
s
=
s
;
dfs
(
G
,
s
);
}
private
void
dfs
(
Digraph
G
,
int
v
)
{
marked
[
v
]
=
true
;
for
(
int
w
:
G
.
adj
(
v
))
{
if
(
!
marked
[
w
])
{
edgeTo
[
w
]
=
v
;
dfs
(
G
,
w
);
}
}
}
/**
* Is there a directed path from the source vertex <tt>s</tt> to vertex <tt>v</tt>?
*
@param
v the vertex
*
@return
<tt>true</tt> if there is a directed path from the source
* vertex <tt>s</tt> to vertex <tt>v</tt>, <tt>false</tt> otherwise
*/
public
boolean
hasPathTo
(
int
v
)
{
return
marked
[
v
];
}
/**
* Returns a directed path from the source vertex <tt>s</tt> to vertex <tt>v</tt>, or
* <tt>null</tt> if no such path.
*
@param
v the vertex
*
@return
the sequence of vertices on a directed path from the source vertex
* <tt>s</tt> to vertex <tt>v</tt>, as an Iterable
*/
public
Iterable
<
Integer
>
pathTo
(
int
v
)
{
if
(
!
hasPathTo
(
v
))
return
null
;
Stack
<
Integer
>
path
=
new
Stack
<
Integer
>
();
for
(
int
x
=
v
;
x
!=
s
;
x
=
edgeTo
[
x
])
path
.
push
(
x
);
path
.
push
(
s
);
return
path
;
}
}
M0.506_PEC4/src/edu/uoc/mecm/eda/utils/DepthFirstOrder.java
M0.506_PEC4/src/edu/uoc/mecm/eda/utils/DepthFirstOrder.java
package
edu
.
uoc
.
mecm
.
eda
.
utils
;
/*************************************************************************
* Compilation: javac DepthFirstOrder.java
* Execution: java DepthFirstOrder filename.txt
* Dependencies: Digraph.java Queue.java Stack.java StdOut.java
* EdgeWeightedDigraph.java DirectedEdge.java
* Data files: http://algs4.cs.princeton.edu/42directed/tinyDAG.txt
* http://algs4.cs.princeton.edu/42directed/tinyDG.txt
*
* Compute preorder and postorder for a digraph or edge-weighted digraph.
* Runs in O(E + V) time.
*
* % java DepthFirstOrder tinyDAG.txt
* v pre post
* --------------
* 0 0 8
* 1 3 2
* 2 9 10
* 3 10 9
* 4 2 0
* 5 1 1
* 6 4 7
* 7 11 11
* 8 12 12
* 9 5 6
* 10 8 5
* 11 6 4
* 12 7 3
* Preorder: 0 5 4 1 6 9 11 12 10 2 3 7 8
* Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8
* Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4
*
*************************************************************************/
/**
* The <tt>DepthFirstOrder</tt> class represents a data type for
* determining depth-first search ordering of the vertices in a digraph
* or edge-weighted digraph, including preorder, postorder, and reverse postorder.
* <p>
* This implementation uses depth-first search.
* The constructor takes time proportional to <em>V</em> + <em>E</em>
* (in the worst case),
* where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
* Afterwards, the <em>preorder</em>, <em>postorder</em>, and <em>reverse postorder</em>
* operation takes take time proportional to <em>V</em>.
* <p>
* <p>
* For additional documentation, see <a href="/algs4/42digraph">Section 4.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
*
@author
Robert Sedgewick
*
@author
Kevin Wayne
*/
public
class
DepthFirstOrder
{
private
boolean
[]
marked
;
// marked[v] = has v been marked in dfs?
private
int
[]
pre
;
// pre[v] = preorder number of v
private
int
[]
post
;
// post[v] = postorder number of v
private
Queue
<
Integer
>
preorder
;
// vertices in preorder
private
Queue
<
Integer
>
postorder
;
// vertices in postorder
private
int
preCounter
;
// counter or preorder numbering
private
int
postCounter
;
// counter for postorder numbering
/**
* Determines a depth-first order for the digraph <tt>G</tt>.
*
@param
G the digraph
*/
public
DepthFirstOrder
(
Digraph
G
)
{
pre
=
new
int
[
G
.
V
()];
post
=
new
int
[
G
.
V
()];
postorder
=
new
Queue
<
Integer
>
();
preorder
=
new
Queue
<
Integer
>
();
marked
=
new
boolean
[
G
.
V
()];
for
(
int
v
=
0
;
v
<
G
.
V
();
v
++
)
if
(
!
marked
[
v
])
dfs
(
G
,
v
);
}
/**
* Determines a depth-first order for the edge-weighted digraph <tt>G</tt>.
*
@param
G the edge-weighted digraph
*/
public
DepthFirstOrder
(
EdgeWeightedDigraph
G
)
{
pre
=
new
int
[
G
.
V
()];
post
=
new
int
[
G
.
V
()];
postorder
=
new
Queue
<
Integer
>
();
preorder
=
new
Queue
<
Integer
>
();
marked
=
new
boolean
[
G
.
V
()];
for
(
int
v
=
0
;
v
<
G
.
V
();
v
++
)
if
(
!
marked
[
v
])
dfs
(
G
,
v
);
}
// run DFS in digraph G from vertex v and compute preorder/postorder
private
void
dfs
(
Digraph
G
,
int
v
)
{
marked
[
v
]
=
true
;
pre
[
v
]
=
preCounter
++
;
preorder
.
enqueue
(
v
);
for
(
int
w
:
G
.
adj
(
v
))
{
if
(
!
marked
[
w
])
{
dfs
(
G
,
w
);
}
}
postorder
.
enqueue
(
v
);
post
[
v
]
=
postCounter
++
;
}
// run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder
private
void
dfs
(
EdgeWeightedDigraph
G
,
int
v
)
{
marked
[
v
]
=
true
;
pre
[
v
]
=
preCounter
++
;
preorder
.
enqueue
(
v
);
for
(
DirectedEdge
e
:
G
.
adj
(
v
))
{
int
w
=
e
.
to
();
if
(
!
marked
[
w
])
{
dfs
(
G
,
w
);
}
}
postorder
.
enqueue
(
v
);
post
[
v
]
=
postCounter
++
;
}
/**
* Returns the preorder number of vertex <tt>v</tt>.
*
@param
v the vertex
*
@return
the preorder number of vertex <tt>v</tt>
*/
public
int
pre
(
int
v
)
{
return
pre
[
v
];
}
/**
* Returns the postorder number of vertex <tt>v</tt>.
*
@param
v the vertex
*
@return
the postorder number of vertex <tt>v</tt>
*/
public
int
post
(
int
v
)
{
return
post
[
v
];
}
/**
* Returns the vertices in postorder.
*
@return
the vertices in postorder, as an iterable of vertices
*/