v1.7.8 - Fix ManyToMany

What's new

1. Replaced rounding in tests for comparing floats to epsilon threshold
2. ManyToMany was broken due map[] lookup error. See the ref.: 2d61de4

v1.7.7 - Minor

What's new

Minor improvements of code.

v1.7.6 - Fix import

What's new

1. There were not closing file. So fix this bug - 9413bf1#diff-5a3040133bc8fe1d1df5b1e886d71838a22430b148df2e80c71bdbc741e52be1
2. Little naming changes

v1.7.5 - Update export functions

What's new

Separate code of ExportToFile() in different blocks:

• ExportEdgesToFile
• ExportVerticesToFile
• ExportShortcutsToFile

There is a little overhead due the loop repeats, but 3-d party packages now can export only needed data (especially shortcuts)

v1.7.4 - Update shortcut getter

What's new

1. Update method graph.IsShortcut.
   Old:

// IsShortcut Returns true if edge is a shortcut (edge defined as two vertices)
func (graph *Graph) IsShortcut(labelFromVertex, labelToVertex int64) (ok bool) {
	_, ok = graph.shortcuts[labelFromVertex][labelToVertex]
	return ok
}

New - Now maps proper source/target IDs + returns ViaVertex ID:

// IsShortcut Returns (vertex_id; true) if edge is a shortcut (edge defined as two vertices)
//
// If source or taget vertex is not found then returns (-1; false)
// If edge is not a shortcut then returns (-1; false)
//
func (graph *Graph) IsShortcut(labelFromVertex, labelToVertex int64) (int64, bool) {
	source, ok := graph.mapping[labelFromVertex]
	if !ok {
		return -1, ok
	}
	target, ok := graph.mapping[labelToVertex]
	if !ok {
		return -1, ok
	}
	shortcut, ok := graph.shortcuts[source][target]
	if !ok {
		return -1, ok
	}
	return graph.Vertices[shortcut.ViaVertex].Label, ok
}

v1.7.3 - New getters

What's new

1. Added new method graph.IsShortcut.

// IsShortcut Returns true if edge is a shortcut (edge defined as two vertices)
func (graph *Graph) IsShortcut(labelFromVertex, labelToVertex int64) (ok bool) {
	_, ok = graph.shortcuts[labelFromVertex][labelToVertex]
	return ok
}

2. Added new method graph.FindVertex

// FindVertex Returns index of vertex in graph
//
// labelExternal - User defined ID of vertex
// If vertex is not found then returns (-1; false)
//
func (graph *Graph) FindVertex(labelExternal int64) (idx int64, ok bool) {
	idx, ok = graph.mapping[labelExternal]
	if !ok {
		return -1, ok
	}
	return
}

v1.7.2 - Eliminate shortcuts duplicates

What's new

1. Added usefull methods on *Vertex such as: delete / update incident edge.
2. Eliminated shortcut duplicates, e.g.:

A -> B -> C on some iteration gives shortcut cost 205.
A -> G -> C on some iteration gives shortcut cost less 195.
So we should eliminate A-B-C and create A-G-C

v1.7.1 - Export/Import: eliminated duplicate writes

UPDATE

1. Do not write contraction duplicates into CSV-file
2. Do not write edges duplicates into CSV-file
3. Update Graph struct:
   replaced

// ...
contracts    map[int64]map[int64]int64
// ...

with

// ...
type ContractionPath struct {
	ViaVertex int64
	Cost      float64
}
// ...
contracts    map[int64]map[int64]*ContractionPath
// ...

For more infromation look into this PR: #16

v1.7.0 - Export/Import function.

Export and import function have got an update.
Issue link for updated feature: #14.

Now export function generates 3 files: for vertices, for edges and for contractions.
Import function was adapted to handle those 3 files.

Now it is easier to build external libraries such as Horizon and osm2ch

v1.6.0 - Isochrones

We glad to introduce isochrones evaluation (corresponding issue is #8 )
See ref. https://wiki.openstreetmap.org/wiki/Isochrone and https://en.wikipedia.org/wiki/Isochrone_map
Corresponding test - https://github.com/LdDl/ch/blob/master/isochrones_test.go#L7

Isochrones implemented as breadth-first search algorithm - https://en.wikipedia.org/wiki/Breadth-first_search

Real world application: evalute point of interesets in search radius, where radius is defined as not great circle distance or euclidean distance, but as graph travel path.

Important note: BFS doesn't guarantee shortest path