CODEWITHSUNDEEP
algorithmgraph
krajol
krajol

Reputation: 848

Graph transformation - vertices into edges and edges into vertices

is there any algorithm or is there any name for a transformation of a graph where one can transform edges into vertices and vertices into edges? Just so we could get a new graph out of it or anything similiar to this problem? I'm not sure if it actually makes sense but I'd be glad if you could give me just any hint about a problem like this.

Upvotes: 22

Views: 13656

Answers (4)

Chidi
Chidi

Reputation: 991

What you are asking for is a line graph. You can use the networkx line_graph function to create a line graph or dual graph of a given graph. However, note that this function does not propagate the data from the original graph so you will have to hack your way around that if you need it.

Upvotes: 3

brgn
brgn

Reputation: 1213

Have you thought about pattern-based graph transformation? Like that you would

  • search for a graph pattern, e.g. the kind of edge that you'd like to turn into a node, and
  • define the operation of transforming that edge into a node/vertex, e.g. transferring all the edge properties into properties of the new node/vertex.

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

There is a lot of scientific literature available in that field, e.g.: http://www.springer.com/de/book/9783319211442

There are also specialized development solutions for graph transformation, like Soley Studio.

Hope that helps.

Upvotes: 3

Vitaliy Kaurov
Vitaliy Kaurov

Reputation: 1300

LineGraph is a built-in function in Wolfram Language:

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

This is what it 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 share a common vertex.
  • For a directed graph g, two vertices in LineGraph[g] are adjacent if their corresponding edges are connected, i.e. the target of one edge is the source of the other edge.
  • LineGraph works with undirected graphs, directed graphs, and multigraphs.

Upvotes: 4

Francesco Turci
Francesco Turci

Reputation: 837

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

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

Upvotes: -1

Related Questions