Refactor structure of OASIS service

[CodeBear801]

Subtask of #358
To be discussed with @wangyoucao577

// this two paragraphs will be placed in doc :)
OASIS stands for Optimized Charge Station Selection Service, which mainly supports generating optimal charge station candidates for given query based on user's vehical information. It expects routing engine(like OSRM) to generate electronic spcific cost and only focus on how to choose most optimal charge station combination which balances charging cost(charging time, payment, etc).
For example, OASIS might suggest user spend 1 hour to charge at station A for x amount of energy then reach destination with 2 hours in total, or charge at station B and station C for 30 minutes each and reach destination with duration of 2 hours 10 minutes.

Overview

Structure layer

• layer 1: handles oasis request and generate oasis response
  • target is handling logic related with http, rgc related framework
  • call NewSelector().GenerateSolution()

• layer 2: (updated on 06302020, this layer has been broken into two layers)
  • Selector is the layer contains logic for how to select charge stations, such as
    * whether need charge or not
    * is destination reachable by single charge
    * multiple charge station solution finding, which could be search along route or charge station based routing, implemented by other packages
  • solution and GenerateSolution abstract the interface for how to generate multiple charge station solution
  • stationgraph implements the GenerateSolution interface, and this package represents algorithm, graph in this diagram
  • chargingstrategy abstract logic of charge which supports calculation in stationgraph

• layer 3: chargestation abstract logic related with how to handle chargestations
  • The major abstraction is value object of Place and operations(usecases) on that object
  • topological_querier_interface
  • spatial_querier_interface
  • place_algorithm
  • more details could go to below

File structure

├── api
│   └── oasis
│       └── request.go
│       └── response.go
│
├── cmd
│   └── oasis
│   └── place-connectivity-gen
│
├── service/oasis
│   │         
│   ├── userinterface
│   │   ├── http 
│   │          └── handler.go
│   │         
│   ├── solution
│   │          └── selector
│   │               └── current files in selectionstrategy
│   │          ├── domain
│   │          │   ├── entity
│   │          │   │      └── solution.go
│   │          │   ├── usecases
│   │          │          └── solution_interface.go
│   │          └── stationgraph
│   │          └── chargingstrategy
│   │          └── chargestation
│   │               ├── domain
│   │               │   ├── entity
│   │               │         └── place.go
│   │               │   ├── usecases
│   │               │         └── topological_querier_interface.go
│   │               │         └── spatial_querier_interface.go
│   │               │         └── location_querier_interface.go  // may be put into spatial_querier_interface.go
│   │               │         └── place_algorithm.go
│   │               │ 
│   │               │ 
│   │               ├── repository   // communication with other services
│   │               │      └── connector_interface.go
│   │               │      └── osrmconnector
│   │               │      └── searchconnector
│   │               │ 
│   │               ├── spatialquerier
│   │               │      └── current files in spatialindexer, implements spatial querier interface
│   │               │ 
│   │               ├── topoquerier
│   │               │      └── current files in stationconnquerier, implements topological_querier_interface
│   │               │ 
│   │               ├── placealgorithm
│   │               │      └── current files in stationfinder except querier_impl_by_stationfinder
│   │               │ 
│   │               ├── topobuilder
│   │               │      └── current files in connectivitymap
│   │               │ 

place.go

// Place records place(location, point of interest) related information such as
// ID and location
// Place represents charge stations for most of times for OASIS service, but it 
// could also represent for a user select location such as original location or
// destination location.
type Place struct {
   ID       PlaceID
   Location *nav.Location
}

// PlaceID defines ID for given place(location, point of interest)
// The data used for pre-processing must contain valid PlaceID, which means it
// either a int64 directly or be processed as int64
type PlaceID int64

topological_querier_interface.go

// TopoQuerier used to return topological information for places
type TopoQuerier interface {

   // GetNearByPlaces finds near by stations by given placeID and return them in recorded sequence
   // Returns nil if given placeID is not found or no connectivity
   GetNearByPlaces(placeID common.PlaceID) []*common.RankedPlaceInfo

   // LocationQuerier returns *nav.location for given placeID
   LocationQuerier
}

spatial_querier_interface.go

// SpatialQuerier answers special query
type SpatialQuerier interface {

   // GetNearByPlaceIDs returns a group of places near to given center location
   GetNearByPlaceIDs(center nav.Location, radius float64, limitCount int) []*common.PlaceInfo
}

location_querier_interface.go

// LocationQuerier returns *nav.location for given placeID
type LocationQuerier interface {

   // GetLocation returns *nav.Location for given placeID
   // Returns nil if given placeID is not found
   GetLocation(placeID PlaceID) *nav.Location
}

place_algorithm.go

// Algorithm contains algorithm implemented based on NearbyStationsIterator
type Algorithm interface {
   // CalculateWeightBetweenNeighbors accepts locations array, which will search for nearby
   // charge stations and then calculate weight between stations, the result is used to
   // construct graph.
   CalculateWeightBetweenNeighbors(locations []*nav.Location,
      oc *osrmconnector.OSRMConnector,
      finder StationFinder) chan stationfindertype.WeightBetweenNeighbors

   // FindOverlap finds overlap charge stations from given two iterators
   FindOverlap(iterF stationfindertype.NearbyStationsIterator,
      iterS stationfindertype.NearbyStationsIterator) []*stationfindertype.ChargeStationInfo
}

solution_interface.go

// SolutionGenerator generates OASIS solutions 
type SolutionGenerator() interface {
   // GenerateOptimumSolutions creates optimal charge solutions
   GenerateOptimumSolutions() []*solution.Solution
}

Updated on 07222020: for actions please go to #352 (comment)

[CodeBear801]

handler

Handler accepts oasis.Request and put oasis.Response to certain channel.

to do:

• move all http related logic into handler, such as http.ResponseWriter.WriterHeader from GenerateSolutions4MultipleCharge
• move all logic from handler such as osrmhelper.RequestRoute4InputOrigDest, selectionstrategy.HasEnoughEnergy to package selectionstrategy

selectionstrategy(selector)

It accepts `oasis.Request` and generates `oasis.Response`.

It will generate internal `solution` format following such logic:
- detect wether destination is reachable or not
- detect whether charge is needed or not
- detect whether destination is reachable via single charge, find best solution
- best solution for multiple charge
   + SearchAlongRoute
   + ChargeStationBasedStrategy

to do:

• error code definition
• mock and testing format for multiple charge

Package stationgraph

Ideally, stationgraph should able to let people easy to implment graph algorithm based on graph interface

https://user-images.githubusercontent.com/16873751/81879163-d60e6500-953e-11ea-9d49-f9ccae39cccc.png

algorithm

      // relax
      node := g.Node(currID)
      for _, targetID := range g.AdjacentNodes(currID) {
         if g.Edge(currID, targetID) == nil {
            glog.Errorf("No connectivity between %+v and %+v which is unexpected, check your logic.\n", currID, targetID)
         }

         len := g.Edge(currID, targetID).Distance
         t := g.Edge(currID, targetID).Duration

         // todo
         // !g.Node(currID).tooNearToCurrentNode(g.Node(targetID), len)
         if g.Node(currID).reachableByDistance(len) {
            chargeTimeNeeded := g.Node(targetID).calcChargeTime(node, len, g.ChargeStrategy())
            if m.add(targetID, currID, len, chargeTimeNeeded+t) {
               g.Node(targetID).updateArrivalEnergy(node, len)
               g.Node(targetID).updateChargingTime(chargeTimeNeeded)
            }
         }
      }

• Dijkstra should only depend on Graph
• Node should be a value object, move its functionality to other places, such as chargestrategy, only keep setter and getter there
• chargestrategy should provide functionality to
  • isTargetDistanceReachable()
  • calculateArrivalEnergy
  • calculateChargingTime

station_graph

• Current station_graph_test.go is more like integration test, and which expose the implemenation detail of a connectivity interface, which should be replaced to mock: when(input)->Then(returns) for interfaces

graph_mock

• change name from mockGraph to fakeGraph

stationfinder

• put CalcWeightBetweenChargeStationsPair as internal function

package chargingstrategy

• change null_charge_strategy to fake_charge_strategy
• change fake_charge_strategy to simple_charge_strategy

[wangyoucao577]

Looks really good!

Some questions for discussing:

• cmd/oasis->cmd/oasisd
• cmd/place-connectivity-gen->cmd/place-connectivity-builder
• put handler.go in service/oasis directly
• put solution.go and solution_interface.go in service/oasis/solution directly (what I'm learning from recently ranking service api/osrm refactoring is that don't over splitting packages)
• what's the relationship between selector and chargestrategy?
• why name repository for the connectors?
• Maybe it's time to have a doc along with the(https://github.com/Telenav/osrm-backend/blob/master/integration/doc/oasis/api.md) that descibes algorithms of oasis to help to understand the code, ha!

[CodeBear801]

Looks really good!

[Perry] Thanks for your feedback, more strength to move on.

Some questions for discussing:

• cmd/oasis->cmd/oasisd

[Perry] Also think about to make this change.

• cmd/place-connectivity-gen->cmd/place-connectivity-builder

[Perry] agree

• put handler.go in service/oasis directly
• put solution.go and solution_interface.go in service/oasis/solution directly (what I'm learning from recently ranking service api/osrm refactoring is that don't over splitting packages)

[Perry] yes, don't over splitting package

• what's the relationship between selector and chargestrategy?

[Perry] selector implements high level functions, such as detecting whether no charge is needed, or just one charge could reach destination, or multiple charges
chargestrategy is a package which abstracts time spend in charge stations and new energy got.
Let me think more about names and how to make there relationship more clear.

• why name repository for the connectors?

[Perry] I saw the name has been used here and here, seems people like to put logic which communicate with external components like message bus, database into a folder called repository

[Perry] Update on 05282020

Repository is an abstraction over persistent storage, which hides the details of data access by pretending that all data is in memory. Here, I used which mainly hide communication with other services, repository might not be a good name here.

• Maybe it's time to have a doc along with the(https://github.com/Telenav/osrm-backend/blob/master/integration/doc/oasis/api.md) that descibes algorithms of oasis to help to understand the code, ha!

[Perry] Totally agree.

[CodeBear801]

Discussion with @wangyoucao577 on 06012020.

handler

• http request
• http response
• init()->calc(input, output)

---

• selector(Name need adjusted)

  • init

  • response

  • • whether need charge or not
    • is destination reachable by single charge
    • multiple charge station solution finding, which could be search along route or charge station based routing, implemented by other packages

  • stationgraph.NewStationGraph().GenerateChargeSolutions() -> solution->oasis.response

  • solutions

  • generatesolutions()

---

• stationgraph

  • search along route
  • charge station based routing

• chargingstrategy

  • station 1 : 60%, 80%, 100%

  node(energy)

---

connectivity

• connectivity_interface
  getConnectvity()
• spatial_index_interface
  getSpatial(point, charge station point)
• place_iterator
  iterator

[CodeBear801]

Actions:

• Refactor Oasis service for entrypoint Refactor Oasis service for entrypoint #363
• Refactor Oasis service for Graph and Place layer Refactor Oasis service for Graph and Place layer #364