Questão:
Alternativa para Graphviz com melhor posicionamento automático de nós para gráficos grandes?
Victor Stafusa
2014-02-05 03:24:47 UTC
view on stackexchange narkive permalink

No passado, usei o Graphviz para criar desenhos de gráficos. É uma boa ferramenta para gráficos pequenos.

Mas, infelizmente, para gráficos grandes, Graphviz é realmente uma merda:

  • Ele sempre cruzou bordas que obviamente poderiam ser desenhadas sem uma cruz.
  • Ele sobrepõe textos diferentes, tornando-os ilegíveis.
  • Não tem estilo reutilizável (como CSS), e você precisa repetir as mesmas personalizações em nós e bordas sobre, sobre e de novo.
  • Se o usuário quiser, basta dizer, trocar as posições de dois nós. Para fazer isso, é freqüentemente necessário hackear fortemente o arquivo de origem, provavelmente danificando partes não relacionadas do gráfico no processo.
  • É muito fácil fazer pequenas alterações em um local isolado do gráfico, Graphviz força grandes mudanças em outros lugares, frequentemente invalidando horas de trabalho tentando convencê-lo a fazer o desenho certo.
  • Ele desperdiça muito espaço no gráfico e ao mesmo tempo superlota alguns lugares com tanta força .
  • Às vezes, algumas arestas criam caminhos muito tortuosos para conectar o nó de origem ao nó de destino, apresentando curvas inúteis estranhas e muitas bordas laterais sobrepostas.
  • Possui efeitos de avalanche . Modificações triviais em algum lugar do gráfico podem perturbar a heurística do Graphviz, resultando em um gráfico completamente diferente.
  • Muitos bugs ...

Eu quero algo que como, um usuário, posso simplesmente:

  • Definir o que são os nós, possivelmente com estilo a ser aplicado.
  • Dizer quais são as arestas, possivelmente com estilo a ser aplicado.

E então o programa dá:

  • Um gráfico com o número mínimo possível de cruzamentos.
  • Nós bem alinhados são bons.

EU NÃO quero:

  • Adicionar muitos hacks na entrada apenas porque a ferramenta é muito estúpida para ver que poderia trocar dois nós específicos para remover um cruzamento.
  • É necessário posicionar manualmente as bordas e nós.
  • Obtenha efeitos de avalanche.

Então, o que pode ser um bom substituto do Graphviz? Eu realmente quero que seja gratuito.

Nota: Não me importo muito com o formato em que o gráfico deve ser inserido, contanto que eu possa salvar e editar um arquivo com o descrição do gráfico (qualquer que seja a linguagem de tal descrição). Portanto, não há absolutamente nenhuma necessidade de ainda estar na linguagem de ponto ou algo semelhante (na verdade, eu ficaria mais do que feliz em jogar fora meus arquivos de ponto inteiramente, pois há muito mais hacks do que a descrição de gráfico real lá). / p>

Vejam pessoal, é assim que você faz uma pergunta aqui (e vou ignorar a sinopse `graphviz realmente uma merda` porque você faz um bom trabalho explicando porque ela" é uma merda ").
Um colega de trabalho diz que d3.js obtém (a maior parte) o posicionamento correto. Obviamente, ele tem outros efeitos colaterais não tão agradáveis, como ser baseado em navegador e dinâmico (ou seja, nem todo mundo obtém a mesma saída), então pode não ser o que você deseja.
Antes de usar o Graphvis, eu estava gerando gráficos em Perl com Graph :: Easy (e com Graph). http://search.cpan.org/~tels/Graph-Easy/lib/Graph/Easy.pm Eu não recomendaria Graph ou Graph :: Easy. Eu migrei * para longe * deles para ter meu programa perl cuspindo um dotfile como uma string e executando o graphvis nele.
De acordo com mais informações de um pastor de vacas, o graphviz é muito bom (sim, sabemos o quão ruim a saída pode ser, mas o problema é totalmente não trivial) para o caso genérico. Se você puder fazer certas suposições (como nenhum ciclo), existem algoritmos melhores, mas o graphviz parece agrupá-los também (brinque um pouco com suas opções). Você precisa de armazenamento em cluster, e isso só se torna acessível mais fácil quando você pode usar suposições sobre os dados de entrada.
@mirabilos Acredite em mim, já experimentei várias opções (desde 2011). Se o gráfico não tivesse ciclo, degeneraria em algum tipo de árvore e seria fácil de desenhar. No entanto, meu gráfico tem muitos ciclos e cerca de 200 nós. Para lidar com isso com o graphviz, tive que quebrar o gráfico em 12 subgráficos independentes, repetindo os nós que aparecem em mais de um gráfico. Além disso, precisei adicionar muitos nós invisíveis, bordas e clusters. Em meus gráficos, os clusters têm pouco ou nenhum significado semântico, eles são apenas hacks para tentar forçar o graphviz a fazer seu trabalho direito.
@Oxinabox, sim, isso é triste. Mas, dado o grande número de hacks na heurística, tags e estrutura do graphviz, acho que reiniciar do zero seria muito melhor do que um fork.
Computational Science SE tem a mesma pergunta aqui: http://scicomp.stackexchange.com/questions/3315/visualizing-very-large-link-graphs.Besides GraphViz, existem várias opções disponíveis: Grátis * [JavaScript InfoVis Toolkit] ( http://philogb.github.com/jit/index.html)* [igraph] (http://igraph.sourceforge.net/) pacote para o [sistema estatístico R] (http: //cran.r-project .org /) * [zGrViewer] (http://zvtm.sourceforge.net/zgrviewer.html) * [Large Graph Library] (http://lgl.sourceforge.net/) Non-free * [GraphInsight] (http : //www.graphinsight.com/)
Eles não atendem às necessidades do OP porque é muito manual, mas para alguns usuários [Cupid] (http://nedbatchelder.com/blog/201401/svg_figures_with_cupid.html) é uma forma válida de proceder.
Você pode postar (ou fornecer um link para) um gráfico de amostra que gostaria de criar?
@Sebastian Bem, já saí da empresa onde tivemos este problema. Mas posso ter os dados em algum arquivo de backup em algum lugar.
Se você fizer isso, por favor, não poste aqui, para evitar problemas legais. Você não deve ter nenhum dado que pertença a uma empresa da qual você saiu.
Cinco respostas:
#1
+73
north at graphviz
2014-03-14 03:24:51 UTC
view on stackexchange narkive permalink

Desculpe pela decepção. O Graphviz poderia ser melhor de várias maneiras, mas neste ponto as perspectivas não são grandes porque AT&T não está apoiando o trabalho tanto quanto fazia no passado e alguns dos autores (como eu) deixaram de procurar outros trabalhos. Estamos à procura de pessoas que queiram assumir o controle, então nos informe.

Também estamos impressionados com yFiles.

Experimente também Software Tom Sawyer; eles têm muito talento de engenharia e trabalharam muito em métodos avançados de layout e ferramentas interativas. (Você pode precisar gastar $ $ $ $ porque o teste gratuito parece ter sido descontinuado.)

A pergunta não diz quais ferramentas ou opções de layout específicas foram testadas ou o quão grande é uma "grande" rede, então não está claro o que sugerir.

Se "grande" significa talvez centenas de nós, tente neato -Goverlap = false (para evitar a sobreposição do rótulo de texto do nó) e possivelmente -Gmodel = subset para tentar um melhor agrupamento. (Essas opções não são o padrão, porque na análise de dados, por exemplo, em bioinformática, uma incorporação de MDS direta oferece uma representação mais precisa das distâncias na rede subjacente.)

Se "grande" significa milhares de nós, talvez muitos milhares, use sfdp em vez de neato novamente com -Goverlap = false. (O modelo de distância de subconjunto não está disponível no sfdp, porque não está claro como lidar com comprimentos de aresta variáveis ​​ao mesclar arestas em um solucionador hierárquico.) Você pode ver um bom exemplo de um gráfico de 1054 nós aqui

Para "problemas de espaço desperdiçado" no caso de componentes desconectados, consulte também os atributos pack e packmode. As soluções para esses problemas não são óbvias (basicamente, você está tentando compactar formas irregulares de maneira ideal, com restrições adicionais e, às vezes, na escala do que as pessoas consideram "grande", então algoritmos subquadráticos são necessários). Para gráficos conectados, experimente -Opções de sobreposição.

Essas são as sugestões. Quanto a desculpas e explicações ...

O que alguém está chamando de "efeito avalanche" também é chamado de instabilidade de layout em relação a (pequenas) alterações no gráfico de entrada. Esta é uma propriedade de quase todos os programas de layout de gráfico em lote e solucionadores de restrições. Portanto, você deve procurar ferramentas interativas como o layout D3 spring embedder, e Tim Dwyer fez um grande trabalho nisso quando estava na Microsoft, então talvez algum dia o Graph Layout toolkit (AGL) adote seus métodos de restrição interativos. Apenas uma observação: a maioria dos pesquisadores e programadores não tentou atacar escala, interatividade e estética ao mesmo tempo (escolha qualquer uma das duas opções acima ...)

O problema de estilo também é bom , simplesmente não tínhamos tempo / energia para lidar com isso, já que a maioria dos gráficos são gerados automaticamente, então você pode aplicar estilos em alguma ferramenta ou script de pré-processamento. Também deve ser considerado que o gráfico não é apenas uma árvore de análise estática, mas depois que um gráfico é lido, sua folha de estilo ou os atributos dos objetos aos quais os estilos foram aplicados podem ser alterados e, em seguida, o gráfico deve ser escrito corretamente de uma forma que ainda preserva a estrutura original tanto quanto possível. Não intransponível, mas esses são detalhes que devem ser pensados ​​com cuidado.

Bugs podem ser relatados em www.graphviz.org em Bug and Issue Tracking.

Roteamento de borda global com curvas suaves - problema difícil. Observe que muitos layouts interessantes de algumas outras ferramentas usam bordas curvas, mas eles apenas desenham sobre todo o resto que está no caminho. Acho que adicionamos esse recurso ao graphviz também. Além disso, acho que havia um papel CHI ou INFOVIS mostrando que as bordas curvas são na verdade um pouco mais difíceis de ler corretamente do que as linhas retas.

Cruzamentos - alguma otimização local pode ser possível. Não tenho certeza de qual ferramenta está sendo usada. É fácil apontar exemplos específicos onde os layouts poderiam ser melhores, mas é mais difícil inventar uma solução eficaz em que o "número mínimo de cruzamentos" não piorasse as coisas em geral.

Observe que estou diretamente afiliado ao Graphviz.

Eu votei a favor. Stephen North é um [especialista reconhecido] (http://scholar.google.co.uk/citations?user=_QJP9-0AAAAJ&hl=en) em visualização de gráficos e, devido ao ataque do OP ao Graphviz, é precioso ter seu insight como uma resposta. (Eu entendo a frustração do OP, mas fazer gráficos é um problema difícil)
#2
+30
Sebastian
2014-03-10 17:51:38 UTC
view on stackexchange narkive permalink

Minha recomendação de software é " yEd" - um aplicativo gratuito para desenho de gráficos de uso geral que tenta muito resolver os problemas que você tem enfrentado. Até onde sei, este software usa as melhores implementações disponíveis gratuitamente dos algoritmos de layout.

Agora, a resposta mais detalhada que seria mais adequada para StackOverflow do que para "Recomendação de software":

O problema que você está tentando resolver é realmente difícil (especialmente no sentido de computacionalmente difícil ), então é improvável que você encontre uma ferramenta que possa resolver todos os seus problemas igualmente bem. Existem várias soluções gratuitas (provavelmente o GraphViz é uma das melhores) e vários concorrentes comerciais. Para a biblioteca de desenho gráfico yFiles comercial, há um aplicativo de plataforma cruzada gratuito (como na cerveja) disponível, que você pode experimentar. Ele pode importar dados de vários formatos diferentes, aplicar mapeamentos de estilo aos seus dados e oferece uma grande coleção de diferentes algoritmos de layout. É chamado yEd e pode ser executado sem qualquer instalação em uma versão da web a partir daqui. A versão desktop pode ser iniciada como um aplicativo java "webstart" diretamente do navegador ou após a instalação de um dos programas independentes para Windows, Linux e Mac.

Alguns dos algoritmos de layout provavelmente não devem ser usados com gráficos muito grandes (dezenas de milhares de elementos), porque eles serão executados por muito tempo ou requerem muita memória, mas na maioria das vezes há pelo menos um estilo de layout que deve se adequar bem aos seus dados. Se você precisar programar com a API, precisará licenciar a biblioteca subjacente (disponível para Java, .net, Javascript), o que vai contra o seu requisito "gratuito", mas isso lhe daria ainda mais controle sobre o layout.

Exoneração de responsabilidade : trabalho para a empresa que cria este produto (gratuito), mas no Stack Exchange não represento meu empregador. Passei a maior parte do meu tempo acadêmico e profissional em software de desenho gráfico desde o final dos anos 1990 e acredito ter um conhecimento muito profundo sobre o mercado e os softwares disponíveis (gratuitos e comerciais). Pode haver outras ferramentas disponíveis e espero que este site traga ótimas alternativas - certamente não as negarei.

+1. A solicitação de OP é impossível (o programa dá um gráfico com o número mínimo possível de cruzamentos, para um gráfico grande -> NP-difícil então boa sorte). Essa resposta é de qualidade especializada.
Eu votei positivamente também. Se existe um lugar onde você deseja que os especialistas participem, é sobre problemas difíceis, e é especialmente bom ouvir os especialistas quando se trata de obter software.
Para converter do GraphViz (`.dot`) para um formato que yEd possa ler, use [dottoxml] (https://bitbucket.org/dirkbaechle/dottoxml).
Como um usuário independente do yEd (não afiliado à empresa), confirmo que o yEd é o melhor software gratuito disponível no mercado (e tentei muitos)
#3
+16
Franck Dernoncourt
2014-03-14 05:43:03 UTC
view on stackexchange narkive permalink

Para responder de forma muito específica à solicitação da pergunta, já que as outras duas respostas fizeram um ótimo trabalho ao se expandir:

O que você pergunta não é possível. Você quer um programa que forneça um "gráfico com o mínimo possível de cruzamentos." E solicitou especificamente que o programa funcione para gráficos grandes.

No entanto, determinar o número de cruzamento de um gráfico é um problema NP-difícil (Garey e Johnson mostraram que é NP-completo em 1983).

Portanto, tal programa não será capaz de garantir encontrar o gráfico com o mínimo possível de cruzamentos em um período de tempo razoável, tornando o programa inútil.

Pode haver um número "razoavelmente pequeno" de travessias, não um mínimo estritamente global.
#4
+5
BrianV
2019-11-15 04:01:36 UTC
view on stackexchange narkive permalink

Isso certamente seria considerado uma "solução baseada no GraphViz", mas se você estiver trabalhando com o GraphViz, pode dar uma olhada em Gephi. É muito mais capaz quando se trata de processar gráficos grandes.

#5
+1
user11879
2018-11-17 00:04:44 UTC
view on stackexchange narkive permalink

PlantUML é uma ferramenta de código aberto que permite aos usuários criar diagramas UML a partir de uma linguagem de texto simples. A linguagem do PlantUML é um exemplo de uma linguagem específica de aplicação. Ele usa o software Graphviz para fazer o layout de seus diagramas. Ele tem sido usado para permitir que alunos cegos trabalhem com UML. O PlantUML também ajuda engenheiros de software cegos a projetar e ler diagramas UML.

enter image description here

Desculpe, mas isso não ajuda em nada. O autor pede explicitamente um software que resolva os problemas melhor do que o GraphViz. Portanto, isso obviamente exclui as soluções baseadas no GraphViz. E os diagramas UML certamente também não são os aplicativos típicos para "gráficos grandes". Você quis dizer responder a uma pergunta diferente?


Estas perguntas e respostas foram traduzidas automaticamente do idioma inglês.O conteúdo original está disponível em stackexchange, que agradecemos pela licença cc by-sa 3.0 sob a qual é distribuído.
Loading...