Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8308


Ignore:
Timestamp:
07/19/12 19:44:56 (12 years ago)
Author:
spimming
Message:

#1894:

  • get neighbors for specific node
  • method to calculate weight between two nodes
  • interface for router
  • Dijkstra algorithm initial commit
  • Utils methods added
Location:
branches/RoutePlanning
Files:
5 added
4 edited

Legend:

Unmodified
Added
Removed

  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

    r8302 r8308  
    4949    <Reference Include="System" />
    5050    <Reference Include="System.Core" />
     51    <Reference Include="System.Drawing" />
    5152    <Reference Include="System.Xml.Linq" />
    5253    <Reference Include="System.Data.DataSetExtensions" />
    … …  
    5657  </ItemGroup>
    5758  <ItemGroup>
     59    <Compile Include="DijkstraAlgorithm.cs" />
     60    <Compile Include="GraphRoutingAlgorithm.cs" />
     61    <Compile Include="IRouter.cs" />
    5862    <Compile Include="Plugin.cs" />
    5963    <Compile Include="Properties\AssemblyInfo.cs" />
    … …  
    6367    <None Include="Plugin.cs.frame" />
    6468    <None Include="Properties\AssemblyInfo.cs.frame" />
     69  </ItemGroup>
     70  <ItemGroup>
     71    <ProjectReference Include="..\..\HeuristicLab.Problems.RoutePlanning\3.3\HeuristicLab.Problems.RoutePlanning.csproj">
     72      <Project>{E93A30BD-D4C8-4DEC-8ECF-2BC3CD9F027B}</Project>
     73      <Name>HeuristicLab.Problems.RoutePlanning</Name>
     74    </ProjectReference>
    6575  </ItemGroup>
    6676  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />

  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs

    r8300 r8308  
    2424    }
    2525
    26     //public Dictionary<long, float> GetNeighbours(long id) {
    27     //  Vertex<Node> vertex = GetVertex(id);
    28     //  Dictionary<long, float> neighbors = new Dictionary<long, float>();
    29     //  IList<Way> edges = GetEdges(vertex);
    30     //  foreach (Way edge in edges) {
     26    public Dictionary<long, float> GetNeighbors(long id) {
     27      Vertex<Node> vertex = GetVertex(id);
     28      Dictionary<long, float> neighbors = new Dictionary<long, float>();
     29      List<Way> edges = GetEdges(vertex);
     30      foreach (Way edge in edges) {
     31        //TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
    3132
    32     //  }
    33     //  return null;
    34     //}
     33        // get all naighbours of current vertex on this edge
     34        List<Vertex<Node>> vertices = GetNeighborVerticesOnEdge(edge, vertex);
     35        foreach (Vertex<Node> neighbor in vertices) {
     36          float weight = GetWeight(edge, vertex, neighbor);
     37          neighbors[neighbor.Id] = weight;
     38        }
     39      }
     40      return null;
     41    }
    3542
     43    public List<Vertex<Node>> GetNeighborVerticesOnEdge(Way edge, Vertex<Node> vertex) {
     44      List<Vertex<Node>> neighbors = new List<Vertex<Node>>();
     45      for (int i = 0; i < edge.Nodes.Count; i++) {
     46        Node node = edge.Nodes[i];
     47        if (node.Id == vertex.Node.Id) {
     48          if (i > 0) {
     49            neighbors.Add(GetVertex(edge.Nodes[i - 1].Id));
     50          }
     51          if (i < edge.Nodes.Count - 1) {
     52            neighbors.Add(GetVertex(edge.Nodes[i + 1].Id));
     53          }
     54        }
     55      }
     56      return neighbors;
     57    }
     58
     59    public float GetWeight(Way edge, Vertex<Node> source, Vertex<Node> target) {
     60      double distance = Utils.Distance(source.Node.Point, target.Node.Point);
     61      int speed = 0;
     62
     63      //TODO:
     64      HighwayType highwayType = edge.HighwayTag;
     65      switch (highwayType) {
     66        case HighwayType.bridleway:
     67        case HighwayType.bus_guideway:
     68        case HighwayType.raceway:
     69        case HighwayType.cycleway:
     70        case HighwayType.footway:
     71        case HighwayType.steps:
     72        case HighwayType.null_type:
     73          speed = 1;
     74          break;
     75
     76        case HighwayType.path:
     77        case HighwayType.service:
     78        case HighwayType.pedestrian:
     79        case HighwayType.living_street:
     80          speed = 15;
     81          break;
     82
     83        case HighwayType.road:
     84        case HighwayType.track:
     85          speed = 30;
     86          break;
     87
     88        case HighwayType.tertiary:
     89        case HighwayType.tertiary_link:
     90        case HighwayType.secondary:
     91        case HighwayType.secondary_link:
     92          speed = 80;
     93          break;
     94
     95        case HighwayType.unclassified:
     96        case HighwayType.residential:
     97          speed = 50;
     98          break;
     99
     100        case HighwayType.trunk:
     101        case HighwayType.trunk_link:
     102        case HighwayType.primary:
     103        case HighwayType.primary_link:
     104          speed = 100;
     105          break;
     106        case HighwayType.motorway:
     107        case HighwayType.motorway_link:
     108          speed = 130;
     109          break;
     110
     111        default:
     112          speed = 1;
     113          break;
     114      }
     115
     116      double weight = (distance / speed) * 3.6;
     117      return (float)weight;
     118    }
    36119  }
    37120}

  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/HeuristicLab.Problems.RoutePlanning.csproj

    r8300 r8308  
    6565    <Compile Include="Osm\OsmBase.cs" />
    6666    <Compile Include="Osm\PointD.cs" />
     67    <Compile Include="Osm\RectangleD.cs" />
    6768    <Compile Include="Osm\Relation.cs" />
    6869    <Compile Include="Osm\RelationMember.cs" />
    6970    <Compile Include="Osm\TagConstants.cs" />
     71    <Compile Include="Osm\Utils.cs" />
    7072    <Compile Include="Osm\Way.cs" />
    7173    <Compile Include="Plugin.cs" />

  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/Node.cs

    r8293 r8308  
    1313    }
    1414
     15    public PointD Point {
     16      get { return point; }
     17    }
     18
    1519    public Node() {
    1620      point = new PointD();
Note: See TracChangeset for help on using the changeset viewer.