search for: isomorph

Dear All, Sorry for the typoes earlier, let me repost the question. Suppose I want to generate sequences of length 3 from two symbols {1,2}, we get the following 8 sequences 1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2 However, I do not want all these 8 sequences. I call two sequencs to be isomorphic if one sequence could be obtained from the other by relabelling the symbols. For example, 111 is isomorphic to 222, 112 is isomorphic to 221. By eliminating all these isomorphic ones, what I want is the following 1 1 1 1 1 2 1 2 1 2 1 1 In general, I need to generate non-isomorphic sequences of...

...me confusion as to whether it was possible to solve the code > folding outlining problem exactly as a graph problem on SSA using standard > value numbering algorithms in polynomial time. > > I can elaborate further, but > 1. it is easy to see that you can map an arbitrary dag to an isomorphic > data flow graph in an SSA IR e.g. in LLVM IR or pre-RA MIR > > 2. Given two dags, you can create their respective isomorphic data flow > graphs (say, put them into two separate functions) > 3. An exact graph based code folding outliner would be able to discover if > the two...

...he paper (from which it seems like it addresses the problem possibly in a more general manner): "The widely used bottom-up SLP algorithm has been improved in several ways. Porpodas et al. [32] propose PSLP, a technique that pads the scalar code with redundant instructions, to convert non-isomorphic instruction sequences into isomorphic ones, thus extending the applicability of SLP. Just like VW-SLP-S, PSLP can vectorize code when some of the lanes differ, but it is most effective when the non-isomorphic parts are only a short section of the instruction chain. VW-SLP, on the other hand,...

Dear R users, i have this problem with matrices i want to check between two matrices if they are isomorphic i will give an example for what excactly i want   1 -1  1                                 -1  1   1 -1   1  -1                                1  -1  -1   1  1   -1                                1   1  -1 this two matrices are isomorphic beacause if i change the first 2 columns the matrices are i...

Hi all, I want to find all the mappings of one graph in another graph, based on their vertex labels Is there any way to do this in igraph based on vertex labels. (as far as i know Igraph allows the subgraph isomorphism based only on vertex and edge colors) Eg: graph 1: x(1) x(2) x(2) y(3) y(4) x(1) z(5) x(2) graph 2: x(1) y(2) # the brackets contain the corresponding vertex ids i would like my output to contain the two mappings from graph 1 i.e x(2) y(3) & x(1) y(4) Regards, Himanshu Mittal [[altern...

I have 3003 16x5 submatrices from a hadamard matrice of 16x15. I want to write an algorithm that check all of these 3003 matrices if they are isomorphic and i want to find and keep the non-isomorphic ones. Any help will be welcome.  [[alternative HTML version deleted]]

Dear R users,  I have 2 matrices dim(16x5) below and i want to write an algorithm that check the 2 matrices if they are isomorphic ones (Isomorphic matrices: if I change the rows or/and columns or/and zeros into 1 and 1 into zeros in a row(s) or column(s) are the 2 matrices identical). 0    0    0    0    0  1    0    1    0    1  0    1    1    0    0  1    1    0    0    1  0    0    0    1    1  1    0    1    1    0  0  ...

...same name from different modules are renamed so their names are unique (%struct.foobar in the second module becomes %struct.foobar.0). After renaming intrinsic names and signatures can become inconsistent. Usually it slips unnoticed because we don't verify individual modules and eventually map isomorphic types to a single type. So isomorphic types get their original names. Although in some cases it causes problems. Initially I came across the problem with my recent change which added an overloaded type to the masked load/store intrinsics (http://reviews.llvm.org/D17270). The discrepancy between...

While playing with SLPVectorizer, I notice that it will happily vectorize cases involving extractelement/insertelement, but won't vectorize isomorphic cases involving extractvalue/insertvalue (such as the attached example). Is that something that could be straightforward to add to SLPVectorizer, or are there some hard issue? In particular, the transformation would seem to require casts of structures to vectors and back. The bitcast instructi...

...res can become > inconsistent. > > This seems like a clear bug in the module loading. If we're changing type > names, we need to change the intrinsic signatures as well. > > > Usually it slips unnoticed because we don't verify individual modules and > eventually map isomorphic types to a single type. So isomorphic types get > their original names. Although in some cases it causes problems. > > Initially I came across the problem with my recent change which added an > overloaded type to the masked load/store intrinsics > (http://reviews.llvm.org/D17270)....

...derstand this request differently. This is on LLVM-IR, so register allocation would happen on the merged block. I-Cache utilization should improve since there is less code in the merged blocked compared to the two original blocks. I could imagine an algorithm that checks whether the two blocks are isomorphic and have the same jump targets. Then merge the two blocks (including adding PHIs if the blocks have different predecessors) by RAUW one block with this other. In the example, both blocks have the same predecessor, i.e. it will be a conditional branch. In this case the transformation (after havin...

Is it legal to substitute non struct type instead of opaque type? For example: ; 1.ll declare void @F(i32*) ; 2.ll %T1 = type opaque declare void @F(%T1*) Is it normal to replace T1 with i32 here? If yes. Will the next types are isomorphic?: %T1 = type opaque { i32, %T1* } { i32, i32* } -Stepan.

i have this problem with matrices i want to check between two matrices if they are isomorphic i will give an example for what excactly i want   1 -1  1                                 -1  1   1 -1   1  -1                                1  -1  -1   1  1   -1                                1   1  -1 this two matrices are isomorphic beacause if i change the first 2 columns the matrices are i...

...eterministic algorithm for Matching Weighted Graphs with bounded degree. Now we all know Graph matching is non-tractable but when degree of vertex has upper bound are there any tractable algorithm? Does this special case comes under 'Finite Parameter Tractability' ? Also we know that Graph isomorphism where degree of vertex has upper bound has tractable algorithms. So will it be possible to reduce the Graph matching problem with bounded degree to Graph isomorphism of bounded degree problem then our original problem will have tractable solution. Appreciate any help or pointer which may take u...

> > > I don't agree, but this is because I fail to see how the two > representations (the GCC-like one you've outlined and the current one with > the proposed extension) aren't completely isomorphic. Your proposal is: > > Lots of data structures are completely isomorphic in the same way, and in plenty of those cases, one is completely unusable, and the other functions quite well. Your below is basically "one is drawn in one direction, and the other is drawn the other". This...

...e: > ; 1.ll > declare void @F(i32*) > > ; 2.ll > %T1 = type opaque > declare void @F(%T1*) > > Is it normal to replace T1 with i32 here? Yes, the linker will do this, because it is forced to break type safety to link up the functions. > If yes. Will the next types are isomorphic?: > > %T1 = type opaque > { i32, %T1* } > { i32, i32* } No. opaque types are instances of struct types and are uniqued by name. i32 is not a struct type. These two types are also not isomorphic: > %T1 = type opaque > %T2 = type opaque > { i32, %T1* } > { i32, %T2* }...

OK. So if we have two modules with the same function name. This functions may not be isomorphic. For example, we can link this files, but the function types are not isomorphic: ; 1.ll %T1 = type opaque declare i32 @foo(%T1*) ; 2.ll define i32 @foo(i32* %v) {...something...} But at the same time we should not map next two functions (PR11627): ; 3.ll declare i32 @foo(i16* %v) ; 4.ll de...

Dear R users, I want a help to write an algorithm for swapping rows and columns in a matrix thanks in advance [[alternative HTML version deleted]]

I'm looking for where in the source recycling and vector multiplication+addition are defined. I see some stuff in ~/src/main/arithmetic.c. Is there anywhere else I should be looking as well? Cheers -- isomorphisms at sdf.org SDF Public Access UNIX System - http://sdf.org

...reason for this limitation other than no one thinking of > it? Does it need to have all the type information early in building > the parser tree? I can't really imagine that. I for one could do > without this limitation. You really can't do this since LLVM types are shape isomorphic. Observe what happens to the types of @x and @y: gordon$ cat input.ll %xty = type {i32} %yty = type {i32} @x = external constant %xty @y = external constant %yty gordon$ llvm-as < input.ll | llvm-dis ; ModuleID = '<stdin>' %xty...