#!/usr/bin/env python3 """ graph_maker 0.1 Usage: graphmaker.py [options] Create simple random planar graphs as examples for algorithm classes. The idea is to distribute nodes randomly and then connect them semi-randomly to neighbouring nodes, with the Euclidain distance plus a random noise factor for link weight. This will only be used for smallish graphs, so we go for slow but convenient algorithms ;-). Note to Coders: For optimal results, the output of all GraphViz tools should order nodes in ascending order, have all edges be from smaller to larger node, and have edges be in ascending order. This assures (?) uniform layout of equivalent graphs. Options: -h --help Print usage information. -v --vertices=v Specify the number of vertices (nodes). Default is 11. The naming convention supports up to 26 nodes. Fix this if you need more ;-). -e --edges=e Specify the number of edges. Edges always connect two different nodes, and there can be only one edge between any two nodes. If you request two many edges, the system will silently try to fulfill this request forever. Default is 22. -n --neighbours=n Number of nearest unconnected neighbours from which to chose the next link for a given node. The default is 3. -r --randomise=r Factor by which to disturb the Euclidean distance between two nodes to arrive at an edge weight. The distance is 1+random.uniform(0,r). Default is 1.5. -u --unique Enforce unique edge weights (good to get a unique solution for e.g. spanning tree algorithms. This takes the normal weight (see last option) and just increases it until an unused value is arrived at. -s --seed=s Seed for the random number generator. Use any string. Copyright 2019 Stephan Schulz, schulz@eprover.org This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program ; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA """ import sys import random import getopt from math import sqrt vertex_no = 11 edge_no = 22 randomiser = 1.5 neighbours = 3 unique_weight = False class Vertex(object): """ Arbitrary node in a planar graph. """ counter = ord("a") def __init__(self, x, y): self.name = chr(Vertex.counter) Vertex.counter+=1 self.x = x self.y = y self.edges = set([]) def isConnected(self): return self.edges def addEdge(self, v): self.edges.add(v) def __repr__(self): return "<%s:%2.5f %2.5f>"%(self.name, self.x, self.y) def EuclidDist(v1, v2): return sqrt((v1.x-v2.x)**2+(v1.y-v2.y)**2) class PlanarGraph(object): """ Planar graph: A list of vertixes, a distance matrix, and a link matrix with costs "inspired" by the Euclidean distance. """ def __init__(self, dimx=10, dimy=10): self.dimx = dimx self.dimy = dimy self.vertices = [] self.adjmatrix = {} self.used_weights = set([]) def addVertex(self, x, y): vertex = Vertex(x,y) self.vertices.append(vertex) def addRandomVertex(self): x = random.uniform(0, self.dimx) y = random.uniform(0, self.dimy) self.addVertex(x,y) def addRandomVertices(self, n): for i in range(n): self.addRandomVertex() def uniqueEdgeWeight(self, weight): while weight in self.used_weights: weight+=1 self.used_weights.add(weight) return weight def addEdge(self, v1, v2): if v1.name > v2.name: v1,v2 = v2, v1 dist = max(EuclidDist(v1, v2),1) weight = int(dist*(1+random.uniform(0,1.5))) if unique_weight: weight=self.uniqueEdgeWeight(weight) self.adjmatrix[(v1, v2)] = weight v1.addEdge(v2) v2.addEdge(v1) def addRandomEdges(self, n=20): for i in range(n): cands1 = [v for v in self.vertices if v.isConnected()] if not cands1: cands1 = self.vertices v1 = random.choice(cands1) cands2 = [v for v in self.vertices if not v.isConnected() and v!=v1] if not cands2: cands2 = self.vertices cands2.sort(key=lambda x:EuclidDist(x, v1)) v2 = random.choice(cands2[:neighbours]) while v1==v2 or v2 in v1.edges: v2 = random.choice(cands2[neighbours:]) self.addEdge(v1, v2) def __repr__(self): vertices = "\n".join(sorted([" "+v.name for v in self.vertices])) edges = "\n".join(sorted([" "+ v1.name + " -> " + v2.name + " [label=\""+str(self.adjmatrix[(v1,v2)])+"\"]" for (v1,v2) in self.adjmatrix.keys()])) res = """ digraph mygraph { rankdir=LR node [fontsize=18, style=solid] edge [fontsize=14, dir=none] %s %s } """%(vertices, edges) return res if __name__ == '__main__': random.seed() try: opts, args = getopt.gnu_getopt(sys.argv[1:], "hv:e:n:r:us:,", ["help", "vertices=", "edges=", "neighbours=", "randomis=", "unique", "seed="]) except getopt.GetoptError as err: print(err) # will print something like "option -a not recognized" print(__doc__) sys.exit(2) for opt, arg in opts: if opt in ("-h", "--help"): print(__doc__) sys.exit(0) elif opt in ("-v", "--vertices"): vertex_no = int(arg) elif opt in ("-e", "--edges"): edge_no = int(arg) elif opt in ("-n", "--neighbours"): neighbours = int(arg) elif opt in ("-r", "--randomise"): randomise = float(arg) elif opt in ("-u", "--unique"): unique_weight = True elif opt in ("-s", "--seed"): random.seed(arg) else: assert False, "Unhandled option ?!?" g = PlanarGraph() g.addRandomVertices(vertex_no) g.addRandomEdges(edge_no) print(g)