Data

Tools

Indexes

Applications

Experiments

Open Source Science

idron

Inferring Distance Rankings on Networks

https://github.com/koeppl/idron

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (10.8%) to scientific vocabulary

Keywords

clojure graph-algorithms shortest-path skyline-query
Last synced: 6 months ago · JSON representation ·

Repository

Inferring Distance Rankings on Networks

Basic Info
Statistics
  • Stars: 0
  • Watchers: 2
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Topics
clojure graph-algorithms shortest-path skyline-query
Created almost 12 years ago · Last pushed almost 4 years ago
Metadata Files
Readme Citation

README.md

IDRoN, a Clojure Library for Inferring Distance Rankings on Networks

Synopsis

We deal with the problem of solving a ranking query from a single source to multiple targets. A ranking is a weak ordering of targets with respect to their distances to the source. The query is evaluated on a routing network, i.e., a directed graph with a cost function. For example, this problem translates into finding nearest points of interests (POIs). Common shortest path searches are time expensive in either pre-calculation or evaluation. Often, the user is preliminarily satisfied with just the ranking, i.e., the distances or the way to follow are secondary information. Hence, the question arises whether it is possible to find an optimal algorithm for this limited problem.

Project Goals

We deliver a library that sits on top of Tinkerpop's graph library that * generates routing networks based on * synthetic data (either internal or external by Jung * real Open Street Map-data * provides shortest path solvers (A* and Dijkstra) * uses one of the provided shortest path solvers for our novel algorithm * evaluates and tests this algorithm with the incanter library

Implementation

The library is implemented in Clojure 1.5. We used Clojure with Tinkerpop because * Tinkerpop is a great interface for accessing a multitude of graph databases (similar to JDBC for relational databases). * Clojure can compile to the JVM. * Clojure is a very expressive language that keeps implementation details away from the actual description of the algorithm. * Clojure's asynchronous nature is perfect to describe our developed algorithm.

Examples

  • Run lein run import /database/mu ~/mu.osm true to create a fresh Neo4J-database /database/mu with data imported from the OSM-XML file mu.osm.
  • Run lein run plot /tmp to plot an evaluation of the implemented algorithms on some graphs to the directory /tmp.

Owner

  • Name: Dominik Köppl
  • Login: koeppl
  • Kind: user
  • Location: Japan
  • Company: Tokyo Medical and Dental University

Researcher on string compression, combinatorics and succinct data structures.

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Köppl"
  given-names: "Dominik"
  orcid: "http://orcid.org/0000-0002-8721-4444"
title: "Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks"
url: "https://github.com/koeppl/idron"
preferred-citation:
  type: article
  authors:
  - family-names: "Köppl"
    given-names: "Dominik"
    orcid: "http://orcid.org/0000-0002-8721-4444"
  doi: 10.3390/info13040168
  journal: "Information"
  start: 1  # First page number
  end: 28 # Last page number
  title: "Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks"
  year: 2022
  issue: 4
  volume: 13

GitHub Events

Total
Last Year

Dependencies

project.clj clojars
  • clj-logging-config 1.9.7
  • com.tinkerpop.blueprints/blueprints-core 2.4.0
  • com.tinkerpop.blueprints/blueprints-graph-jung 2.4.0
  • com.tinkerpop.blueprints/blueprints-neo4j-graph 2.4.0
  • com.tinkerpop.furnace/furnace 0.1.0-SNAPSHOT
  • incanter 1.5.4
  • jung/jung 1.7.6
  • org.clojars.gjahad/debug-repl 0.3.3
  • org.clojure/clojure 1.5.1
  • org.clojure/data.json 0.2.3
  • org.clojure/data.priority-map 0.0.4
  • org.clojure/data.xml 0.0.7
  • org.clojure/tools.logging 0.2.6
  • org.clojure/tools.nrepl 0.2.3
  • org.clojure/tools.trace 0.7.5