Commits

Kirill Simonov committed da517c2

Converted the project into a Python library.

Comments (0)

Files changed (30)

 .*.swp
 *.pyc
 *.png
-pycairo-*
+*.egg-info
+build
+dist
+Copyright (c) 2011 Kirill Simonov
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+of the Software, and to permit persons to whom the Software is furnished to do
+so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+

algorithm.py

-
-
-from model import (ensure, WithArcWeight, WithNodeRank, WithLayers, WithBeadOrder,
-                   WithGraphSize, WithNodeDimensions, WithGraphMargins,
-                   WithNodePosition, WithArcVertices, WithArcPolarity)
-import itertools
-
-
-def rank(graph):
-    return rank_feedback(graph)
-
-
-def rank_feedback(graph):
-    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
-    ensure(not graph.readable(WithNodeRank), "already with node ranks", graph)
-
-    graph.upgrade(WithNodeRank)
-
-    def get_cycle(forbidden):
-
-        path = []
-        active = {}
-        visited = set()
-
-        def dfs(node):
-            if node in visited:
-                return None
-            if node in active:
-                cycle = path[active[node]:]
-                return cycle
-            active[node] = len(path)
-            for arc in node.outgoing:
-                if arc in forbidden:
-                    continue
-                path.append(arc)
-                cycle = dfs(arc.target)
-                if cycle is not None:
-                    return cycle
-                path.pop()
-            visited.add(node)
-            return None
-
-        for node in graph.nodes:
-            cycle = dfs(node)
-            if cycle is not None:
-                return cycle
-        return None
-
-    def get_node_weights(forbidden):
-        weights = {}
-        active = set()
-
-        def dfs(node):
-            assert node not in weights and node not in active
-            active.add(node)
-            total = 0.0
-            for arc in node.outgoing:
-                if arc in forbidden:
-                    continue
-                if arc.target not in weights:
-                    weights[arc.target] = dfs(arc.target)
-                total += arc.weight.value + weights[arc.target]
-            return total
-
-        for node in graph.nodes:
-            if node not in weights:
-                weights[node] = dfs(node)
-        return weights
-
-    feedback = []
-    arc_weights = dict((arc, arc.weight.value) for arc in graph.arcs)
-
-    cycle = get_cycle(feedback)
-    while cycle is not None:
-        min_weight = min(arc_weights[arc] for arc in cycle)
-        for arc in cycle:
-            if arc_weights[arc] == min_weight:
-                feedback.append(arc)
-            arc_weights[arc] -= min_weight
-        cycle = get_cycle(feedback)
-
-    for arc in feedback[:]:
-        feedback.remove(arc)
-        cycle = get_cycle(feedback)
-        if cycle is not None:
-            feedback.append(arc)
-
-    node_weights = get_node_weights(feedback)
-    ordered_nodes = sorted(graph.nodes, key=(lambda node: node_weights[node]))
-    for value, node in enumerate(ordered_nodes):
-        node.set_rank(value)
-
-    graph.freeze(WithNodeRank)
-
-    return graph
-
-
-def rank_greedy(graph):
-    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
-    ensure(not graph.readable(WithNodeRank), "already with node ranks", graph)
-
-    graph.upgrade(WithNodeRank)
-
-    selected = []
-    while len(selected) < len(graph.nodes):
-        candidates = []
-        min_outdegree = None
-        for node in graph.nodes:
-            if node in selected:
-                continue
-            outdegree = sum(arc.weight.value for arc in node.outgoing
-                            if arc.target not in selected and arc.target is not node)
-            if min_outdegree is None or outdegree < min_outdegree:
-                candidates = [node]
-                min_outdegree = outdegree
-            elif outdegree == min_outdegree:
-                candidates.append(node)
-        if selected:
-            parent = selected[-1]
-            if set(parent.neighbors) & set(candidates):
-                candidates = [node for node in candidates if node in parent.neighbors]
-        next_node = None
-        min_degree = None
-        for node in candidates:
-            degree = (sum(arc.weight.value for arc in node.incoming
-                          if arc.origin not in selected and arc.origin is not node) +
-                      sum(arc.weight.value for arc in node.outgoing
-                          if arc.target not in selected and arc.target is not node))
-            if min_degree is None or degree < min_degree:
-                next_node = node
-                min_degree = degree
-        selected.append(next_node)
-
-    for value, node in enumerate(selected):
-        node.set_rank(value)
-
-    graph.freeze(WithNodeRank)
-
-    return graph
-
-
-def polarize(graph):
-    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
-    ensure(graph.readonly(WithNodeRank), "without node ranks", graph)
-    ensure(not graph.readable(WithArcPolarity), "already with arc polarity", graph)
-
-    graph.upgrade(WithArcPolarity)
-
-    nodes = graph.nodes_by_rank
-    polarity_by_arc = {}
-
-    node = nodes[0]
-    for next_node in nodes[1:]:
-        for arc in node.incoming:
-            if arc.origin in [node, next_node]:
-                polarity_by_arc[arc] = 0
-        for arc in node.outgoing:
-            if arc.target in [node, next_node]:
-                polarity_by_arc[arc] = 0
-        node = next_node
-
-    for polarity in [-1, 1]:
-        arcs_by_range = {}
-        weight_by_range = {}
-        for length in range(1, len(nodes)):
-            for start in range(len(nodes)-length):
-                end = start+length
-                if length == 1:
-                    arcs_by_range[start, end] = []
-                    weight_by_range[start, end] = 0.0
-                else:
-                    arcs = []
-                    weight = 0.0
-                    for arc in graph.arcs:
-                        if arc in polarity_by_arc:
-                            continue
-                        if ((arc.origin.rank.value == start and arc.target.rank.value == end) or
-                            (arc.origin.rank.value == end and arc.target.rank.value == start)):
-                            arcs.append(arc)
-                            weight += arc.weight.value
-                    best_sep = None
-                    for sep in range(start+1, end):
-                        if best_sep is None or (weight_by_range[start, sep]+weight_by_range[sep, end] >
-                                                weight_by_range[start, best_sep]+weight_by_range[best_sep, end]):
-                            best_sep = sep
-                    arcs += arcs_by_range[start, best_sep] + arcs_by_range[best_sep, end]
-                    weight += weight_by_range[start, best_sep] + weight_by_range[best_sep, end]
-                    arcs_by_range[start, end] = arcs
-                    weight_by_range[start, end] = weight
-        for arc in arcs_by_range[0, len(nodes)-1]:
-            polarity_by_arc[arc] = polarity
-
-    for arc in graph.arcs:
-        if arc in polarity_by_arc:
-            continue
-        start = min(arc.origin.rank.value, arc.target.rank.value)
-        end = max(arc.origin.rank.value, arc.target.rank.value)
-        left_crosses = 0.0
-        right_crosses = 0.0
-        for other_arc in graph.arcs:
-            polarity = polarity_by_arc.get(other_arc, 0)
-            if not polarity:
-                continue
-            other_start = min(other_arc.origin.rank.value, other_arc.target.rank.value)
-            other_end = max(other_arc.origin.rank.value, other_arc.target.rank.value)
-            if (start < other_start < end < other_end) or (other_start < start < other_end < end):
-                if polarity < 0:
-                    left_crosses += other_arc.weight.value
-                elif polarity > 0:
-                    right_crosses += other_arc.weight.value
-        if left_crosses < right_crosses:
-            polarity_by_arc[arc] = -1
-        else:
-            polarity_by_arc[arc] = +1
-
-    for arc in graph.arcs:
-        value = polarity_by_arc[arc]
-        arc.set_polarity(value)
-
-    graph.freeze(WithArcPolarity)
-
-    return graph
-
-
-def layer(graph):
-    return layer_simplex(graph)
-
-
-def layer_neatly(graph):
-    ensure(graph.readonly(WithNodeRank), "without node ranks", graph)
-    ensure(not graph.readable(WithLayers), "already with layers", graph)
-
-    graph.upgrade(WithLayers)
-
-    max_nodes_per_layer = int(len(graph.nodes)**0.5)+1
-    nodes = graph.nodes_by_rank[:]
-    while nodes:
-        candidates = []
-        for node in nodes:
-            for neighbor in node.neighbors:
-                if neighbor in candidates:
-                    break
-            else:
-                candidates.append(node)
-                if len(candidates) > max_nodes_per_layer:
-                    break
-        layer = graph.add_layer()
-        for node in candidates:
-            layer.add_node_bead(node)
-            nodes.remove(node)
-
-    for arc in graph.arcs:
-        head = min(arc.origin.layer.idx, arc.target.layer.idx) + 1
-        tail = max(arc.origin.layer.idx, arc.target.layer.idx)
-        for idx in range(head, tail):
-            graph.layers[idx].add_arc_bead(arc)
-
-    graph.freeze(WithLayers)
-
-    return graph
-
-
-def layer_respecting_rank(graph):
-    ensure(graph.readonly(WithNodeRank), "without node ranks", graph)
-    ensure(not graph.readable(WithLayers), "already with layers", graph)
-
-    graph.upgrade(WithLayers)
-
-    max_nodes_per_layer = int(len(graph.nodes)**0.5)+1
-    nodes = graph.nodes_by_rank[:]
-    while nodes:
-        candidates = []
-        for node in nodes:
-            for neighbor in node.neighbors:
-                if neighbor.rank.value < node.rank.value and neighbor.layer is None:
-                    break
-            else:
-                candidates.append(node)
-                if len(candidates) > max_nodes_per_layer:
-                    break
-        layer = graph.add_layer()
-        for node in candidates:
-            layer.add_node_bead(node)
-            nodes.remove(node)
-
-    for arc in graph.arcs:
-        head = min(arc.origin.layer.idx, arc.target.layer.idx) + 1
-        tail = max(arc.origin.layer.idx, arc.target.layer.idx)
-        for idx in range(head, tail):
-            graph.layers[idx].add_arc_bead(arc)
-
-    graph.freeze(WithLayers)
-
-    return graph
-
-
-def layer_simplex(graph):
-    ensure(graph.readonly(WithNodeRank), "without node ranks", graph)
-    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
-    ensure(not graph.readable(WithLayers), "already with layers", graph)
-
-    graph.upgrade(WithLayers)
-
-    A = dict(((i,j),0) for i in range(len(graph.nodes)) for j in range(len(graph.arcs)))
-    B = [0]*len(graph.nodes)
-    C = [0]*len(graph.arcs)
-
-    for arc in graph.arcs:
-        if arc.origin is arc.target:
-            continue
-        w = arc.weight.value
-        i1 = arc.origin.idx
-        i2 = arc.target.idx
-        if arc.origin.rank.value < arc.target.rank.value:
-            i1, i2 = i2, i1
-        j = arc.idx
-        A[i1,j] = +1
-        A[i2,j] = -1
-        C[j] = 1
-        B[i1] += w
-        B[i2] -= w
-
-    positions = simplex_fast(A, B, C)
-
-    idx_by_position = {}
-    for idx in range(len(positions)):
-        position = int(positions[idx])
-        idx_by_position.setdefault(position, [])
-        idx_by_position[position].append(idx)
-    for position in sorted(idx_by_position):
-        layer = graph.add_layer()
-        for idx in idx_by_position[position]:
-            node = graph.nodes[idx]
-            layer.add_node_bead(node)
-
-    for arc in graph.arcs:
-        head = min(arc.origin.layer.idx, arc.target.layer.idx) + 1
-        tail = max(arc.origin.layer.idx, arc.target.layer.idx)
-        for idx in range(head, tail):
-            graph.layers[idx].add_arc_bead(arc)
-
-    graph.freeze(WithLayers)
-
-    return graph
-
-
-def order(graph):
-    return order_hybrid(graph)
-
-
-def order_by_default(graph):
-    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
-
-    graph.upgrade(WithBeadOrder)
-
-    for layer in graph.layers:
-        for order, bead in enumerate(layer.beads):
-            bead.set_order(order)
-
-    graph.freeze(WithBeadOrder)
-
-    return graph
-
-
-def order_optimally(graph):
-    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
-
-    graph.upgrade(WithBeadOrder)
-
-    layer = graph.layers[0]
-    indexes = range(len(layer.beads))
-    shuffles = list(itertools.permutations(indexes))
-    crosses = {}
-    solutions = {}
-    for shuffle in shuffles:
-        crosses[shuffle] = 0.0
-        solutions[shuffle] = [shuffle]
-
-    for next_layer in graph.layers[1:]:
-        next_indexes = range(len(next_layer.beads))
-        next_shuffles = list(itertools.permutations(next_indexes))
-        next_crosses = {}
-        next_solutions = {}
-
-        weights = {}
-        for idx, bead in enumerate(layer.beads):
-            for next_idx, next_bead in enumerate(next_layer.beads):
-                arcs = []
-                if bead.is_node:
-                    for arc in bead.node.incoming+bead.node.outgoing:
-                        if next_bead.is_node and next_bead.node in [arc.origin, arc.target]:
-                            arcs.append(arc)
-                        elif next_bead.is_arc and next_bead.arc is arc:
-                            arcs.append(arc)
-                else:
-                    if next_bead.is_node and bead.arc in next_bead.node.incoming+next_bead.node.outgoing:
-                        arcs.append(bead.arc)
-                    elif next_bead.is_arc and bead.arc is next_bead.arc:
-                        arcs.append(bead.arc)
-                weight = 0.0
-                for arc in arcs:
-                    weight += arc.weight.value
-                weights[idx, next_idx] = weight
-
-        for next_shuffle in next_shuffles:
-
-            crossings = {}
-            for left_idx in indexes:
-                for right_idx in indexes:
-                    crossing = 0.0
-                    if left_idx != right_idx:
-                        for next_left_idx in next_indexes:
-                            left_weight = weights[left_idx, next_left_idx]
-                            for next_right_idx in next_indexes:
-                                right_weight = weights[right_idx, next_right_idx]
-                                if next_shuffle[next_left_idx] > next_shuffle[next_right_idx]:
-                                    crossing += left_weight*right_weight
-                    crossings[left_idx, right_idx] = crossing
-
-            min_cross = None
-            min_solution = None
-
-            for shuffle in shuffles:
-                cross = crosses[shuffle]
-                for left_idx in indexes:
-                    for right_idx in indexes:
-                        if shuffle[left_idx] < shuffle[right_idx]:
-                            cross += crossings[left_idx, right_idx]
-                if min_cross is None or cross < min_cross:
-                    min_cross = cross
-                    min_solution = solutions[shuffle]
-
-            next_crosses[next_shuffle] = min_cross
-            next_solutions[next_shuffle] = min_solution+[next_shuffle]
-
-        layer = next_layer
-        indexes = next_indexes
-        shuffles = next_shuffles
-        crosses = next_crosses
-        solutions = next_solutions
-
-    min_cross = None
-    min_solution = None
-    for shuffle in shuffles:
-        cross = crosses[shuffle]
-        if min_cross is None or cross < min_cross:
-            min_cross = cross
-            min_solution = solutions[shuffle]
-
-    for layer, shuffle in zip(graph.layers, min_solution):
-        for bead, value in zip(layer.beads, shuffle):
-            bead.set_order(value)
-
-    graph.freeze(WithBeadOrder)
-
-    return graph
-
-
-def order_dfs(graph):
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
-
-    graph.upgrade(WithBeadOrder)
-
-    next_order_by_layer = {}
-    for layer in graph.layers:
-        next_order_by_layer[layer] = 0
-
-    stack = []
-    stack.extend(reversed(graph.beads))
-    while stack:
-        bead = stack.pop()
-        if bead.order is not None:
-            continue
-        value = next_order_by_layer[bead.layer]
-        bead.set_order(value)
-        next_order_by_layer[bead.layer] = value+1
-        stack.extend(bead.neighbors)
-
-    graph.freeze(WithBeadOrder)
-
-    return graph
-
-
-def order_transpose(graph):
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
-
-    graph.upgrade(WithBeadOrder)
-
-    weights = {}
-    layer = graph.layers[0]
-    for next_layer in graph.layers[1:]:
-        for bead in layer.beads:
-            for next_bead in next_layer.beads:
-                arcs = []
-                if bead.is_node:
-                    for arc in bead.node.incoming+bead.node.outgoing:
-                        if next_bead.is_node and next_bead.node in [arc.origin, arc.target]:
-                            arcs.append(arc)
-                        elif next_bead.is_arc and next_bead.arc is arc:
-                            arcs.append(arc)
-                else:
-                    if next_bead.is_node and bead.arc in next_bead.node.incoming+next_bead.node.outgoing:
-                        arcs.append(bead.arc)
-                    elif next_bead.is_arc and bead.arc is next_bead.arc:
-                        arcs.append(bead.arc)
-                weight = 0.0
-                for arc in arcs:
-                    weight += arc.weight.value
-                weights[bead, next_bead] = weight
-        layer = next_layer
-
-    order_by_bead = {}
-    next_order_by_layer = {}
-    for layer in graph.layers:
-        next_order_by_layer[layer] = 0
-    stack = []
-    stack.extend(reversed(graph.beads))
-    while stack:
-        bead = stack.pop()
-        if bead in order_by_bead:
-            continue
-        value = next_order_by_layer[bead.layer]
-        order_by_bead[bead] = value
-        next_order_by_layer[bead.layer] = value+1
-        stack.extend(bead.neighbors)
-
-    improved = True
-    while improved:
-        improved = False
-        for prev_layer, layer, next_layer in zip([None]+graph.layers[:-1], graph.layers, graph.layers[1:]+[None]):
-            prev_beads = None
-            if prev_layer is not None:
-                prev_beads = sorted(prev_layer.beads, key=(lambda bead: order_by_bead[bead]))
-            beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
-            next_beads = None
-            if next_layer is not None:
-                next_beads = sorted(next_layer.beads, key=(lambda bead: order_by_bead[bead]))
-            for idx in range(len(beads)-1):
-                left = beads[idx]
-                right = beads[idx+1]
-                direct = 0.0
-                reverse = 0.0
-                if prev_beads is not None:
-                    for left_neighbor in prev_beads:
-                        left_weight = weights[left_neighbor, left]
-                        for right_neighbor in prev_beads:
-                            right_weight = weights[right_neighbor, right]
-                            if order_by_bead[left_neighbor] > order_by_bead[right_neighbor]:
-                                direct += left_weight*right_weight
-                            if order_by_bead[left_neighbor] < order_by_bead[right_neighbor]:
-                                reverse += left_weight*right_weight
-                if next_beads is not None:
-                    for left_neighbor in next_beads:
-                        left_weight = weights[left, left_neighbor]
-                        for right_neighbor in next_beads:
-                            right_weight = weights[right, right_neighbor]
-                            if order_by_bead[left_neighbor] > order_by_bead[right_neighbor]:
-                                direct += left_weight*right_weight
-                            if order_by_bead[left_neighbor] < order_by_bead[right_neighbor]:
-                                reverse += left_weight*right_weight
-                if reverse < direct or (reverse == direct and left.idx < right.idx):
-                    beads[idx] = right
-                    beads[idx+1] = left
-                    order_by_bead[left] = idx+1
-                    order_by_bead[right] = idx
-                    improved = True
-
-    for bead in graph.beads:
-        value = order_by_bead[bead]
-        bead.set_order(value)
-
-    graph.freeze(WithBeadOrder)
-
-    return graph
-
-
-def order_median(graph):
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
-
-    graph.upgrade(WithBeadOrder)
-
-    weights = {}
-    layer = graph.layers[0]
-    for next_layer in graph.layers[1:]:
-        for bead in layer.beads:
-            for next_bead in next_layer.beads:
-                arcs = []
-                if bead.is_node:
-                    for arc in bead.node.incoming+bead.node.outgoing:
-                        if next_bead.is_node and next_bead.node in [arc.origin, arc.target]:
-                            arcs.append(arc)
-                        elif next_bead.is_arc and next_bead.arc is arc:
-                            arcs.append(arc)
-                else:
-                    if next_bead.is_node and bead.arc in next_bead.node.incoming+next_bead.node.outgoing:
-                        arcs.append(bead.arc)
-                    elif next_bead.is_arc and bead.arc is next_bead.arc:
-                        arcs.append(bead.arc)
-                weight = 0.0
-                for arc in arcs:
-                    weight += arc.weight.value
-                weights[bead, next_bead] = weight
-                weights[next_bead, bead] = weight
-        layer = next_layer
-
-    order_by_bead = {}
-    next_order_by_layer = {}
-    for layer in graph.layers:
-        next_order_by_layer[layer] = 0
-    stack = []
-    stack.extend(reversed(graph.beads))
-    while stack:
-        bead = stack.pop()
-        if bead in order_by_bead:
-            continue
-        value = next_order_by_layer[bead.layer]
-        order_by_bead[bead] = value
-        next_order_by_layer[bead.layer] = value+1
-        stack.extend(bead.neighbors)
-
-    next_layouts = zip(graph.layers[1:], graph.layers[:-1])
-    current_layouts = zip(graph.layers[:-1][::-1], graph.layers[1:][::-1])
-    for count in range(len(graph.beads)):
-        current_layouts, next_layouts = next_layouts, current_layouts
-
-        for layer, opposite_layer in current_layouts:
-            beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
-            medians = {}
-            for bead in beads:
-                neighbors = sorted(order_by_bead[neighbor]
-                                  for neighbor in opposite_layer.beads if weights[bead,neighbor] > 0.0)
-                if not neighbors:
-                    value = order_by_bead[bead]
-                else:
-                    length = len(neighbors)
-                    if length % 2 == 1:
-                        value = neighbors[length/2]
-                    elif length == 2:
-                        value = 0.5*sum(neighbors)
-                    else:
-                        l = neighbors[length/2-1] - neighbors[0]
-                        r = neighbors[-1] - neighbors[length/2]
-                        value = 1.0*(l*neighbors[length/2-1]+r*neighbors[length/2])/(l+r)
-                medians[bead] = value
-            beads = sorted(beads, key=(lambda bead: medians[bead]))
-            for idx, bead in enumerate(beads):
-                order_by_bead[bead] = idx
-
-        improved = True
-        while improved:
-            improved = False
-            for prev_layer, layer, next_layer in zip([None]+graph.layers[:-1],
-                                                     graph.layers,
-                                                     graph.layers[1:]+[None])[::-1]:
-                beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
-                for idx in range(len(beads)-1):
-                    left = beads[idx]
-                    right = beads[idx+1]
-                    direct = 0.0
-                    reverse = 0.0
-                    for opposite_layer in [prev_layer, next_layer]:
-                        if opposite_layer is None:
-                            continue
-                        for left_neighbor in opposite_layer.beads:
-                            left_weight = weights[left_neighbor, left]
-                            for right_neighbor in opposite_layer.beads:
-                                right_weight = weights[right_neighbor, right]
-                                if order_by_bead[left_neighbor] > order_by_bead[right_neighbor]:
-                                    direct += left_weight*right_weight
-                                if order_by_bead[left_neighbor] < order_by_bead[right_neighbor]:
-                                    reverse += left_weight*right_weight
-                    if reverse < direct:
-                        beads[idx] = right
-                        beads[idx+1] = left
-                        order_by_bead[left] = idx+1
-                        order_by_bead[right] = idx
-                        improved = True
-
-    for bead in graph.beads:
-        value = order_by_bead[bead]
-        bead.set_order(value)
-
-    graph.freeze(WithBeadOrder)
-
-    return graph
-
-
-def order_hybrid(graph):
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
-
-    graph.upgrade(WithBeadOrder)
-
-    weights = {}
-    layer = graph.layers[0]
-    for next_layer in graph.layers[1:]:
-        for bead in layer.beads:
-            for next_bead in next_layer.beads:
-                arcs = []
-                if bead.is_node:
-                    for arc in bead.node.incoming+bead.node.outgoing:
-                        if next_bead.is_node and next_bead.node in [arc.origin, arc.target]:
-                            arcs.append(arc)
-                        elif next_bead.is_arc and next_bead.arc is arc:
-                            arcs.append(arc)
-                else:
-                    if next_bead.is_node and bead.arc in next_bead.node.incoming+next_bead.node.outgoing:
-                        arcs.append(bead.arc)
-                    elif next_bead.is_arc and bead.arc is next_bead.arc:
-                        arcs.append(bead.arc)
-                weight = 0.0
-                for arc in arcs:
-                    weight += arc.weight.value
-                weights[bead, next_bead] = weight
-                weights[next_bead, bead] = weight
-        layer = next_layer
-
-    order_by_bead = {}
-    next_order_by_layer = {}
-    for layer in graph.layers:
-        next_order_by_layer[layer] = 0
-    stack = []
-    stack.extend(reversed(graph.beads))
-    while stack:
-        bead = stack.pop()
-        if bead in order_by_bead:
-            continue
-        value = next_order_by_layer[bead.layer]
-        order_by_bead[bead] = value
-        next_order_by_layer[bead.layer] = value+1
-        stack.extend(bead.neighbors)
-
-    def crossings():
-        total = 0.0
-        layer = graph.layers[0]
-        for next_layer in graph.layers[1:]:
-            for lbead in layer.beads:
-                lorder = order_by_bead[lbead]
-                for rbead in layer.beads:
-                    rorder = order_by_bead[rbead]
-                    if rorder <= lorder:
-                        continue
-                    for next_lbead in next_layer.beads:
-                        if not weights[lbead, next_lbead]:
-                            continue
-                        next_lorder = order_by_bead[next_lbead]
-                        for next_rbead in next_layer.beads:
-                            if not weights[rbead, next_rbead]:
-                                continue
-                            next_rorder = order_by_bead[next_rbead]
-                            if next_rorder >= next_lorder:
-                                continue
-                            total += weights[lbead, next_lbead]*weights[rbead, next_rbead]
-            layer = next_layer
-        return total
-
-    best_crossings = crossings()
-    best_order_by_bead = order_by_bead.copy()
-
-    next_layouts = zip(graph.layers[1:], graph.layers[:-1])
-    current_layouts = zip(graph.layers[:-1][::-1], graph.layers[1:][::-1])
-    for count in range(len(graph.layers)):
-        current_layouts, next_layouts = next_layouts, current_layouts
-
-        for layer, opposite_layer in current_layouts:
-            beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
-            medians = {}
-            for bead in beads:
-                neighbors = sorted(order_by_bead[neighbor]
-                                  for neighbor in opposite_layer.beads if weights[bead,neighbor] > 0.0)
-                if not neighbors:
-                    value = order_by_bead[bead]
-                else:
-                    length = len(neighbors)
-                    if length % 2 == 1:
-                        value = neighbors[length/2]
-                    elif length == 2:
-                        value = 0.5*sum(neighbors)
-                    else:
-                        l = neighbors[length/2-1] - neighbors[0]
-                        r = neighbors[-1] - neighbors[length/2]
-                        value = 1.0*(l*neighbors[length/2-1]+r*neighbors[length/2])/(l+r)
-                medians[bead] = value
-            beads = sorted(beads, key=(lambda bead: medians[bead]))
-            for idx, bead in enumerate(beads):
-                order_by_bead[bead] = idx
-
-        improved = True
-        while improved:
-            improved = False
-            for prev_layer, layer, next_layer in zip([None]+graph.layers[:-1],
-                                                     graph.layers,
-                                                     graph.layers[1:]+[None])[::-1]:
-                beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
-                for delta in [+1, -1]:
-                    if delta > 0:
-                        idx = 0
-                    else:
-                        idx = len(beads)-2
-                    while 0 <= idx < len(beads)-1:
-                        left = beads[idx]
-                        right = beads[idx+1]
-                        direct = 0.0
-                        reverse = 0.0
-                        for opposite_layer in [prev_layer, next_layer]:
-                            if opposite_layer is None:
-                                continue
-                            for left_neighbor in opposite_layer.beads:
-                                left_weight = weights[left_neighbor, left]
-                                if not left_weight:
-                                    continue
-                                for right_neighbor in opposite_layer.beads:
-                                    right_weight = weights[right_neighbor, right]
-                                    if not right_weight:
-                                        continue
-                                    if order_by_bead[left_neighbor] > order_by_bead[right_neighbor]:
-                                        direct += left_weight*right_weight
-                                    if order_by_bead[left_neighbor] < order_by_bead[right_neighbor]:
-                                        reverse += left_weight*right_weight
-                        if reverse < direct:
-                            beads[idx] = right
-                            beads[idx+1] = left
-                            order_by_bead[left] = idx+1
-                            order_by_bead[right] = idx
-                            improved = True
-                        idx += delta
-
-        curr_crossings = crossings()
-        if curr_crossings < best_crossings:
-            best_crossings = curr_crossings
-            best_order_by_bead = order_by_bead.copy()
-            #print "NEW LAYOUT:", best_crossings
-
-    for bead in graph.beads:
-        value = best_order_by_bead[bead]
-        bead.set_order(value)
-
-    graph.freeze(WithBeadOrder)
-
-    return graph
-
-
-def place(graph):
-    return place_simplex(graph)
-
-
-def place_uniform(graph):
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(graph.readonly(WithBeadOrder), "without bead orders", graph)
-    ensure(graph.readonly(WithNodeDimensions), "without node dimensions", graph)
-    ensure(graph.readonly(WithGraphMargins), "without graph margins", graph)
-    ensure(not graph.readable(WithGraphSize), "already with graph size", graph)
-    ensure(not graph.readable(WithNodePosition), "already with node positions", graph)
-    ensure(not graph.readable(WithArcVertices), "already with arc vertices", graph)
-
-    graph.upgrade(WithGraphSize)
-    graph.upgrade(WithNodePosition)
-    graph.upgrade(WithArcVertices)
-
-    width = graph.margins.horizontal
-    height = graph.margins.vertical
-    for layer in graph.layers:
-        layer_width = (len(layer.beads)+1)*graph.margins.horizontal
-        layer_height = 0
-        for bead in layer.beads:
-            if bead.is_node:
-                layer_width += bead.node.dimensions.width
-        for bead in layer.beads:
-            if bead.is_node:
-                layer_height = max(layer_height, bead.node.dimensions.height)
-        width = max(width, layer_width)
-        height += layer_height+graph.margins.vertical
-    graph.set_size(width, height)
-
-    top = graph.margins.vertical
-    for layer in graph.layers:
-        left = graph.margins.horizontal
-        height = 0
-        density = 0
-        for bead in layer.beads:
-            if bead.is_node:
-                height = max(height, bead.node.dimensions.height)
-                density += bead.node.dimensions.width
-        spread = 0
-        if len(layer.beads) > 1:
-            spread = (graph.size.width-2*graph.margins.horizontal-density) / (len(layer.beads)-1)
-        else:
-            left += (graph.size.width-2*graph.margins.horizontal-density) / 2
-        for bead in layer.beads_by_order:
-            if bead.is_node:
-                w = bead.node.dimensions.width
-                h = bead.node.dimensions.height
-                x = left
-                y = top + (height-h)/2
-                cx = x+w/2
-                cy = y+h/2
-                bead.node.set_position(x, y, w, h)
-                for arc in bead.node.incoming+bead.node.outgoing:
-                    arc.add_vertex(cx, cy)
-                left += w+spread
-            if bead.is_arc:
-                x = left
-                y = top + height/2
-                bead.arc.add_vertex(x, y)
-                left += spread
-        top += height+graph.margins.vertical
-
-    graph.freeze(WithGraphSize)
-    graph.freeze(WithNodePosition)
-    graph.freeze(WithArcVertices)
-
-    return graph
-
-
-def debug_simplex(A, B, C):
-    M = len(B)
-    N = len(C)
-    print
-    print "A:"
-    for i in range(M):
-        for j in range(N):
-            print A[i,j],
-        print
-    print "B:"
-    for i in range(M):
-        print B[i],
-    print
-    print "C:"
-    for j in range(N):
-        print C[j],
-    print
-
-def simplex(A, B, C):
-    M = len(B)
-    N = len(C)
-    A = dict((key, float(A[key])) for key in A)
-    B = [float(b) for b in B]
-    C = [float(-c) for c in C]
-    X = [i for i in range(M)]
-    Y = [None for j in range(N)]
-    #debug_simplex(A, B, C)
-
-    eps = 1e-5
-    while not (all(c >= -eps for c in C) and all(b >= -eps for b in B)):
-        i0 = None
-        j0 = None
-        if all(b >= -eps for b in B):
-            for j in range(N):
-                if C[j] < -eps:
-                    j0 = j
-                    break
-            for i in range(M):
-                if A[i,j0] > eps:
-                    if i0 is None or B[i]/A[i,j0] < B[i0]/A[i0,j0]:
-                        i0 = i
-        else:
-            for i in range(M):
-                if B[i] < -eps:
-                    i0 = i
-                    break
-            for j in range(N):
-                if A[i0,j] < -eps:
-                    j0 = j
-                    break
-            for i in range(M):
-                if A[i,j0] > eps and B[i] > -eps:
-                    if B[i]/A[i,j0] < B[i0]/A[i0,j0]:
-                        i0 = i
-        assert i0 is not None and j0 is not None
-        AA = {}
-        BB = [None]*M
-        CC = [None]*N
-        for i in range(M):
-            for j in range(N):
-                if i == i0 and j == j0:
-                    AA[i,j] = 1/A[i0,j0]
-                elif i == i0:
-                    AA[i,j] = A[i,j]/A[i0,j0]
-                elif j == j0:
-                    AA[i,j] = -A[i,j]/A[i0,j0]
-                else:
-                    AA[i,j] = A[i,j]-A[i0,j]*A[i,j0]/A[i0,j0]
-        for i in range(M):
-            if i == i0:
-                BB[i] = B[i]/A[i0,j0]
-            else:
-                BB[i] = B[i]-B[i0]*A[i,j0]/A[i0,j0]
-        for j in range(N):
-            if j == j0:
-                CC[j] = -C[j]/A[i0,j0]
-            else:
-                CC[j] = C[j]-A[i0,j]*C[j0]/A[i0,j0]
-        A, B, C = AA, BB, CC
-        X[i0], Y[j0] = Y[j0], X[i0]
-        #print
-        #print "pivot:", (i0, j0)
-        #debug_simplex(A, B, C)
-
-    #debug_simplex(A, B, C)
-    solution = [0]*M
-    for y, c in zip(Y, C):
-        if y is not None:
-            solution[y] = int(c)
-    #print "solution:", solution
-    return solution
-
-def simplex_fast(A, B, C):
-    M = len(B)
-    N = len(C)
-    A = [[float(A[i,j]) for j in range(N)] for i in range(M)]
-    B = [float(b) for b in B]
-    C = [float(-c) for c in C]
-    X = [i for i in range(M)]
-    Y = [None for j in range(N)]
-
-    eps = 1e-5
-    while not (all(c >= -eps for c in C) and all(b >= -eps for b in B)):
-        i0 = None
-        j0 = None
-        p0 = None
-        if all(b >= -eps for b in B):
-            for j in range(N):
-                if C[j] < -eps:
-                    j0 = j
-                    break
-            for i in range(M):
-                if A[i][j0] > eps:
-                    p = B[i]/A[i][j0]
-                    if p0 is None or p < p0:
-                        i0 = i
-                        p0 = p
-        else:
-            for i in range(M):
-                if B[i] < -eps:
-                    i0 = i
-                    break
-            assert i0 is not None
-            for j in range(N):
-                if A[i0][j] < -eps:
-                    j0 = j
-                    break
-            assert j0 is not None
-            p0 = B[i0]/A[i0][j0]
-            for i in range(M):
-                if A[i][j0] > eps and B[i] > -eps:
-                    p = B[i]/A[i][j0]
-                    if p < p0:
-                        i0 = i
-                        p0 = p
-        assert i0 is not None and j0 is not None
-        AA = [None]*M
-        BB = [None]*M
-        CC = [None]*N
-        irange = range(i0)+range(i0+1, M)
-        jrange = range(j0)+range(j0+1, N)
-        s = A[i0][j0]
-
-        p = B[i0]/s
-        for i in irange:
-            BB[i] = B[i]-A[i][j0]*p
-        BB[i0] = p
-        q = C[j0]/s
-        for j in jrange:
-            CC[j] = C[j]-A[i0][j]*q
-        CC[j0] = -q
-        for i in irange:
-            r = A[i][j0]/s
-            AA[i] = A[i]
-            if abs(r) > eps:
-                for j in jrange:
-                    AA[i][j] -= A[i0][j]*r
-            AA[i][j0] = -r
-        AA[i0] = A[i0]
-        for j in jrange:
-            AA[i0][j] /= s
-        AA[i0][j0] = 1/s
-        A, B, C = AA, BB, CC
-        X[i0], Y[j0] = Y[j0], X[i0]
-
-    solution = [0]*M
-    for y, c in zip(Y, C):
-        if y is not None:
-            solution[y] = int(c)
-    #print "solution:", solution
-    return solution
-
-
-def place_simplex(graph):
-    ensure(graph.readonly(WithLayers), "without layers", graph)
-    ensure(graph.readonly(WithBeadOrder), "without bead orders", graph)
-    ensure(graph.readonly(WithNodeDimensions), "without node dimensions", graph)
-    ensure(graph.readonly(WithGraphMargins), "without graph margins", graph)
-    ensure(not graph.readable(WithGraphSize), "already with graph size", graph)
-    ensure(not graph.readable(WithNodePosition), "already with node positions", graph)
-    ensure(not graph.readable(WithArcVertices), "already with arc vertices", graph)
-
-    graph.upgrade(WithGraphSize)
-    graph.upgrade(WithNodePosition)
-    graph.upgrade(WithArcVertices)
-
-    A = {}
-    B = []
-    C = []
-    delta = graph.margins.horizontal
-    for layer in graph.layers:
-        beads = layer.beads_by_order
-        bead = beads[0]
-        for next_bead in beads[1:]:
-            c = delta
-            if bead.is_node:
-                c += bead.node.dimensions.width/2
-            if next_bead.is_node:
-                c += next_bead.node.dimensions.width/2
-            i1 = bead.idx
-            i2 = next_bead.idx
-            j = len(C)
-            A[i1,j] = -1
-            A[i2,j] = +1
-            C.append(c)
-            bead = next_bead
-    B += [0]*len(graph.beads)
-    layer = graph.layers[0]
-    for next_layer in graph.layers[1:]:
-        for bead in layer.beads:
-            for next_bead in next_layer.beads:
-                arcs = []
-                if bead.is_node:
-                    for arc in bead.node.incoming+bead.node.outgoing:
-                        if next_bead.is_node and next_bead.node in [arc.origin, arc.target]:
-                            arcs.append(arc)
-                        elif next_bead.is_arc and next_bead.arc is arc:
-                            arcs.append(arc)
-                else:
-                    if next_bead.is_node and bead.arc in next_bead.node.incoming+next_bead.node.outgoing:
-                        arcs.append(bead.arc)
-                    elif next_bead.is_arc and bead.arc is next_bead.arc:
-                        arcs.append(bead.arc)
-                b = 0.0
-                for arc in arcs:
-                    b += arc.weight.value
-                if bead.is_arc and next_bead.is_arc:
-                    b *= 8
-                elif bead.is_arc or next_bead.is_arc:
-                    b *= 4
-                if b:
-                    i1 = bead.idx
-                    i2 = next_bead.idx
-                    i3 = len(B)
-                    j1 = len(C)
-                    j2 = len(C)+1
-                    A[i1,j1] = -1
-                    A[i2,j1] = +1
-                    A[i3,j1] = +1
-                    A[i1,j2] = +1
-                    A[i2,j2] = -1
-                    A[i3,j2] = +1
-                    B.append(b)
-                    C.append(0)
-                    C.append(0)
-        layer = next_layer
-    for i in range(len(B)):
-        for j in range(len(C)):
-            if (i,j) not in A:
-                A[i,j] = 0
-
-    centers = simplex_fast(A, B, C)
-    left = None
-    right = None
-    for bead in graph.beads:
-        l = r = centers[bead.idx]
-        if bead.is_node:
-            l -= bead.node.dimensions.width/2
-            r += bead.node.dimensions.width/2
-        if left is None or l < left:
-            left = l
-        if right is None or r > right:
-            right = r
-    width = graph.margins.horizontal*2 + (right-left)
-    height = graph.margins.vertical
-    for layer in graph.layers:
-        layer_height = 0
-        for bead in layer.beads:
-            if bead.is_node:
-                layer_height = max(layer_height, bead.node.dimensions.height)
-        height += layer_height+graph.margins.vertical
-    graph.set_size(width, height)
-    shift = graph.margins.horizontal-left
-
-    top = graph.margins.vertical
-    for layer in graph.layers:
-        height = 0
-        for bead in layer.beads:
-            if bead.is_node:
-                height = max(height, bead.node.dimensions.height)
-        for bead in layer.beads_by_order:
-            if bead.is_node:
-                w = bead.node.dimensions.width
-                h = bead.node.dimensions.height
-                x = shift+centers[bead.idx]-w/2
-                y = top + (height-h)/2
-                cx = x+w/2
-                cy = y+h/2
-                bead.node.set_position(x, y, w, h)
-                for arc in bead.node.incoming+bead.node.outgoing:
-                    arc.add_vertex(cx, cy)
-            if bead.is_arc:
-                x = shift+centers[bead.idx]
-                y = top + height/2
-                bead.arc.add_vertex(x, y)
-        top += height+graph.margins.vertical
-
-    graph.freeze(WithGraphSize)
-    graph.freeze(WithNodePosition)
-    graph.freeze(WithArcVertices)
-
-    return graph
-
-
-def place_polarized(graph):
-    ensure(graph.readonly(WithNodeRank), "without node ranks", graph)
-    ensure(graph.readonly(WithArcPolarity), "without arc polarity", graph)
-    ensure(graph.readonly(WithNodeDimensions), "without node dimensions", graph)
-    ensure(graph.readonly(WithGraphMargins), "without graph margins", graph)
-    ensure(not graph.readable(WithGraphSize), "already with graph size", graph)
-    ensure(not graph.readable(WithNodePosition), "already with node positions", graph)
-    ensure(not graph.readable(WithArcVertices), "already with arc vertices", graph)
-
-    graph.upgrade(WithGraphSize)
-    graph.upgrade(WithNodePosition)
-    graph.upgrade(WithArcVertices)
-
-    width = 0
-    height = 0
-    for node in graph.nodes:
-        width = max(width, node.dimensions.width)
-        height += node.dimensions.height+graph.margins.vertical
-    width *= 3
-    width += 2*graph.margins.horizontal*len(graph.nodes)
-    height += graph.margins.vertical
-    graph.set_size(width, height)
-
-    top = graph.margins.vertical
-    center = width/2
-    for node in graph.nodes_by_rank:
-        x = center-node.dimensions.width/2
-        y = top
-        w = node.dimensions.width
-        h = node.dimensions.height
-        node.set_position(x, y, w, h)
-        top += node.dimensions.height+graph.margins.vertical
-
-    left = graph.margins.horizontal*len(graph.nodes)
-    right = width-graph.margins.horizontal*len(graph.nodes)
-    for arc in graph.arcs:
-        start = arc.origin.position.y + arc.origin.position.h/2
-        end = arc.target.position.y + arc.target.position.h/2
-        length = abs(arc.origin.rank.value-arc.target.rank.value)
-        arc.add_vertex(center, start)
-        if arc.polarity.value < 0:
-            arc.add_vertex(left-length*graph.margins.horizontal, (start+end)/2)
-        elif arc.polarity.value > 0:
-            arc.add_vertex(right+length*graph.margins.horizontal, (start+end)/2)
-        arc.add_vertex(center, end)
-
-    graph.freeze(WithGraphSize)
-    graph.freeze(WithNodePosition)
-    graph.freeze(WithArcVertices)
-
-    return graph
-
-

database.py

-
-
-from model import build, WithNodeLabel, WithArcWeight
-from htsql import HTSQL
-from htsql.introspect import introspect
-
-
-def build_schema(db):
-    with HTSQL(db):
-        catalog = introspect()
-
-    graph = build(WithNodeLabel, WithArcWeight)
-
-    node_by_table = {}
-    for schema in catalog.schemas:
-        for table in schema.tables:
-            node = graph.add_node()
-            node.set_label(table.name)
-            node_by_table[table] = node
-
-    for schema in catalog.schemas:
-        for table in schema.tables:
-            origin = node_by_table[table]
-            for foreign_key in table.foreign_keys:
-                target_schema = catalog.schemas[foreign_key.target_schema_name]
-                target_table = target_schema.tables[foreign_key.target_name]
-                target = node_by_table[target_table]
-                is_parental = (target_table.primary_key is not None and
-                               all(column_name in target_table.primary_key.origin_column_names
-                                   for column_name in foreign_key.origin_column_names))
-                if is_parental:
-                    weight = 1.0
-                else:
-                    weight = 0.5
-                arc = graph.add_arc(origin, target)
-                arc.set_weight(weight)
-
-    graph.freeze()
-    return graph
-
-

demo/example-loop.py

+
+from grrdrr.model import build, WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight
+from grrdrr.draw import measure, draw
+from grrdrr.algorithm import rank, layer, order, place
+
+
+example = build(WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight)
+
+example.set_style(
+        background_color=(0.5, 0.5, 0.5),
+        node_color=(0.0, 0.0, 0.5),
+        arc_color=(0.5, 0.0, 0.0),
+        text_color=(1.0, 1.0, 1.0),
+        font_size=18.0)
+
+alpha = example.add_node()
+beta = example.add_node()
+gamma = example.add_node()
+
+alpha.set_label("alpha")
+beta.set_label("beta")
+gamma.set_label("gamma")
+
+alpha_beta = example.add_arc(alpha, beta)
+beta_gamma = example.add_arc(beta, gamma)
+gamma_alpha = example.add_arc(gamma, alpha)
+
+alpha_beta.set_label("alpha-beta").set_weight(1.0)
+beta_gamma.set_label("beta-gamma").set_weight(1.0)
+gamma_alpha.set_label("gamma-alpha").set_weight(1.0)
+
+example.freeze()
+measure(example)
+rank(example)
+layer(example)
+order(example)
+place(example)
+
+example = example.clone()
+
+print
+print "(%s, %s)" % (example.size.width, example.size.height)
+for node in example.nodes_by_rank:
+    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
+
+stream = open("example-loop.png", "wb")
+draw(example, stream)
+
+

demo/example-polarity.py

+
+from grrdrr.model import WithGraphStyle
+from grrdrr.database import build_schema
+from grrdrr.draw import measure, draw, draw_smooth
+from grrdrr.algorithm import rank, rank_greedy, layer, order, place, polarize, place_polarized
+import sys
+
+if len(sys.argv) != 2:
+    print "Usage: %s <db>" % sys.argv[0]
+    sys.exit(1)
+db = sys.argv[1]
+
+example = build_schema(db)
+example.upgrade(WithGraphStyle)
+example.freeze()
+
+measure(example)
+rank_greedy(example)
+polarize(example)
+place_polarized(example)
+
+example = example.clone()
+
+print
+print repr(example)
+
+print
+for node in example.nodes:
+    print repr(node)
+
+print
+for arc in example.arcs:
+    print repr(arc), arc.weight.value
+
+print
+for node in example.nodes_by_rank:
+    print node, node.rank.value
+
+print
+for arc in example.arcs:
+    print repr(arc), arc.polarity.value
+
+print
+total = 0.0
+for node1 in example.nodes:
+    for node2 in example.nodes:
+        if node1.rank.value >= node2.rank.value:
+            continue
+        for arc1 in node1.outgoing:
+            if arc1.polarity.value == 0:
+                continue
+            t1 = min(arc1.origin.rank.value, arc1.target.rank.value)
+            b1 = max(arc1.origin.rank.value, arc1.target.rank.value)
+            for arc2 in node2.outgoing:
+                if arc2.polarity.value != arc1.polarity.value:
+                    continue
+                t2 = min(arc2.origin.rank.value, arc2.target.rank.value)
+                b2 = max(arc2.origin.rank.value, arc2.target.rank.value)
+                if t1 < t2 < b1 < b2 or t2 < t1 < b2 < b1:
+                    total += arc1.weight.value+arc2.weight.value
+print "CROSSINGS:", total
+
+stream = open("example-polarity.png", "wb")
+draw_smooth(example, stream)
+
+

demo/example-regress.py

+
+from grrdrr.model import build, WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight
+from grrdrr.draw import measure, draw, draw_smooth
+from grrdrr.algorithm import rank, layer, order, place
+
+
+example = build(WithGraphStyle, WithNodeLabel, WithArcWeight)
+
+example.set_style(
+        arc_width=1.5,
+        border_width=1.5,
+        font_size=16.0)
+
+ad_school = example.add_node()
+ad_department = example.add_node()
+ad_program = example.add_node()
+ad_course = example.add_node()
+
+id_instructor = example.add_node()
+id_confidential = example.add_node()
+id_appointment = example.add_node()
+
+cd_semester = example.add_node()
+cd_class = example.add_node()
+
+ed_student = example.add_node()
+ed_enrollment = example.add_node()
+
+rd_prerequisite = example.add_node()
+rd_classification = example.add_node()
+rd_course_classification = example.add_node()
+rd_program_requirement = example.add_node()
+
+ad_school.set_label("school")
+ad_department.set_label("department")
+ad_program.set_label("program")
+ad_course.set_label("course")
+
+id_instructor.set_label("instructor")
+id_confidential.set_label("confidential")
+id_appointment.set_label("appointment")
+
+cd_semester.set_label("semester")
+cd_class.set_label("class")
+
+ed_student.set_label("student")
+ed_enrollment.set_label("enrollment")
+
+rd_prerequisite.set_label("prerequisite")
+rd_classification.set_label("classification")
+rd_course_classification.set_label("course_classification")
+rd_program_requirement.set_label("program_requirement")
+
+example.add_arc(ad_department, ad_school).set_weight(0.5)
+example.add_arc(ad_program, ad_school).set_weight(1.0)
+example.add_arc(ad_program, ad_program).set_weight(0.5)
+example.add_arc(ad_course, ad_department).set_weight(1.0)
+example.add_arc(id_confidential, id_instructor).set_weight(1.0)
+example.add_arc(id_appointment, ad_department).set_weight(1.0)
+example.add_arc(id_appointment, id_instructor).set_weight(1.0)
+example.add_arc(cd_class, ad_course).set_weight(1.0)
+example.add_arc(cd_class, cd_semester).set_weight(1.0)
+example.add_arc(cd_class, id_instructor).set_weight(0.5)
+example.add_arc(ed_student, ad_program).set_weight(0.5)
+example.add_arc(ed_enrollment, ed_student).set_weight(1.0)
+example.add_arc(ed_enrollment, cd_class).set_weight(1.0)
+example.add_arc(rd_prerequisite, ad_course).set_weight(1.0)
+example.add_arc(rd_prerequisite, ad_course).set_weight(1.0)
+example.add_arc(rd_classification, rd_classification).set_weight(0.5)
+example.add_arc(rd_course_classification, ad_course).set_weight(1.0)
+example.add_arc(rd_course_classification, rd_classification).set_weight(1.0)
+example.add_arc(rd_program_requirement, ad_program).set_weight(1.0)
+example.add_arc(rd_program_requirement, rd_classification).set_weight(1.0)
+
+example.freeze()
+measure(example)
+rank(example)
+layer(example)
+order(example)
+place(example)
+
+example = example.clone()
+
+print
+print repr(example)
+
+print
+for node in example.nodes:
+    print repr(node)
+
+print
+for arc in example.arcs:
+    print repr(arc), arc.weight.value
+
+
+print
+for node in example.nodes_by_rank:
+    print node, node.rank.value
+
+print
+for layer in example.layers:
+    print repr(layer)
+    for bead in layer.beads:
+        print "\t", repr(bead)
+
+print
+for layer in example.layers:
+    print repr(layer)
+    for bead in layer.beads_by_order:
+        print "\t", repr(bead)
+
+print
+print "(%s, %s)" % (example.size.width, example.size.height)
+for node in example.nodes_by_rank:
+    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
+
+stream = open("htsql_regress.png", "wb")
+#draw(example, stream)
+draw_smooth(example, stream)
+
+

demo/example-schema.py

+
+from grrdrr.model import WithGraphStyle
+from grrdrr.draw import measure, draw_smooth
+from grrdrr.algorithm import rank, layer, order, place
+from grrdrr.database import build_schema
+from grrdrr.graphviz import draw_graphviz
+import sys
+import re
+
+if len(sys.argv) != 2:
+    print "Usage: %s <db>" % sys.argv[0]
+    sys.exit(1)
+db = sys.argv[1]
+basename_match = re.search(r'[0-9a-zA-Z_-]+$', db)
+if basename_match is not None:
+    basename = basename_match.group()
+else:
+    basename = db
+
+example = build_schema(db)
+example.upgrade(WithGraphStyle)
+example.set_style(
+        arc_width=1.5,
+        border_width=1.5,
+        font_size=16.0)
+example.freeze()
+
+print "MEASURING..."
+measure(example)
+print "RANKING..."
+rank(example)
+print "LAYERING..."
+layer(example)
+print "ORDERING..."
+order(example)
+print "PLACING..."
+place(example)
+print "DONE"
+
+#print
+#print repr(example)
+
+#print
+#for node in example.nodes:
+#    print repr(node)
+
+#print
+#for arc in example.arcs:
+#    print repr(arc), arc.weight.value
+
+#print
+#for node in example.nodes_by_rank:
+#    print node, node.rank.value
+
+#print
+#for layer in example.layers:
+#    print repr(layer)
+#    for bead in layer.beads:
+#        print "\t", repr(bead)
+
+#print
+#for layer in example.layers:
+#    print repr(layer)
+#    for bead in layer.beads_by_order:
+#        print "\t", repr(bead)
+
+#print
+#print "(%s, %s)" % (example.size.width, example.size.height)
+#for node in example.nodes_by_rank:
+#    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
+
+filename = "%s.graphviz.png" % basename
+stream = open(filename, 'wb')
+draw_graphviz(example, stream)
+stream.close()
+print "GraphViz rendering is written to: %s" % filename
+
+filename = "%s.sugiyama.png" % basename
+stream = open(filename, 'wb')
+draw_smooth(example, stream)
+stream.close()
+print "Sugiyama rendering is written to: %s" % filename
+

demo/example-small.py

+
+from grrdrr.model import build, WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight
+from grrdrr.draw import measure, draw
+from grrdrr.algorithm import rank, layer, order, place
+
+
+example = build(WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight)
+
+example.set_style(
+        background_color=(0.5, 0.5, 0.5),
+        node_color=(0.0, 0.0, 0.5),
+        arc_color=(0.5, 0.0, 0.0),
+        text_color=(1.0, 1.0, 1.0),
+        font_size=18.0)
+
+op_organization = example.add_node()
+op_project = example.add_node()
+op_person = example.add_node()
+op_participation = example.add_node()
+
+op_organization.set_label("op.organization")
+op_project.set_label("op.project")
+op_person.set_label("op.person")
+op_participation.set_label("op.participation")
+
+project_organization_fk = example.add_arc(op_project, op_organization)
+person_organization_fk = example.add_arc(op_person, op_organization)
+participation_project_fk = example.add_arc(op_participation, op_project)
+participation_person_fk = example.add_arc(op_participation, op_person)
+
+project_organization_fk.set_label("organization").set_weight(0.5)
+person_organization_fk.set_label("organization").set_weight(1.0)
+participation_project_fk.set_label("project").set_weight(1.0)
+participation_person_fk.set_label("person").set_weight(1.0)
+
+example.freeze()
+measure(example)
+rank(example)
+layer(example)
+order(example)
+place(example)
+
+example = example.clone()
+
+print
+print "(%s, %s)" % (example.size.width, example.size.height)
+for node in example.nodes_by_rank:
+    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
+
+stream = open("example-small.png", "wb")
+draw(example, stream)
+
+
+
+from grrdrr.model import build, WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight
+from grrdrr.draw import measure, draw, draw_smooth
+from grrdrr.algorithm import rank, layer, order, place
+
+
+example = build(WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight)
+
+example.set_style(
+        arc_width=1.5,
+        border_width=1.5,
+        font_size=16.0)
+
+op_organization = example.add_node()
+op_project = example.add_node()
+op_person = example.add_node()
+op_participation = example.add_node()
+hr_private_info = example.add_node()
+ws_workitem = example.add_node()
+ws_worklist = example.add_node()
+ws_dependency = example.add_node()
+wsx_issue = example.add_node()
+wsx_meeting = example.add_node()
+wsx_meeting_topic = example.add_node()
+wsx_standing_meeting = example.add_node()
+tb_invoice = example.add_node()
+tb_lineitem = example.add_node()
+tb_timeslip = example.add_node()
+
+op_organization.set_label("op.organization")
+op_project.set_label("op.project")
+op_person.set_label("op.person")
+op_participation.set_label("op.participation")
+hr_private_info.set_label("hr.private_info")
+ws_workitem.set_label("ws.workitem")
+ws_worklist.set_label("ws.worklist")
+ws_dependency.set_label("ws.dependency")
+wsx_issue.set_label("wsx.issue")
+wsx_meeting.set_label("wsx.meeting")
+wsx_meeting_topic.set_label("wsx.meeting_topic")
+wsx_standing_meeting.set_label("wsx.standing_meeting")
+tb_invoice.set_label("tb.invoice")
+tb_lineitem.set_label("tb.lineitem")
+tb_timeslip.set_label("tb.timeslip")
+
+organization_division_of_fk = example.add_arc(op_organization, op_organization)
+project_organization_fk = example.add_arc(op_project, op_organization)
+person_organization_fk = example.add_arc(op_person, op_organization)
+participation_project_fk = example.add_arc(op_participation, op_project)
+participation_person_fk = example.add_arc(op_participation, op_person)
+private_info_person_fk = example.add_arc(hr_private_info, op_person)
+workitem_project_fk = example.add_arc(ws_workitem, op_project)
+workitem_worklist_fk = example.add_arc(ws_workitem, ws_worklist)
+worklist_workitem_fk = example.add_arc(ws_worklist, ws_workitem)
+worklist_person_fk = example.add_arc(ws_worklist, op_person)
+dependency_of_workitem_fk = example.add_arc(ws_dependency, ws_workitem)
+dependency_on_workitem_fk = example.add_arc(ws_dependency, ws_workitem)
+issue_workitem_fk = example.add_arc(wsx_issue, ws_workitem)
+issue_person_fk = example.add_arc(wsx_issue, op_person)
+meeting_workitem_fk = example.add_arc(wsx_meeting, ws_workitem)
+meeting_topic_meeting_fk = example.add_arc(wsx_meeting_topic, wsx_meeting)
+standing_meeting_meeting_fk = example.add_arc(wsx_standing_meeting, wsx_meeting)
+invoice_organization_fk = example.add_arc(tb_invoice, op_organization)
+lineitem_invoice_fk = example.add_arc(tb_lineitem, tb_invoice)
+timeslip_participation_fk = example.add_arc(tb_timeslip, op_participation)
+timeslip_lineitem_fk = example.add_arc(tb_timeslip, tb_lineitem)
+timeslip_workitem_fk = example.add_arc(tb_timeslip, ws_workitem)
+
+organization_division_of_fk.set_label("division_of").set_weight(0.5)
+project_organization_fk.set_label("organization").set_weight(0.5)
+person_organization_fk.set_label("organization").set_weight(1.0)
+participation_project_fk.set_label("project").set_weight(1.0)
+participation_person_fk.set_label("person").set_weight(1.0)
+private_info_person_fk.set_label("person").set_weight(1.0)
+workitem_project_fk.set_label("project").set_weight(1.0)
+workitem_worklist_fk.set_label("worklist").set_weight(0.5)
+worklist_workitem_fk.set_label("workitem").set_weight(1.0)
+worklist_person_fk.set_label("assigned_to").set_weight(0.5)
+dependency_of_workitem_fk.set_label("of").set_weight(1.0)
+dependency_on_workitem_fk.set_label("on").set_weight(1.0)
+issue_workitem_fk.set_label("workitem").set_weight(1.0)
+issue_person_fk.set_label("reported_by").set_weight(0.5)
+meeting_workitem_fk.set_label("workitem").set_weight(1.0)
+meeting_topic_meeting_fk.set_label("meeting").set_weight(1.0)
+standing_meeting_meeting_fk.set_label("meeting").set_weight(1.0)
+invoice_organization_fk.set_label("organization").set_weight(0.5)
+lineitem_invoice_fk.set_label("invoice").set_weight(1.0)
+timeslip_participation_fk.set_label("participation").set_weight(1.0)
+timeslip_lineitem_fk.set_label("lineitem").set_weight(0.5)
+timeslip_workitem_fk.set_label("workitem").set_weight(0.5)
+
+example.freeze()
+measure(example)
+rank(example)
+layer(example)
+order(example)
+place(example)
+
+example = example.clone()
+
+print
+print repr(example)
+
+print
+for node in example.nodes:
+    print repr(node)
+
+print
+for arc in example.arcs:
+    print repr(arc), arc.weight.value
+
+
+print
+for node in example.nodes_by_rank:
+    print node, node.rank.value
+
+print
+for layer in example.layers:
+    print repr(layer)
+    for bead in layer.beads:
+        print "\t", repr(bead)
+
+print
+for layer in example.layers:
+    print repr(layer)
+    for bead in layer.beads_by_order:
+        print "\t", repr(bead)
+
+print
+print "(%s, %s)" % (example.size.width, example.size.height)
+for node in example.nodes_by_rank:
+    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
+
+stream = open("example.png", "wb")
+#draw(example, stream)
+draw_smooth(example, stream)
+
+

draw.py

-
-from model import (ensure, WithGraphStyle, WithNodeLabel, WithNodeDimensions, WithGraphMargins,
-                   WithGraphSize, WithNodePosition, WithArcVertices)
-import cairo
-
-
-def measure(graph):
-    ensure(graph.readonly(WithGraphStyle, WithNodeLabel), "without graph style or node labels", graph)
-    ensure(not graph.readable(WithNodeDimensions), "already with node dimensions", graph)
-    ensure(not graph.readable(WithGraphMargins), "already with graph margins", graph)
-    graph.upgrade(WithNodeDimensions)
-    graph.upgrade(WithGraphMargins)
-
-    dummy_surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, 1, 1)
-    dummy_context = cairo.Context(dummy_surface)
-    dummy_context.set_font_size(graph.style.font_size)
-
-    extents = dummy_context.text_extents('M')
-    x_bearing, y_bearing, width, height, x_advance, y_advance = extents
-    m_width = width
-    m_height = height
-    graph.set_margins(int(3*m_width), int(3*m_height))
-
-    for node in graph.nodes:
-        extents = dummy_context.text_extents(node.label.text)
-        x_bearing, y_bearing, width, height, x_advance, y_advance = extents
-        node_width = int(width+m_width*2)
-        node_height = int(height+m_height*2)
-        node.set_dimensions(node_width, node_height)
-
-    graph.freeze(WithNodeDimensions)
-    graph.freeze(WithGraphMargins)
-
-    return graph
-
-
-def draw(graph, stream):
-    ensure(graph.readonly(WithGraphStyle), "without graph style", graph)
-    ensure(graph.readonly(WithGraphSize), "without graph size", graph)
-    ensure(graph.readonly(WithNodePosition), "without node positions", graph)
-    ensure(graph.readonly(WithArcVertices), "without arc vertices", graph)
-
-    surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, graph.size.width, graph.size.height)
-    context = cairo.Context(surface)
-    context.set_font_size(graph.style.font_size)
-
-    context.set_source_rgb(*graph.style.background_color)
-    context.rectangle(0, 0, graph.size.width, graph.size.height)
-    context.fill()
-
-    context.set_source_rgb(*graph.style.arc_color)
-    context.set_line_width(graph.style.arc_width)
-    for arc in graph.arcs:
-        context.new_path()
-        vertex = arc.vertices[0]
-        context.move_to(vertex.x, vertex.y)
-        for vertex in arc.vertices[1:]:
-            context.line_to(vertex.x, vertex.y)
-        context.stroke()
-
-    context.set_source_rgb(*graph.style.node_color)
-    for node in graph.nodes:
-        context.new_path()
-        context.rectangle(node.position.x, node.position.y, node.position.w, node.position.h)
-        context.fill()
-
-    context.set_source_rgb(*graph.style.border_color)
-    context.set_line_width(graph.style.border_width)
-    for node in graph.nodes:
-        context.new_path()
-        context.rectangle(node.position.x, node.position.y, node.position.w, node.position.h)
-        context.stroke()
-
-    if graph.readonly(WithNodeLabel):
-        context.set_source_rgb(*graph.style.text_color)
-        for node in graph.nodes:
-            if node.label is not None:
-                cx = node.position.x + node.position.w/2
-                cy = node.position.y + node.position.h/2
-                extents = context.text_extents(node.label.text)
-                x_bearing, y_bearing, width, height, x_advance, y_advance = extents
-                x = cx - (width/2 + x_bearing)
-                y = cy - (height/2 + y_bearing)
-                context.move_to(x, y)
-                context.show_text(node.label.text)
-
-    surface.write_to_png(stream)
-
-    return graph
-
-
-def draw_smooth(graph, stream):
-    ensure(graph.readonly(WithGraphStyle), "without graph style", graph)
-    ensure(graph.readonly(WithGraphSize), "without graph size", graph)
-    ensure(graph.readonly(WithNodePosition), "without node positions", graph)
-    ensure(graph.readonly(WithArcVertices), "without arc vertices", graph)
-
-    surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, graph.size.width, graph.size.height)
-    context = cairo.Context(surface)
-    context.set_font_size(graph.style.font_size)
-
-    context.set_source_rgb(*graph.style.background_color)
-    context.rectangle(0, 0, graph.size.width, graph.size.height)
-    context.fill()
-
-    context.set_source_rgb(*graph.style.arc_color)
-    context.set_line_width(graph.style.arc_width)
-    for arc in graph.arcs:
-        context.new_path()
-        if len(arc.vertices) > 2:
-            vertex = arc.vertices[0]
-            context.move_to(vertex.x, vertex.y)
-            for idx in range(1, len(arc.vertices)-1):
-                if idx == 1:
-                    vertex = arc.vertices[0]
-                    s_x, s_y = vertex.x, vertex.y
-                else:
-                    vertex1 = arc.vertices[idx-1]
-                    vertex2 = arc.vertices[idx]
-                    s_x, s_y = (vertex1.x+vertex2.x)/2, (vertex1.y+vertex2.y)/2
-                if idx == len(arc.vertices)-2:
-                    vertex = arc.vertices[-1]
-                    e_x, e_y = vertex.x, vertex.y
-                else:
-                    vertex1 = arc.vertices[idx]
-                    vertex2 = arc.vertices[idx+1]
-                    e_x, e_y = (vertex1.x+vertex2.x)/2, (vertex1.y+vertex2.y)/2
-                vertex = arc.vertices[idx]
-                q_x, q_y = vertex.x, vertex.y
-                x1, y1 = 1.0/3.0*s_x+2.0/3.0*q_x, 1.0/3.0*s_y+2.0/3.0*q_y
-                x2, y2 = 1.0/3.0*e_x+2.0/3.0*q_x, 1.0/3.0*e_y+2.0/3.0*q_y
-                x3, y3 = e_x, e_y
-                context.curve_to(x1, y1, x2, y2, x3, y3)
-        else:
-            vertex = arc.vertices[0]
-            context.move_to(vertex.x, vertex.y)
-            for vertex in arc.vertices[1:]:
-                context.line_to(vertex.x, vertex.y)
-        context.stroke()
-
-    context.set_source_rgb(*graph.style.node_color)
-    for node in graph.nodes:
-        context.new_path()
-        context.rectangle(node.position.x, node.position.y, node.position.w, node.position.h)
-        context.fill()
-
-    context.set_source_rgb(*graph.style.border_color)
-    context.set_line_width(graph.style.border_width)
-    for node in graph.nodes:
-        context.new_path()
-        context.rectangle(node.position.x, node.position.y, node.position.w, node.position.h)
-        context.stroke()
-
-    if graph.readonly(WithNodeLabel):
-        context.set_source_rgb(*graph.style.text_color)
-        for node in graph.nodes:
-            if node.label is not None:
-                cx = node.position.x + node.position.w/2
-                cy = node.position.y + node.position.h/2
-                extents = context.text_extents(node.label.text)
-                x_bearing, y_bearing, width, height, x_advance, y_advance = extents
-                x = cx - (width/2 + x_bearing)
-                y = cy - (height/2 + y_bearing)
-                context.move_to(x, y)
-                context.show_text(node.label.text)
-
-    surface.write_to_png(stream)
-
-    return graph
-
-

example-loop.py

-
-from model import build, WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight
-from draw import measure, draw
-from algorithm import rank, layer, order, place
-
-
-example = build(WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight)
-
-example.set_style(
-        background_color=(0.5, 0.5, 0.5),
-        node_color=(0.0, 0.0, 0.5),
-        arc_color=(0.5, 0.0, 0.0),
-        text_color=(1.0, 1.0, 1.0),
-        font_size=18.0)
-
-alpha = example.add_node()
-beta = example.add_node()
-gamma = example.add_node()
-
-alpha.set_label("alpha")
-beta.set_label("beta")
-gamma.set_label("gamma")
-
-alpha_beta = example.add_arc(alpha, beta)
-beta_gamma = example.add_arc(beta, gamma)
-gamma_alpha = example.add_arc(gamma, alpha)
-
-alpha_beta.set_label("alpha-beta").set_weight(1.0)
-beta_gamma.set_label("beta-gamma").set_weight(1.0)
-gamma_alpha.set_label("gamma-alpha").set_weight(1.0)
-
-example.freeze()
-measure(example)
-rank(example)
-layer(example)
-order(example)
-place(example)
-
-example = example.clone()
-
-print
-print "(%s, %s)" % (example.size.width, example.size.height)
-for node in example.nodes_by_rank:
-    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
-
-stream = open("example-loop.png", "wb")
-draw(example, stream)
-
-

example-polarity.py

-
-from model import WithGraphStyle
-from database import build_schema
-from draw import measure, draw, draw_smooth
-from algorithm import rank, rank_greedy, layer, order, place, polarize, place_polarized
-import sys
-
-if len(sys.argv) != 2:
-    print "Usage: %s <db>" % sys.argv[0]
-    sys.exit(1)
-db = sys.argv[1]
-
-example = build_schema(db)
-example.upgrade(WithGraphStyle)
-example.freeze()
-
-measure(example)
-rank_greedy(example)
-polarize(example)
-place_polarized(example)
-
-example = example.clone()
-
-print
-print repr(example)
-
-print
-for node in example.nodes:
-    print repr(node)
-
-print
-for arc in example.arcs:
-    print repr(arc), arc.weight.value
-
-print
-for node in example.nodes_by_rank:
-    print node, node.rank.value
-
-print
-for arc in example.arcs:
-    print repr(arc), arc.polarity.value
-
-print
-total = 0.0
-for node1 in example.nodes:
-    for node2 in example.nodes:
-        if node1.rank.value >= node2.rank.value:
-            continue
-        for arc1 in node1.outgoing:
-            if arc1.polarity.value == 0:
-                continue
-            t1 = min(arc1.origin.rank.value, arc1.target.rank.value)
-            b1 = max(arc1.origin.rank.value, arc1.target.rank.value)
-            for arc2 in node2.outgoing:
-                if arc2.polarity.value != arc1.polarity.value:
-                    continue
-                t2 = min(arc2.origin.rank.value, arc2.target.rank.value)
-                b2 = max(arc2.origin.rank.value, arc2.target.rank.value)
-                if t1 < t2 < b1 < b2 or t2 < t1 < b2 < b1:
-                    total += arc1.weight.value+arc2.weight.value
-print "CROSSINGS:", total
-
-stream = open("example-polarity.png", "wb")
-draw_smooth(example, stream)
-
-

example-regress.py

-
-from model import build, WithGraphStyle, WithNodeLabel, WithArcLabel, WithArcWeight
-from draw import measure, draw, draw_smooth
-from algorithm import rank, layer, order, place
-
-
-example = build(WithGraphStyle, WithNodeLabel, WithArcWeight)
-
-example.set_style(
-        arc_width=1.5,
-        border_width=1.5,
-        font_size=16.0)
-
-ad_school = example.add_node()
-ad_department = example.add_node()
-ad_program = example.add_node()
-ad_course = example.add_node()
-
-id_instructor = example.add_node()
-id_confidential = example.add_node()
-id_appointment = example.add_node()
-
-cd_semester = example.add_node()
-cd_class = example.add_node()
-
-ed_student = example.add_node()
-ed_enrollment = example.add_node()
-
-rd_prerequisite = example.add_node()
-rd_classification = example.add_node()
-rd_course_classification = example.add_node()
-rd_program_requirement = example.add_node()
-
-ad_school.se