nicolewhite

Solve the Widest Path Problem in Cypher

The widest path problem has a number of applications in many domains, including networking, shipping, and emergency response. Assuming the relationships between nodes in a graph are weighted by a capacity of some sort, the widest path problem involves finding the path between two nodes that maximizes the minimum capacity in the path.

Below, each node is a router in a city and the relationships between the routers have a bandwidth property indicating the bandwidth capacity of the two routers' connection. The direction of the connection is arbitrary.

nicolewhite

library(RNeo4j)
library(igraph)

graph = startGraph("http://localhost:7474/db/data/")
clear(graph)

create_users = "FOREACH (i IN RANGE(1,50) | CREATE (:User {id:i, name:'name ' + i}))

                WITH 1 AS dummy
                

nicolewhite

library(RNeo4j)

graph = startGraph("http://localhost:7474/db/data/")

# Create time tree.
# Copied from http://www.markhneedham.com/blog/2014/04/19/neo4j-cypher-creating-a-time-tree-down-to-the-day/
timetree = "WITH range(2011, 2014) AS years, range(1,12) as months
            FOREACH(year IN years | 
              MERGE (y:Year {year: year})
              FOREACH(month IN months | 

nicolewhite

OSCON Twitter Graph

During the OSCON conference, the Neo4j team will be collecting tweets and adding them to a graph. Below is an example database of 15 tweets.

create (_0:`Tweet` {`text`:"RT @BrentVukmer: The worst things so far about @oscon - too many choices, not enough time."})
create (_1:`User` {`username`:"oscon"})

nicolewhite

import requests
import os
import time
from py2neo import neo4j

# Connect to graph and add constraints.
url = os.environ['NEO4J_URL']
# url = "http://localhost:7474/db/data/"
graph = neo4j.GraphDatabaseService(url)

nicolewhite

For Nick

Sample Data

I tried to copy your data model as I understood it. I created two User nodes each with five View nodes. User 1’s sequence of views touches a distinct set of Page nodes; User 2’s sequence of views is not a distinct set; User 2 visits the analytics page twice.

nicolewhite

import tweepy
from tweepy import Cursor
import unicodecsv
from unidecode import unidecode

# Authentication and connection to Twitter API.
consumer_key = ""
consumer_secret = ""
access_key = ""
access_secret = ""

nicolewhite

Datasets for Graph Hack 2014.

All stores are Neo4j 2.1.3.

Transportation

Flights

What is related, and how?

Flight	ORIGIN Airport

nicolewhite

<NotepadPlus>
    <UserLang name="Cypher" ext="cypher" udlVersion="2.1">
        <Settings>
            <Global caseIgnored="yes" allowFoldOfComments="yes" foldCompact="no" forcePureLC="0" decimalSeparator="0" />
            <Prefix Keywords1="no" Keywords2="no" Keywords3="no" />
        </Settings>
        <KeywordLists>
            <Keywords name="Comments">00// 01 02 03// 04</Keywords>
            <Keywords name="Operators1">( ) , = :</Keywords>
            <Keywords name="Folders in comment, open">CASE</Keywords>

nicolewhite

create (_0:`Gate` {`number`:1})
create (_1:`Gate` {`number`:2})
create (_2:`Gate` {`number`:3})
create (_3:`Gate` {`number`:4})
create (_4:`Gate` {`number`:5})
create (_5:`Gate` {`number`:6})
create (_6:`Gate` {`number`:7})
create (_7:`Gate` {`number`:8})
create (_8:`Gate` {`number`:9})
create (_9:`Gate` {`number`:10})