Примечание: см. Информацию о Graphviz ниже.
Это должно дать вам отправную точку:
Редактировать: Эта версия обрабатывает геныкоторые описываются более чем одним символом.
awk '
BEGIN { regdelim = "|" }
{
delim=""
if ($2 == "+") {
if (plus[$1]) delim=regdelim
plus[$1]=plus[$1] delim $3
}
else
if ($2 == "-") {
if (minus[$1]) delim=regdelim
minus[$1]=minus[$1] delim $3
}
}
END {
for (root in plus) {
split(plus[root],regs,regdelim)
for (reg in regs) {
if (plus[regs[reg]] && plus[root] ~ plus[regs[reg]]) {
print "Match: ", root, "+", regs[reg], "+", plus[regs[reg]]
}
}
}
}
' inputfile
В предложении BEGIN установите regdelim на символ, который не отображается в ваших данных.
У меня естьпропущен код обработки минус-данных.
Вывод:
Match: a + b + c
Match: f + g + h
Редактировать 2:
Версия ниже позволяет вам искать произвольныекомбинации.Он обобщает технику, использованную в оригинальной версии, поэтому нет необходимости дублировать код.Также исправлено несколько других ошибок ограничений .
#!/bin/bash
# written by Dennis Williamson - 2010-11-12
# for /3395312/podschet-vhozhdeniya-podgrafa-v-grafe
# A (AB) B, A (AC) C, B (BC) C - where "(XY)" represents a + or a -
# provided by the positional parameters $1, $2 and $3
# $4 carries the data file name and is referenced at the end of the script
awk -v AB=$1 -v AC=$2 -v BC=$3 '
BEGIN { regdelim = "|" }
{
if ($2 == AB) {
if (regAB[$1]) delim=regdelim; else delim=""
regAB[$1]=regAB[$1] delim $3
}
if ($2 == AC) {
if (regAC[$1]) delim=regdelim; else delim=""
regAC[$1]=regAC[$1] delim $3
}
if ($2 == BC) {
if (regBC[$1]) delim=regdelim; else delim=""
regBC[$1]=regBC[$1] delim $3
}
}
END {
for (root in regAB) {
split(regAB[root],ABarray,regdelim)
for (ABindex in ABarray) {
split(regAC[root],ACarray,regdelim)
for (ACindex in ACarray) {
split(regBC[ABarray[ABindex]],BCarray,regdelim)
for (BCindex in BCarray) {
if (ACarray[ACindex] == BCarray[BCindex]) {
print " Match:", root, AB, ABarray[ABindex] ",", root, AC, ACarray[ACindex] ",", ABarray[ABindex], BC, BCarray[BCindex]
}
}
}
}
}
}
' "$4"
Это можно назвать так, чтобы выполнить исчерпывающий поиск:
for ab in + -; do for ac in + -; do for bc in + -; do echo "Searching: $ab$ac$bc"; ./searchgraph $ab $ac $bc inputfile; done; done; done
Для этих данных:
a - e
a + b
b + c
c - f
m - n
b - d
a + c
b - e
l - n
f + g
b + i
g + h
l + m
f + h
a + i
a - j
k - j
a - k
Вывод цикла оболочки, вызывающего новую версию скрипта, будет выглядеть следующим образом:
Searching: +++
Match: a + b, a + c, b + c
Match: a + b, a + i, b + i
Match: f + g, f + h, g + h
Searching: ++-
Searching: +-+
Searching: +--
Match: l + m, l - n, m - n
Match: a + b, a - e, b - e
Searching: -++
Searching: -+-
Searching: --+
Searching: ---
Match: a - k, a - j, k - j
Редактировать 3:
Graphviz
Другим подходом будет использование Graphviz .Язык DOT может описывать график, а gvpr, который является "AWK-подобным" 1 языком программирования, может анализировать и манипулировать файлами DOT.
Учитывая входные данные в формате, показанном в вопросе, вы можете использовать следующую программу AWK для преобразования их в DOT:
#!/usr/bin/awk -f
BEGIN {
print "digraph G {"
print " size=\"5,5\""
print " ratio=.85"
print " node [fontsize=24 color=blue penwidth=3]"
print " edge [fontsize=18 labeldistance=5 labelangle=-8 minlen=2 penwidth=3]"
print " {rank=same; f l}"
m = "-" # ASCII minus/hyphen as in the source data
um = "−" # u2212 minus: − which looks better on the output graphic
p = "+"
}
{
if ($2 == m) { $2 = um; c = lbf = "red"; arr=" arrowhead = empty" }
if ($2 == p) { c = lbf = "green3"; arr="" }
print " " $1, "->", $3, "[taillabel = \"" $2 "\" color = \"" c "\" labelfontcolor = \"" lbf "\"" arr "]"
}
END {
print "}"
}
Команда для запуска будет выглядеть примерно так:
$ ./dat2dot data.dat > data.dot
Вы можете создать рисунок выше, используя:
$ dot -Tpng -o data.png data.dot
Я использовал расширенные данные, как указано вышев этом ответе.
Чтобы выполнить исчерпывающий поиск по типу указанных вами подграфов, вы можете использовать следующую программу gvpr:
BEGIN {
edge_t AB, BC, AC;
}
E {
AB = $;
BC = fstedge(AB.head);
while (BC && BC.head.name != AB.head.name) {
AC = isEdge(AB.tail,BC.head,"");
if (AC) {
printf("%s %s %s, ", AB.tail.name, AB.taillabel, AB.head.name);
printf("%s %s %s, ", AC.tail.name, AC.taillabel, AC.head.name);
printf("%s %s %s\n", BC.tail.name, BC.taillabel, BC.head.name);
}
BC = nxtedge(BC, AB.head);
}
}
Для ее запуска вы можете использовать:
$ gvpr -f groups.g data.dot | sort -k 2,2 -k 5,5 -k 8,8
Вывод будет аналогичен приведенному выше для комбинации AWK / оболочки (в разделе «Редактировать 2»):
a + b, a + c, b + c
a + b, a + i, b + i
f + g, f + h, g + h
a + b, a − e, b − e
l + m, l − n, m − n
a − k, a − j, k − j
1 Грубо говоря.