-
Notifications
You must be signed in to change notification settings - Fork 40
Example codes
This page shows several example codes with Graphillion.
This is originally a problem in the entrance exam to Hokkaido University, 2014; the original version is found here.
Consider paths from S (21) to G (5) with eight edges (least edge paths). Each edge requires two minutes to pass through, but edge 'a' (17,18) takes one minute and edge 'b' (10,15) is eight minutes.
1 --- 2 --- 3 --- 4 --- G
| | | | |
6 --- 7 --- 8 --- 9 -- 10
| | | | ! b
11 -- 12 -- 13 -- 14 -- 15
| | | | |
16 -- 17 == 18 -- 19 -- 20
| | a | | |
S -- 22 -- 23 -- 24 -- 25
- How many paths are there that pass through edge 'a'?
- How many paths are there that pass through edge 'b' without 'a'?
- How long does it take from S to G on average?
from graphillion import GraphSet
import graphillion.tutorial as tl
GraphSet.set_universe(tl.grid(4, 4))
S, G, a, b, L = 21, 5, (17,18), (10,15), 8
paths = GraphSet.paths(S, G).len(L)
print '1.', len(paths.including(a))
print '2.', len(paths.excluding(a).including(b))
def E(paths):
t = 0.
for p in paths:
for e in p:
if e == a: t += 1
elif e == b: t += 8
else : t += 2
return t / len(paths)
print '3.', E(paths)The least edge constraint is indispensable to allow test-takers to count the paths efficiently with the binomial coefficient, but Graphillion allows us to solve this problem without the constraint, as follows.
paths = GraphSet.paths(S, G)
print "1.", len(paths.including(a))
print "2.", len(paths.excluding(a).including(b))
print "3.", E(paths)We examine a key algorithm of Ekillion, which is a Web service enumerating all train paths between a given pair of stations.
Assume the following railway map, in which distances between stations are shown in parentheses, and lunch boxes are sold at Shinjuku and Yotsuya stations.
+--(11.3)------------------------- Ueno
| |
| (3.6)
| |
Shinjuku --(3.7)-- Yotsuya --(6.6)-- Tokyo
| |
| (6.8)
| |
+--(10.6)-------------------- Shinagawa
- How many paths are there from Tokyo to Shinagawa?
- Find the most longest path from Tokyo to Shinagwa.
- Find a path going by Yotsuya from Tokyo to Shinagwa.
- Find a path with most lunch stations from Tokyo to Shinagwa.
from graphillion import GraphSet
universe = [('Tokyo' , 'Shinagawa', 6.8),
('Shinagawa', 'Shinjuku' , 10.6),
('Shinjuku' , 'Ueno' , 11.3),
('Ueno' , 'Tokyo' , 3.6),
('Tokyo' , 'Yotsuya' , 6.6),
('Yotsuya' , 'Shinjuku' , 3.7)]
GraphSet.set_universe(universe)
paths = GraphSet.paths('Tokyo', 'Shinagawa')
print '1.', len(paths)
print '2.', paths.max_iter().next()
print '3.', paths.including('Yotsuya').choice()
# Since weights have to be set on vertices, not edges like the above,
# for indicating lunch stations, we give weights on edges of lunch
# stations as follows.
#
# +--(0.5)------------------------ Ueno
# | |
# | (0)
# | |
# Shinjuku --(1)-- Yotsuya --(0.5)-- Tokyo
# | |
# | (0)
# | |
# +--(0.5)------------------- Shinagawa
lunch_weights = {}
lunch_stations = ['Shinjuku', 'Yotsuya']
for e in universe:
e = (e[0], e[1]) # remove distance
lunch_weights[e] = 0.5 * len([v for v in lunch_stations if v == e[0] or v == e[1]])
print '4.', paths.max_iter(lunch_weights).next()The low-level GraphSet constructor named graphs() can specify arbitrary complicated graph types. With this constructor, find all sets of a path between 1 and 5 and another path between 21 and 25, as follows.
1 2 3 4 5
| |
6 --- 7 --- 8 9 -- 10
| |
11 -- 12 13 -- 14 15
| |
16 17 18 19 -- 20
| | | |
21 22 -- 23 -- 24 25
from graphillion import GraphSet
import graphillion.tutorial as tl
GraphSet.set_universe(tl.grid(4, 4))
degree_constraints = {}
for v in range(1, 26):
if v == 1 or v == 5 or v == 21 or v == 25:
degree_constraints[v] = 1
else:
degree_constraints[v] = range(0, 3, 2) # zero or two
path_sets = GraphSet.graphs(vertex_groups=[(1, 5), (21, 25)],
degree_constraints=degree_constraints,
no_loop=True)
print len(path_sets)This problem examines an impact of the universe edge list on the memory/storage footprint.
4--8
/
2--5
/
1
\
3--6
\
7
We consider the above tree as our universe, and enumerate subtrees with the following constraints; these subtrees must consist of two or more edges, and they must include at least one of edges (1,2) and (2,4).
Find the best order of the universe edge list in terms of the memory/storage footprint, with the Monte-Carlo method by randomly sorting the universe edge list.
from graphillion import GraphSet
from random import shuffle
universe = [(1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (4,8)]
best = { 'list': None, 'footprint': 99999 }
for _ in range(100):
shuffle(universe)
GraphSet.set_universe(universe, traversal='as-is') # without re-ordering the universe list
trees = GraphSet.trees().larger(1);
trees = trees.including((1,2)) | trees.including((2,4))
footprint = len(trees.dumps()) # size of internal representation
if footprint < best['footprint']:
best = { 'list': universe, 'footprint': footprint }
print best['list']