algorithm - Eliminating symmetry from graphs -


i have algorithmic problem in have derived transfer matrix between lot of states. next step exponentiate it, large, need reductions on it. contains lot of symmetry. below examples on how many nodes can eliminated simple observations.

my question whether there algorithm efficiently eliminate symmetry in digraphs, way i've done manually below.

in cases initial vector has same value nodes.

in first example see b, c, d , e receive values a , 1 of each other. hence contain identical value, , can merge them.

digraph a digraph b

in example spot, graph identical point of view of a, b, c , d. respective sidenodes, doesn't matter inner node attached. hence can reduce graph down 2 states.

digraph c digraph d

update: people reasonable enough not quite sure meant "state transfer matrix". idea here is, can split combinatorial problem number of state types each n in recurrence. matrix tell how n-1 n.

usually interested value of 1 of states, need calculate others well, can next level. in cases however, multiple states symmetrical, meaning have same value. it's quite waste calculate of these, want reduce graph until nodes "unique".

below example of transfer matrix reduced graph in example 1.

[s_a(n)]   [1  1  1] [s_a(n-1)] [s_f(n)] = [1  0  0]*[s_f(n-1)] [s_b(n)]   [4  0  1] [s_b(n-1)]

any suggestions or references papers appreciated.

brendan mckay's nauty ( http://cs.anu.edu.au/~bdm/nauty/) best tool know of computing automorphisms of graphs. may expensive compute whole automorphism group of graph, might able reuse of algorithms described in mckay's paper "practical graph isomorphism" (linked nauty page).


Comments

Post a Comment

Popular posts from this blog

apache - Add omitted ? to URLs -

i working on website cms reads page name of query string, e.g. http://exmaple.com/?pagename . trying create rewrite rule rewrite ? . so, user types in /pagename , taken /?pagename try this: rewriteengine on rewritecond %{request_filename} !-d rewritecond %{request_filename} !-f rewriterule ^/?(.*) index.php?$1 [l]
Read more

redirect - bbPress Forum - rewrite to wwww.mysite prohibits login -

i using bbpress installation without wordpress integration. the redirect of rewriteengine @ forum site works: rewriteengine on rewritecond %{http_host} ^forum.mysite.com$ rewriterule (.*)$ http://www.forum.mysite.com/$1 [r=301,l] the problem login pppress. bbpress login not recognize: http://www.forum.mysite/bb-login.php . it redirects to: http://forum.mysite.com/bb-login.php . i tried permalink settings none , name based, same issue. does uses redirect in bbpress or how can eliminate "double" content , redirect permanently www.? i redirected www.forum.mysite.com forum.mysite.com , achieved eliminate "double" content.
Read more

php - How can I stop spam on my custom forum/blog? -

so have custom built forum & blog system of late has been dealing lot of spam. if wordpress use akismet, if different common platform i'm sure i'd find plugin. there kind of static class can download this? using php. i'd still go akismet, if it. uses outside of wordpress, may have pay fee it, depending on use -- check terms , conditions -- it's option , easy implement in php using api. use api key wordpress. com account access. basically, grab whichever php client library takes fancy -- use alex potsides' php5 library -- plug in key, , it's handful of lines of code. here's bare bones of validation straight 1 of live sites: ... if ($akismet) { $akismet->setcommentauthor($name); $akismet->setcommentauthoremail($session->userinfo["email"]); $akismet->setcommentauthorurl(""); $akismet->setcommentcontent($sentence);...
Read more