|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectmas.agentsHempelsSofa.algorithms.GraphAlgorithms
public class GraphAlgorithms
An implementation of some graph algorithms which are important for our agents to compute their next actions.
Constructor Summary | |
---|---|
GraphAlgorithms()
|
Method Summary | |
---|---|
static java.util.LinkedList<java.util.LinkedList<Vertex>> |
dijkstra(Graph graph)
Runs the standard Dijkstra Algorithm on a given graph . |
static java.util.LinkedList<java.util.LinkedList<Vertex>> |
dijkstra(Graph graph,
double stepWeight,
double edgeWeight)
Runs a weighted Dijkstra Algorithm on a given graph . |
static java.util.LinkedList<Vertex> |
findConnectedComponent(Graph graph,
Vertex root)
Runs breadth first search on the graph. |
static java.util.LinkedList<Vertex> |
findFastestPath(Graph graph,
Vertex source,
Vertex target)
Runs breadth first search on the graph to find the fastest path difference to findConnectdComponent is that this algorithm stops when the target is found |
static java.util.LinkedList<Vertex> |
findSurveyedConnectedComponent(Graph graph,
Vertex root)
Runs breadth first search on the graph. |
static java.util.LinkedList<Vertex> |
getSurrounding(Vertex core)
returns a list of all the neighbours which are at most 2 steps away of the position. the position itself is not included |
static java.util.LinkedList<java.util.LinkedList<Vertex>> |
goTowards(Graph graph)
|
static java.util.LinkedList<java.util.LinkedList<Vertex>> |
goTowards(Graph graph,
double stepWeight,
double edgeWeight,
int maxEdgeCost)
this action is pretty similar to dijkstra() above only difference: it considers the unsurveyed edges as well, weighting them by 5 |
static java.util.LinkedList<java.util.LinkedList<Vertex>> |
goTowards(Vertex root,
Graph graph,
double stepWeight,
double edgeWeight)
this method call finds all shortest path from a given Vertex root |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public GraphAlgorithms()
Method Detail |
---|
public static java.util.LinkedList<java.util.LinkedList<Vertex>> dijkstra(Graph graph)
graph
.
graph
- The actually known graph.
graph
to
all vertices as a list of lists of edges.public static java.util.LinkedList<java.util.LinkedList<Vertex>> dijkstra(Graph graph, double stepWeight, double edgeWeight)
graph
.
graph
- The actually known graph.stepWeight
- The weight for the number of steps. This is important,
since every goto issue costs a step.edgeWeight
- The weight for the edges weights. This determines the
influence of edge weights.
graph
to
all vertices as a list of lists of edges.public static java.util.LinkedList<java.util.LinkedList<Vertex>> goTowards(Graph graph, double stepWeight, double edgeWeight, int maxEdgeCost)
public static java.util.LinkedList<java.util.LinkedList<Vertex>> goTowards(Vertex root, Graph graph, double stepWeight, double edgeWeight)
public static java.util.LinkedList<java.util.LinkedList<Vertex>> goTowards(Graph graph)
public static java.util.LinkedList<Vertex> findFastestPath(Graph graph, Vertex source, Vertex target)
graph
- the graphsource
- the source vertextarget
- the target to go to
public static java.util.LinkedList<Vertex> findConnectedComponent(Graph graph, Vertex root)
graph
- the graphroot
- the source node
source
.public static java.util.LinkedList<Vertex> findSurveyedConnectedComponent(Graph graph, Vertex root)
graph
- the graphroot
- the source node
source
.public static java.util.LinkedList<Vertex> getSurrounding(Vertex core)
core
- the center vertex.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |