lddl / ch Goto Github PK

package main

import (
	"github.com/LdDl/ch"
	"fmt"
	"os"
	"bufio"
	"io"
	"strconv"
	"encoding/csv"
)


func main() {
	g := ch.Graph{} // Prepare variable for storing graph
	fmt.Println("Preparing Graph")
	graphFromCSV(&g, "data/graph.csv") // Import CSV-file file into programm
	fmt.Println("Preparing Contracted")
	g.PrepareContracts() // Compute contraction hierarchies
	fmt.Println("writing to file")
	err := g.ExportToFile("data/export_pgrouting.csv")
	if err != nil {
		fmt.Println(err)
		return
	}

}

func graphFromCSV(graph *ch.Graph, fname string) error {
	file, err := os.Open(fname)
	if err != nil {
		return err
	}
	defer file.Close()
	reader := csv.NewReader(bufio.NewReader(file))

	reader.Comma = ';'

	_, err = reader.Read()
	if err != nil {
		return err
	}

	for {
		record, err := reader.Read()
		if err == io.EOF {
			break
		}
		source, err := strconv.ParseInt(record[0], 10, 64)
		if err != nil {
			return err
		}

		target, err := strconv.ParseInt(record[1], 10, 64)
		if err != nil {
			return err
		}


		oneway := record[2]
		weight, err := strconv.ParseFloat(record[3], 64)
		if err != nil {
			return err
		}

		err = graph.CreateVertex(source)
		if err != nil {
			return err
			fmt.Println("This is the Source")
			fmt.Println(err)
		}
		err = graph.CreateVertex(target)
		if err != nil {
			return err
			fmt.Println("This is the Target")
			fmt.Println(err)
		}

		err = graph.AddEdge(source, target, weight)
		if err != nil {
			return err
		}
		if oneway == "B" {
			err = graph.AddEdge(target, source, weight)
			if err != nil {
				return err
			}
		}
	}
	return nil
}

package main

import (
	"github.com/LdDl/ch"
	"fmt"
	"os"
	"bufio"
	"io"
	"strconv"
	"encoding/csv"
	// "github.com/gin-gonic/gin"
)


func main() {
	g := ch.Graph{} // Prepare variable for storing graph
	fmt.Println("Preparing Graph")
	graphFromCSV(&g, "data/export_pgrouting.csv") // Import CSV-file file into program
	u := int64(1794303) // Define source vertex
	v := int64(1787974) // Define target vertex
	fmt.Println("Preparing Shortest Path")
	ans, path := g.ShortestPath(u, v) // Get shortest path and it's cost between source and target vertex
	fmt.Println(ans)
	fmt.Println(path)
}

func graphFromCSV(graph *ch.Graph, fname string) error {
	file, err := os.Open(fname)
	if err != nil {
		return err
	}
	defer file.Close()
	reader := csv.NewReader(bufio.NewReader(file))

	reader.Comma = ';'
	// reader.LazyQuotes = true

	// Read header
	_, err = reader.Read()
	if err != nil {
		return err
	}

	for {
		record, err := reader.Read()
		if err == io.EOF {
			break
		}
		source, err := strconv.ParseInt(record[0], 10, 64)
		if err != nil {
			return err
		}
	//	fmt.Println("This is the Source")
	//	fmt.Println(source)

		target, err := strconv.ParseInt(record[1], 10, 64)
		if err != nil {
			return err
		}

	//	fmt.Println("This is the Target")
	//	fmt.Println(target)

		// if intinslice(source, []int{5606, 5607, 255077, 238618}) == false && intinslice(target, []int{5606, 5607, 255077, 238618}) == false {
		// 	continue
		// }

		oneway := record[2]
		weight, err := strconv.ParseFloat(record[3], 64)
		if err != nil {
			return err
		}

		err = graph.CreateVertex(source)
		if err != nil {
			return err
			fmt.Println("This is the Source")
			fmt.Println(err)
		}
		err = graph.CreateVertex(target)
		if err != nil {
			return err
			fmt.Println("This is the Target")
			fmt.Println(err)
		}

		err = graph.AddEdge(source, target, weight)
		if err != nil {
			return err
		}
		if oneway == "B" {
			err = graph.AddEdge(target, source, weight)
			if err != nil {
				return err
			}
		}
	}
	return nil
}

// computeImportance Update importance of vertex
func (vertex *Vertex) computeImportance() {
	// Worst possible shortcuts number throught the vertex is: NumWorstShortcuts = NumIncomingEdges*NumOutcomingEdges
	vertex.shortcutCover = len(vertex.inIncidentEdges) * len(vertex.outIncidentEdges)
	// Number of total incident edges is: NumIncomingEdges+NumOutcomingEdges
	vertex.incidentEdgesNum = len(vertex.inIncidentEdges) + len(vertex.outIncidentEdges)
	// Edge difference is between NumWorstShortcuts and TotalIncidentEdgesNum
	vertex.edgeDiff = vertex.shortcutCover - vertex.incidentEdgesNum
	// [+] Spatial diversity heuristic: for each vertex maintain a count of the number of neighbors that have already been contracted [vertex.delNeighbors], and add this to the summary importance
	// note: the more neighbours have already been contracted, the later this vertex will be contracted in further.
	// [+] Bidirection edges heuristic: for each vertex check how many bidirected incident edges vertex has.
	// note: the more bidirected incident edges == less important vertex is.
	vertex.importance = vertex.edgeDiff*14 + vertex.incidentEdgesNum*25 + vertex.delNeighbors*10 - vertex.bidirectedEdges()
}

// update Importance of vertex "on demand" as follows:
// Before contracting vertex with currently smallest Importance, recompute its Importance and see if it is still the smallest
// If not pick next smallest one, recompute its Importance and see if that is the smallest now; If not, continue in same way
vertex := heap.Pop(graph.pqImportance).(*Vertex)
vertex.computeImportance()
if graph.pqImportance.Len() != 0 && vertex.importance > graph.pqImportance.Peek().importance {
    graph.pqImportance.Push(vertex)
    continue
}

type Vertex struct {
	...
	orderPos int
        ...
}

func (vertex *Vertex) OrderPos() int {
	return vertex.orderPos
}
func (vertex *Vertex) SetOrderPos(orderPos int){
	vertex.orderPos = orderPos
}

// 		from_vertex_id - int64, ID of source vertex
// 		to_vertex_id - int64, ID of arget vertex
// 		f_internal - int64, Internal ID of source vertex
// 		t_internal - int64, Internal ID of target vertex
// 		weight - float64, Weight of an edge
// 		via_vertex_id - int64, ID of vertex through which the contraction exists (-1 if no contraction)
// 		v_internal - int64, Internal ID of vertex through which the contraction exists (-1 if no contraction)

// 		from_vertex_id - int64, ID of source vertex
// 		to_vertex_id - int64, ID of arget vertex
// 		f_internal - int64, Internal ID of source vertex
// 		t_internal - int64, Internal ID of target vertex
// 		weight - float64, Weight of an edge
// 		via_vertex_id - int64, ID of vertex through which the contraction exists (-1 if no contraction)
// 		v_internal - int64, Internal ID of vertex through which the contraction exists (-1 if no contraction)

// Header of main CSV-file containing information about vertices:
// 		vertex_id - int64, ID of vertex
// 		internal_id - int64, internal ID of arget vertex
// 		order_pos - int, Position of vertex in hierarchies (evaluted by library)
// 		importance - int, Importance of vertex in graph (evaluted by library)

// 		from_vertex_id - int64, ID of source vertex
// 		to_vertex_id - int64, ID of arget vertex
// 		f_internal - int64, Internal ID of source vertex
// 		t_internal - int64, Internal ID of target vertex
// 		weight - float64, Weight of an edge

// Header of main CSV-file containing information about vertices:
// 		vertex_id - int64, ID of vertex
// 		internal_id - int64, internal ID of arget vertex
// 		order_pos - int, Position of vertex in hierarchies (evaluted by library)
// 		importance - int, Importance of vertex in graph (evaluted by library)

// 		from_vertex_id - int64, ID of source vertex
// 		to_vertex_id - int64, ID of arget vertex
// 		f_internal - int64, Internal ID of source vertex
// 		t_internal - int64, Internal ID of target vertex
// 		weight - float64, Weight of an contraction
// 		via_vertex_id - int64, ID of vertex through which the contraction exists
// 		v_internal - int64, Internal ID of vertex through which the contraction exists

type Vertex struct {
	...
	importance    int
        ...
}

func (vertex *Vertex) Importance() int {
	return vertex.importance
}
func (vertex *Vertex) SetImportance(importance int){
	vertex.importance = importance
}

type Graph struct {
    frozen bool
}
func (g *Graph) ModifyData(....) error {
    if g.frozen {
        return "can't modify data in frozen graph"
    }
}
func (g *Graph) PrepareContracts() error {
    {
    // graph preparation
    }
    g.Freeze()
}
// Freeze - Exported
func (g *Graph) Freeze() {
    g.frozen = true
}
// unfreeze - unexported
func (g *Graph) unfreeze() {
    g.frozen = false
}

...distance.distance = vertex.distance.distance + cost
...distance.contractionID = contractionID 
...distance.sourceID = sourceID

// checkID Checks if both source's and target's contraction ID are not equal
func (graph *Graph) checkID(source, target int64) bool {
	s := graph.Vertices[source].distance
	t := graph.Vertices[target].distance
	return s.contractionID != t.contractionID || s.sourceID != t.sourceID
}