关键词: 带权图, 无向图, 遗传算法, 画图, 权长相合

Abstract: Concerning the problem that the weighted undirected graphs output is needed to demonstrate weights with edge lengths, a new algorithm for weighted undirected graphs based on genetic algorithm was proposed. The algorithm obtained the ideal vertex coordinates by the crossover and mutation on the vertex coordinate coding. The mutation operator combined the inconsistent mutation with single neighbourhood mutation. In the fitness function, four evaluation criteria were employed: the average distance of the vertex, the edge crossing number, the uniformity of the angles around the multi-degree vertex, and the uniformity of the ratios of edge weight and edge length. The experimental results show that the drawn graph by the proposed algorithm is featured with edge-crossing-free, clear showing of branches and weight-length consistency. The visual output results of the algorithm are clear, visually optimized and especially faithful to weights. The algorithm is suitable to draw most kinds of weighted undirected graphs and can be used in undirected graph drawing methods and/or prototypes.

Key words: weighted graph, undirected graph, genetic algorithm, graph drawing, weight-length consistency