Example codes

Takeru Inoue edited this page Nov 24, 2015 · 16 revisions

This page shows several examples with Graphillion.

Congested roads - edge inclusion and exclusion

This problem is found in the entrance exam to Hokkaido University, 2014; the original version is here (4th question).

Consider paths from S (21) to G (5) with eight edges (i.e., 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
  1. How many paths are there that pass through edge 'a'?
  2. How many paths are there that pass through edge 'b' without 'a'?
  3. 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 average_time(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.', average_time(paths)

The least edge constraint is indispensable to allow test-takers to count the paths efficiently by manual with the binomial coefficient, but Graphillion allows us to solve this problem without the constraint, as follows.

paths = GraphSet.paths(S, G)  # without least edge constraint

print "1.", len(paths.including(a))
print "2.", len(paths.excluding(a).including(b))
print "3.", average_time(paths)

Ekillion - weighted edges and vertices

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
  1. How many paths are there from Tokyo to Shinagawa?
  2. Find the most longest path from Tokyo to Shinagwa.
  3. Find a path going by Yotsuya from Tokyo to Shinagwa.
  4. 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()

Collection of path sets

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  # degree of vertex v is one
    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)

Impact of universe list

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']

Network reliability

Given a set of vertices and probabilities of link availability, we calculate the probability such that all the vertices in the set are connected.

Consider the following graph, which has five vertices and six edges. Each link would be available with probability of 0.9.

 1 --- 2 --- 4
 |     |     |
 +---- 3 --- 5

Graphillion tells us that three vertices, 1, 3, and 4 are connected with probability of 0.967383, as follows.

from graphillion import GraphSet

GraphSet.set_universe([(1,2), (1,3), (2,3), (2,4), (3,5), (4,5)])

# find all subgraphs that connect vertices 1, 3, and 4
gs = GraphSet({}).including(GraphSet.connected_components([1,3,4]))

# calculate the probability such that any of the subgraphs happens.
probabilities = {(1,2): .9, (1,3): .9, (2,3): .9, (2,4): .9, (3,5): .9, (4,5): .9}
print gs.probability(probabilities)

Vertex list representation of path and cycle

Graphillion represents a path or a cycle as a set of edges, like [(1, 2), (2, 3), (3, 4)], or as a NetworkX graph object. However, you might like to simply use a vertex list, [1, 2, 3, 4], to represent a path or a cycle. A set of edges and NetworkX graph object can be easily converted into a simple vertex list, as follows.

import networkx as nx
E = [(1, 2), (2, 3), (3, 4)]  # set of edges, representing path
G = nx.Graph(E)  # NetworkX graph object

print list(nx.dfs_preorder_nodes(G, 1))  # [1, 2, 3, 4]
Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.