| 1 |
#!/usr/bin/env python |
| 2 |
|
| 3 |
# $Id: sixtest.py,v 1.5 2008/02/06 22:59:39 joko Exp $ |
| 4 |
|
| 5 |
# (c) 2008 Andreas Motl <andreas.motl@ilo.de> |
| 6 |
|
| 7 |
# This program is free software: you can redistribute it and/or modify |
| 8 |
# it under the terms of the GNU Affero General Public License as published by |
| 9 |
# the Free Software Foundation, either version 3 of the License, or |
| 10 |
# (at your option) any later version. |
| 11 |
# |
| 12 |
# This program is distributed in the hope that it will be useful, |
| 13 |
# but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 14 |
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 15 |
# GNU Affero General Public License for more details. |
| 16 |
# |
| 17 |
# You should have received a copy of the GNU Affero General Public License |
| 18 |
# along with this program. If not, see <http://www.gnu.org/licenses/>. |
| 19 |
|
| 20 |
|
| 21 |
|
| 22 |
# Uses BGL-Python (depth_first_search) |
| 23 |
# |
| 24 |
# BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/ |
| 25 |
# |
| 26 |
# Documentation: |
| 27 |
# - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html |
| 28 |
# - http://www.boost.org/libs/graph/doc/depth_first_search.html |
| 29 |
# |
| 30 |
# Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/ |
| 31 |
|
| 32 |
|
| 33 |
import sys, os |
| 34 |
|
| 35 |
sys.path.append('bgl_python') |
| 36 |
os.environ['PATH'] += ';' + './bgl_python' |
| 37 |
|
| 38 |
import boost.graph as bgl |
| 39 |
|
| 40 |
|
| 41 |
|
| 42 |
# from http://www.boost.org/libs/graph/doc/DFSVisitor.html |
| 43 |
class tree_edges_dfs_visitor(bgl.dfs_visitor): |
| 44 |
|
| 45 |
def __init__(self, name_map): |
| 46 |
#bgl.dfs_visitor.__init__(self) |
| 47 |
self.name_map = name_map |
| 48 |
self.state = True |
| 49 |
|
| 50 |
def tree_edge(self, e, g): |
| 51 |
(u, v) = (g.source(e), g.target(e)) |
| 52 |
print "Tree edge ", |
| 53 |
print self.name_map[u], |
| 54 |
print " -> ", |
| 55 |
print self.name_map[v] |
| 56 |
self.state = True |
| 57 |
|
| 58 |
def start_vertex(self, v, g): |
| 59 |
#print 'sssss' |
| 60 |
self._seperator() |
| 61 |
|
| 62 |
def initialize_vertex(self, v, g): |
| 63 |
#print '>>>' |
| 64 |
self._seperator() |
| 65 |
|
| 66 |
def finish_vertex(self, v, g): |
| 67 |
#print '<<<' |
| 68 |
self._seperator() |
| 69 |
|
| 70 |
def _seperator(self): |
| 71 |
if self.state: |
| 72 |
print '-' * 21 |
| 73 |
self.state = False |
| 74 |
|
| 75 |
def build_fixed_graph(): |
| 76 |
graph = bgl.Graph() |
| 77 |
|
| 78 |
#graph.add_vertex_property_map(name='my_name', type='float') |
| 79 |
|
| 80 |
# 'write_graphviz' requires property 'node_id' on vertices |
| 81 |
# see http://lists.boost.org/boost-users/2006/06/19877.php |
| 82 |
vmap = graph.vertex_property_map('string') |
| 83 |
graph.vertex_properties['node_id'] = vmap |
| 84 |
|
| 85 |
|
| 86 |
v1 = graph.add_vertex() |
| 87 |
vmap[v1] = '1' |
| 88 |
|
| 89 |
v2 = graph.add_vertex() |
| 90 |
vmap[v2] = '2' |
| 91 |
|
| 92 |
v3 = graph.add_vertex() |
| 93 |
vmap[v3] = '3' |
| 94 |
|
| 95 |
v4 = graph.add_vertex() |
| 96 |
vmap[v4] = '4' |
| 97 |
|
| 98 |
e1 = graph.add_edge(v1, v2) |
| 99 |
e2 = graph.add_edge(v1, v3) |
| 100 |
e3 = graph.add_edge(v3, v4) |
| 101 |
|
| 102 |
""" |
| 103 |
for vertex in graph.vertices: |
| 104 |
#print vertex.id, vertex |
| 105 |
print vmap[vertex], vertex |
| 106 |
#print vertex.__getattribute__('id') |
| 107 |
#print vertex['id'] |
| 108 |
#print vertex.get('id') |
| 109 |
#print |
| 110 |
""" |
| 111 |
|
| 112 |
graph.write_graphviz('friends.dot') |
| 113 |
|
| 114 |
return graph |
| 115 |
|
| 116 |
|
| 117 |
|
| 118 |
def main(): |
| 119 |
|
| 120 |
# Load a graph from the GraphViz file 'mst.dot' |
| 121 |
#graph = bgl.Graph.read_graphviz('mst.dot') |
| 122 |
graph = build_fixed_graph() |
| 123 |
|
| 124 |
# Compute all paths rooted from each vertex |
| 125 |
#mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight) |
| 126 |
#bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None) |
| 127 |
for root in graph.vertices: |
| 128 |
print |
| 129 |
print '=' * 42 |
| 130 |
print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root] |
| 131 |
visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id']) |
| 132 |
bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None) |
| 133 |
|
| 134 |
|
| 135 |
# STOP HERE |
| 136 |
sys.exit(0) |
| 137 |
|
| 138 |
|
| 139 |
|
| 140 |
|
| 141 |
|
| 142 |
# Compute the weight of the minimum spanning tree |
| 143 |
#print 'MST weight =',sum([weight[e] for e in mst_edges]) |
| 144 |
|
| 145 |
# Put the weights into the label. Make MST edges solid while all other |
| 146 |
# edges remain dashed. |
| 147 |
label = graph.edge_property_map('string') |
| 148 |
style = graph.edge_property_map('string') |
| 149 |
for e in graph.edges: |
| 150 |
label[e] = str(weight[e]) |
| 151 |
if e in mst_edges: |
| 152 |
style[e] = 'solid' |
| 153 |
else: |
| 154 |
style[e] = 'dashed' |
| 155 |
|
| 156 |
# Associate the label and style property maps with the graph for output |
| 157 |
graph.edge_properties['label'] = label |
| 158 |
graph.edge_properties['style'] = style |
| 159 |
|
| 160 |
# Write out the graph in GraphViz DOT format |
| 161 |
graph.write_graphviz('friends_path_2to3.dot') |
| 162 |
|
| 163 |
|
| 164 |
if __name__ == '__main__': |
| 165 |
main() |
Parent Directory
| 
Revision Log
