Geek Answers Handbook

Convert graph - vertices to edges and edges to vertices

is there any algorithm or is there any name for transforming a graph where you can convert edges to vertices and vertices to edges? Just so we can get a new schedule or something similar to this problem? I'm not sure if this really makes sense, but I would be glad if you could give me at least some hint of such a problem.

+7
source share
3 answers

LineGraph is a built-in function in the Wolfram language:

http://reference.wolfram.com/language/ref/LineGraph.html

This is what he does:

  • Each vertex in LineGraph [g] corresponds to an edge in g.
  • For an undirected graph g, two vertices in LineGraph [g] are adjacent if their corresponding edges have a common vertex.
  • For a directed graph g, two vertices in LineGraph [g] are adjacent if their corresponding edges are connected, that is, the target of one edge is the source of the other edge.
  • LineGraph works with undirected graphs, directional graphs and multigraphs.
+1
source

I believe that you can easily turn edges into vertices using the following Python library: http://networkx.lanl.gov/

You can get a list of edges, a list of nodes and exchange two for building a new graph. You just need some (basic) knowledge of Python.

0
source

Have you thought about transforming a graph based on a template ? As if you

  • search for a graphic template, for example. the type of edge you would like to turn into a node, and
  • define the operation of converting this edge to the node / vertex, for example. Transfer all edge properties to the properties of the new node / vertex.

In the graph transformation literature, these two steps are called the left and right side of the graph-transform-rule .

There is a lot of scientific literature in this area, for example: http://www.springer.com/de/book/9783319211442

There are also specialized designs for transforming graphs, such as Soley Studio .

Hope this helps.

0
source

More articles:


All Articles