(r4) IsomorphicDoc < FST

FST Web>FstQuickTour>IsomorphicDoc (revision 4) (raw view)~~EditAttach~~

---+ Isomorphic  %ICON{"wip"}%

---++ Description

This operation determines if two transducers with a [[IsomorphicDoc#IsomorphicCaveats][certain required determinism]] have the same states, irrespective of numbering, and the same transitions with the same labels and weights, irrespective of ordering. In other words, =Isomorphic(A, B)=  is true if and only if the states of A can be renumbered and the transitions leaving each state reordered so that [[EqualDoc][Equal(A, B)]] is true.

---++ Usage

| <verbatim>
template <class Arc>
bool Isomorphic(const Fst<Arc> &fst1,
                const Fst<Arc> &fst2,
                double delta = kDelta);
</verbatim> | %DOX{namespacefst.html#Isomorphic[%H%]}% |
| <verbatim>
fstisomorphic a.fst b.fst
</verbatim> ||

---++ Examples

| ==A== | ==B== | ==C==|
| %ATTACHURL%/iso1.png |  %ATTACHURL%/iso2.png |  %ATTACHURL%/iso3.png | 

<verbatim>
Isomorphic(A, B);  // returns true
Isomorphic(A, C);  // returns false

$ if fstisomorphic a.fst b.fst; then echo true; else echo false; fi
true
$ if fstisomorphic a.fst c.fst; then echo true; else echo false; fi
false
</verbatim>



---++ Complexity

=Isomorphic=
   * Time: O(_V<sub>1</sub>_ + _V<sub>2</sub>_ + _E<sub>1</sub> log D<sub>1</sub>_ + _E<sub>2</sub>  log D<sub>2</sub>_)
   * Space:  O(_V<sub>1</sub>_ + _V<sub>2</sub>_  + _D<sub>1</sub>_ + _D<sub>2</sub>_)
where  _V<sub>i</sub>_ = # of states, _E<sub>i</sub>_ = # of transitions,  _D<sub>i</sub>_ = maximum [[FstGlossary#OutDegreeDef][out-degree]]

#IsomorphicCaveats
---++ Caveats

The inputs should be deterministic in the sense that no state has two transitions with the same input label, output label and weight (e.g., deterministic after [[EncodeDecodeDoc][Encode]] is performed on the labels and weights). If non-determinism in this sense is encountered, an error is raised.
This requirement is imposed since the general solution is _graph isomorphism complete_, for which no known polynomial-time algorithm exists.

---++ See Also

[[EqualDoc][Equal]], [[EquivalentDoc][Equivalent]], [[RandEquivalentDoc][RandEquivalent]]


---++ References

Zemlyachenko, Viktor N., Nickolay M. Korneenko, and Regina I. Tyshkevich. "Graph isomorphism problem." Journal of Soviet Mathematics 29.4 (1985): 1426-1481.

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who
png	iso1.png	r1	manage	9.4 K	2014-04-23 - 00:26	MichaelRiley
png	iso2.png	r1	manage	9.5 K	2014-04-23 - 00:26	MichaelRiley
png	iso3.png	r1	manage	11.4 K	2014-04-23 - 00:26	MichaelRiley

Topic revision: r4 - 2014-04-23 - MichaelRiley