mas.agentsHempelsSofa.algorithms
Class GraphAlgorithms

java.lang.Object
  extended by mas.agentsHempelsSofa.algorithms.GraphAlgorithms

public class GraphAlgorithms
extends java.lang.Object

An implementation of some graph algorithms which are important for our agents to compute their next actions.

Author:
Hempels-Sofa

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

GraphAlgorithms

public GraphAlgorithms()
Method Detail

dijkstra

public static java.util.LinkedList<java.util.LinkedList<Vertex>> dijkstra(Graph graph)
Runs the standard Dijkstra Algorithm on a given graph.

Parameters:
graph - The actually known graph.
Returns:
The shortest paths from the actual position in graph to all vertices as a list of lists of edges.

dijkstra

public static java.util.LinkedList<java.util.LinkedList<Vertex>> dijkstra(Graph graph,
                                                                          double stepWeight,
                                                                          double edgeWeight)
Runs a weighted Dijkstra Algorithm on a given graph.

Parameters:
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.
Returns:
The shortest paths from the actual position in graph to all vertices as a list of lists of edges.

goTowards

public 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


goTowards

public 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


goTowards

public static java.util.LinkedList<java.util.LinkedList<Vertex>> goTowards(Graph graph)

findFastestPath

public 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

Parameters:
graph - the graph
source - the source vertex
target - the target to go to
Returns:
the fastest path

findConnectedComponent

public static java.util.LinkedList<Vertex> findConnectedComponent(Graph graph,
                                                                  Vertex root)
Runs breadth first search on the graph.

Parameters:
graph - the graph
root - the source node
Returns:
The connected component which contains source.

findSurveyedConnectedComponent

public static java.util.LinkedList<Vertex> findSurveyedConnectedComponent(Graph graph,
                                                                          Vertex root)
Runs breadth first search on the graph.

Parameters:
graph - the graph
root - the source node
Returns:
The connected component which contains source.

getSurrounding

public 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

Parameters:
core - the center vertex.


Copyright © 2012. All Rights Reserved.