7
$\begingroup$

I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs.

More specifically, I work with labeled, directed multigraphs, and would like to be able to calculate and visualize especially the lexicographic product of such graphs.

Further, as it more precisely is a close variant of the lexicographic product I am interested in, it would be preferable if modifying the predefined operation is possible.

Specifically, I am interested in the following: where L(sG) constitute the set of labels on node s in graph G, and pre(tH) is one of two sets of labels for t in H, the product is one such that 1) the set of nodes is (s,t) such that pre(tH) is a subset of L(sG), 2) (s,t) and (s',t') are related in GxH as specified by the lexicographic product, and 3) the labels L(sGxH) are [those from L(sG) plus those from the second set of labels of t in H called post(t,H)] minus [those from L(sG) inconsistent with the new post(t,H)].

I do not assume that the program in question has the specified operation pre-programmed, but it would be very nice if it was implementable with some tampering.

Does any one know of a package that would allow this?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your edit is better suited as a comment on @jernej's post $\endgroup$ – Suresh Venkat Nov 30 '12 at 16:37
  • $\begingroup$ I don't quite follow what do you mean by "close variant". Can you describe more precisely what exactly do you want? $\endgroup$ – Jernej Dec 1 '12 at 12:31
  • $\begingroup$ Of course. I have done so now. I hope this is specific enough -- further details, I'm afraid, would require auxiliary definitions. $\endgroup$ – Rasmus Dec 4 '12 at 18:18
  • $\begingroup$ In terms of calculating the adjacency, for most products of graphs, it simply involves Kronecker products of the original adjacencies wiki.canisiusmath.net/… $\endgroup$ – Dimitris Dec 6 '12 at 18:15
6
$\begingroup$

I think that Sage is the right thing for this task.

Example.

sage: G = digraphs.Circuit(40)  
sage: G = G.lexicographic_product(G)
sage: G.show()

Other graph products and algorithms are available as well.

Improve this answer
$\endgroup$
0
$\begingroup$

try also this recent ref:

Visualization of Graph Products by Janicke et al, IEEE Transactions on Visualization and Computer Graphics (2010)

... Graph products constitute a class that arises frequently in graph theory, but for which no visualization algorithm has been proposed until now. In this paper, we present an algorithm for drawing graph products and the aesthetic criterion graph product's drawings are subject to. We show that the popular High-Dimensional Embedder approach applied to cartesian products already respects this aestetic criterion, but has disadvantages. We also present how our method is integrated as a new component into the TopoLayout framework. Our implementation is used for further research of graph products in a biological context.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.